Jesús A. De Loera – Optimization Online

On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond

Published: 2014/08/18, Updated: 2015/12/07

(Mixed) Integer Linear Programming, Linear Programming augmentation, circuit, edmonds-karp, elementary vector, graver basis, integer program, linear programming, steepest descent, steepest descent vector, test set

Motivated by Bland’s linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using “discrete steepest-descent augmentations” (i.e., directions with the best … Read more

On Chubanov’s method for Linear Programming

Published: 2012/04/09

We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new … Read more

The central curve in linear programming

Published: 2010/12/17

Jesús A. De Loera

Bernd Sturmfels

Cynthia Vinzant

Convex Optimization, Linear Programming, Nonlinear Optimization central path, curvature, degree, gauss map, groebner basis, hyperbolic polynomial, hyperplane arrangement, interior point methods, linear programming, matroid, projective variety, tutte polynomial

The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more

Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility

Published: 2008/01/29

(Mixed) Integer Nonlinear Programming, Combinatorial Optimization, Graphs and Matroids coloring, nullstellensatz, polynomial system

Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more

Pareto Optima of Multicriteria Integer Linear Programs

Published: 2007/07/10

Jesús A. De Loera

Raymond Hemmecke

Matthias Köppe

Integer Programming, Multi-Criteria Optimization

We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomial-space polynomial-delay prescribed-order enumeration algorithm … Read more

Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz

Published: 2007/06/13

Combinatorial Optimization, Integer Programming, Nonlinear Optimization hilbert's nullstellensatz, polynomial method

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new … Read more