China
Africa
Explore chapters and articles related to this topic
A Dynamical Systems Approach to Solving Linear Programming Problems
Published in K. D. Elworthy, W. Norrie Evenitt, E. Bruce Lee, Differential equations, dynamical systems, and control science, 2017
Stanislaw H. Zak, Viriya Upatising, Walter E. Lillo, Stefen Hui
Linear programming (LP) plays a fundamental role in many disciplines such as economics, strategic planning, analysis of algorithms, combinatorial problems, etc. In 1947, Dantzig ([1]) developed a method for solving linear programs which is known today as the simplex method. In 1951, Brown and Koopmans ([2]) described the first of a series of interior point methods for solving linear programs. Khachiyan ([3]) showed that linear programming problems can be solved in polynomial time using his ellipsoid method (see [4] for a discussion of this technique). However, computational experience with the ellipsoid algorithm has shown that it is not a practical alternative to the simplex method ([5, 6]). Recently, Karmarkar ([7]) (see also Strang ([8]) or Schrijver ([4]) for more details of this method) developed a linear programming algorithm which solves some complicated real-world problems of scheduling, routing and planning more efficiently than the simplex method. The simplex method is classified as an exterior point method and Karmarkar's method is classified as an interior point method ([9]). Recently, Gill et al. ([6]) showed that the whole family of the interior point methods can be derived from some classical results from the field of nonlinear programming. The classical methods of nonlinear programming include the penalty function method ([10]) and the barrier method ([11]). Conn ([12]) developed alternative methods for solving linear programs utilizing unconstrained optimization with penalty function methods. Another approach to solving LP problems, using interconnected networks of simple analog processors, was proposed by Pyne ([13]) and later studied by Rybashov ([14, 15]), Karpinskaya ([16]), and others. Since then various dynamic LP problem solvers have been proposed - see e.g. Tank and Hopfield ([17]), Kennedy and Chua ([18]), Rodriguez-Vazquez et al. ([19]), and Cichocki and Unbehauen ([20]).
Practical taxi sharing schemes at large transport terminals
Published in Transportmetrica B: Transport Dynamics, 2019
Zhiyuan Liu, Shuaian Wang, Kai Huang, Jun Chen, Yingna Fu
We give a sketch of the idea of how [P1] is solved in polynomial time based on Schrijver (2003). The maximum weight matching problem is equivalent to the maximum weight perfect matching problem. The convex hull of all of the feasible solutions to the maximum weight perfect matching problem can be explicitly defined by a set of constraints, the number of which is exponential. However, there is a strongly polynomial time algorithm that can check whether a point satisfies all of the constraints, and if the answer is no, output a violated constraint. Thus the separation oracle is polynomially solvable. The equivalence between optimization and separation via the ellipsoid method leads to a polynomial time algorithm for the maximum weight matching problem.