linear programming

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

On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances

Categories Applications - OR and Management Sciences, Linear Programming, Network Optimization Tags , , , , ,

Benchmark instances for multicommodity flow problems frequently lack the structural nuances of real-world networks or fail to maintain a rigorous mathematical relationship with their single-commodity counterparts. This paper introduces a formal meta-generation framework that addresses these limitations by lifting single-commodity minimum-cost flow instances into the multicommodity space while strictly preserving the underlying network topology, capacity … Read more

Folding Mixed-Integer Linear Programs and Reflection Symmetries

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

For mixed-integer linear programming and linear programming it is well known that symmetries can have a negative impact on the performance of branch-and-bound and linear optimization algorithms. A common strategy to handle symmetries in linear programs is to reduce the dimension of the linear program by aggregating symmetric variables and solving a linear program of … Read more

The SCIP Optimization Suite 10.0

Categories Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems Tags , , , , , , , , ,

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in SCIP Optimization Suite 10.0. The updates in SCIP 10.0 include a new solving mode for exactly solving rational mixed-integer linear programs, a new presolver … Read more

On Parametric Linear Programming Duality

Categories Linear Programming, Other Topics Tags , , ,

Recognizing the strength of parametric optimization to model uncertainty, we extend the classical linear programming duality theory to a parametric setting. For linear programs with parameters in general locations, we prove parametric weak and strong duality theorems and parametric complementary slackness theorems. ArticleDownload

Solving a linear program via a single unconstrained minimization

Categories Linear Programming, Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

This paper proposes a novel approach for solving linear programs. We reformulate a primal-dual linear program as an unconstrained minimization of a convex and twice continuously differentiable merit function. When the optimal set of the primal-dual pair is nonempty, its optimal set is equal to the optimal set of the proposed merit function. Minimizing this … Read more

When Does Primal Interior Point Method Beat Primal-dual in Linear Optimization?

Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , ,

The primal-dual interior point method (IPM) is widely regarded as the most efficient IPM variant for linear optimization. In this paper, we demonstrate that the improved stability of the pure primal IPM can allow speedups relative to a primal-dual solver, particularly as the IPM approaches convergence.  The stability of the primal scaling matrix makes it … Read more

Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Linear Programming Tags , , , , , , ,

Given a family of linear constraints and a linear objective function one can consider whether to apply a Linear Programming (LP) algorithm or use a Linear Superiorization (LinSup) algorithm on this data. In the LP methodology one aims at finding a point that fulfills the constraints and has the minimal value of the objective function … Read more

A Primal-Dual Frank-Wolfe Algorithm for Linear Programming

Categories Linear Programming Tags , , ,

We present two first-order primal-dual algorithms for solving saddle point formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming) and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both the primal and dual of the saddle point formulation of a standard-form LP. The latter is a modification of FWLP in which regularizing perturbations are … Read more