Linear Programming

A Computational Toolbox for Linear Optimization with Joint Affine Chance Constraints

Categories Constrained Nonlinear Optimization, Linear Programming, Optimization Software Benchmark Tags , , , ,

We present a Julia computational toolbox for linear optimization problems with joint affine chance constraints under elliptically symmetric uncertainty. The toolbox combines a spherical–radial oracle for estimating the joint probability and its gradient with three structured optimization methods: Proximal, Feasible, and Penalty. The oracle supports several elliptically symmetric distributions and is integrated with these methods … Read more

Unshackling Column Generation for Linearized Unconstrained Binary Quadratic Programs

Categories Integer Programming, Linear Programming, Nonlinear Optimization Tags , , ,

When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more

An Asymptotic Framework for the Integrality Gap of the Traveling Salesman Problem

Categories 0-1 Programming, Linear Programming Tags , ,

The integrality gap of the subtour elimination relaxation for the Traveling Salesman Problem is a longstanding open problem, epitomized by the \(\frac{4}{3}\)-conjecture. Understanding this gap requires a detailed analysis of the extreme points of the subtour elimination polytope. In this work, we introduce a new perspective for studying the integrality gap through what we call … Read more

The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+8 Non-Zero Components

Categories 0-1 Programming, Linear Programming, Polyhedra Tags , ,

We address the classical Dantzig – Fulkerson – Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution … Read more

ArcLP: A Matlab implementation of an O(√nL) arc-search infeasible interior-point algorithm for linear programming

Categories Linear Programming, Optimization Software and Modeling Systems Tags , ,

This paper presents a Matlab implementation of an arc-search infeasible interior point algorithm for linear programming (LP), which has a proven polynomial bound of O(√nL), the best among all interior-point algorithms for LP. Software architecture and major functions are discussed. Its ease of use is described by a simple example. Crucial strategies are summarized. Quality … Read more

On the exponential circuit imbalance of the Ben-Tal Nemirovski approximation

Categories Linear Programming Tags ,

Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\bar{\chi}_A^*$. Their work builds on Vavasis and Ye’s (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\bar{\chi}_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number … Read more

Sparsity-Preserving Integration of Convex Curvature Information into Linear Relaxations for Quadratic Unconstrained Binary Optimization

Categories Linear Programming, Quadratic Programming, Semi-definite Programming

We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly … Read more

Polyhedral Bounds for Forbidden-Vertices Sets and No-Good Cut Relaxations

Categories (Mixed) Integer Linear Programming, 0-1 Programming, Linear Programming Tags , ,

We study the convex hull obtained after deleting prescribed vertices from the binary cube. The analysis separates three regimes according to the number of deleted vertices. When this number is fixed, both the original-space facet count and the linear extension complexity remain linear in the ambient dimension, up to constants depending only on the number … Read more

Convex Hulls of Binary Reflected Gray Code Intervals

Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra Tags , ,

The binary reflected Gray code orders the vertices of the unit hypercube along a Hamiltonian path in which consecutive vertices differ in exactly one coordinate. While Gray codes have been extensively studied from a combinatorial perspective, much less is known about the polyhedral structure of convex hulls of contiguous subpaths of this order. This paper … Read more

Finding Short Paths on Simple Polytopes

Categories Combinatorial Optimization, Linear Programming, Polyhedra Tags , , , , ,

We prove that computing a shortest monotone path to the optimum of a linear program over a simple polytope is NP-hard, thus resolving a 2022 open question of De Loera, Kafer, and Sanit\`{a}. As a consequence, finding a shortest sequence of pivots to an optimal basis with the simplex method is NP-hard. In fact, we … Read more