Kitahara and Mizuno get new bounds for the number of distinct solutions generated by the simplex method for linear programming (LP). In this paper, we combine results of Kitahara and Mizuno and Tardos’s strongly polynomial algorithm, and propose an algorithm for solving a standard form LP problem. The algorithm solves polynomial number of artificial LP … Read more
Although it is easy to prove the sufficient conditions for optimality of a linear program, the necessary conditions pose a pedagogical challenge. A widespread practice in deriving the necessary conditions is to invoke Farkas’ lemma, but proofs of Farkas’ lemma typically involve “nonlinear” topics such as separating hyperplanes between disjoint convex sets, or else more … Read more
This paper provides operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping in linear optimization under uniqueness of nominal optimal solutions. Our analysis is developed in two different parametric settings. First, in the framework of canonical perturbations … Read more
Cooperative games with transferable utilities belong to a branch of game theory where groups of players can enter into binding agreements and form coalitions in order to jointly achieve some objectives. In a cooperative setting, one of the most important questions to address is how to establish a payoff distribution among the players in such … Read more
Kalai and Kleitman established the bound $n^{\log(d) + 2}$ for the diameter of a $d$-dimensional polyhedron with $n$ facets. Here we improve the bound slightly to $(n-d)^{\log(d)}$. CitationSchool of Operations Research and Information Engineering, Cornell University, Ithaca NY, USA, February 2014ArticleDownload View PDF
We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called infeasibility step and a few – at most three – centering steps. In this paper each iteration consists of only a infeasibility step, whereas the iteration bound improves the … Read more
We present a strongly polynomial algorithm for linear optimization problems of the form min{cx|Ax = b, x >= 0} having 0-1 vectors among their optimal solutions. The algorithm runs in time O(n^4*max\{m,log n}), where n is the number of variables and m is the number of equations. The algorithm also constructs necessary and sufficient optimality … Read more
Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more
Many practical problems can be formulated as $\ell_0$-minimization problems with nonnegativity constraints, which seek the sparsest nonnegative solutions to underdetermined linear systems. Recent study indicates that $\ell_1$-minimization is efficient for solving some classes of $\ell_0$-minimization problems. From a mathematical point of view, however, the understanding of the relationship between $\ell_0$- and $\ell_1$-minimization remains incomplete. In … Read more
This is the “front matter” of a new open-source book on Linear Optimization. The book and associated Matlab/AMPL/Mathematica programs are freely available from: https://sites.google.com/site/jonleewebpage/home/publications/#book CitationJon Lee, “A First Course in Linear Optimization”, Third Edition, Reex Press, 2013-2017.ArticleDownload View PDF