Orbital Crossover

Symmetry in optimization has been known to wreak havoc in optimization algorithms. Often, some of the hardest instances are highly symmetric. This is not the case in linear programming, as symmetry allows one to reduce the size of the problem, possibly dramatically, while still maintaining the same optimal objective value. This is done by aggregating … Read more

Regularized Nonsmooth Newton Algorithms for Best Approximation

We consider the problem of finding the best approximation point from a polyhedral set, and its applications, in particular to solving large-scale linear programs. The classical projection problem has many various and many applications. We study a regularized nonsmooth Newton type solution method where the Jacobian is singular; and we compare the computational performance to … Read more

A binary linear programming approach for supporting administrative territorial consolidation

The objective of this paper is to develop a scalable binary linear programming model for finding the optimal aggregation of communes into spatially contiguous administrative territorial units (ATUs) constrained on certain balancing criteria. The requirement for the ATUs to be contiguous represents the main computational bottleneck and, therefore, it prevents one from using such models … Read more

COIL: A Deep Architecture for Column Generation

Column generation is a popular method to solve large-scale linear programs with an exponential number of variables. Several important applications, such as the vehicle routing problem, rely on this technique in order to be solved. However, in practice, column generation methods suffer from slow convergence (i.e. they require too many iterations). Stabilization techniques, which carefully … Read more

Polynomial worst-case iteration complexity of quasi-Newton primal-dual interior point algorithms for linear programming

Quasi-Newton methods are well known techniques for large-scale numerical optimization. They use an approximation of the Hessian in optimization problems or the Jacobian in system of nonlinear equations. In the Interior Point context, quasi-Newton algorithms compute low-rank updates of the matrix associated with the Newton systems, instead of computing it from scratch at every iteration. … Read more

Production Theory for Constrained Linear Activity Models

The purpose of this paper is to generalize the framework of activity analysis discussed in Villar (2003) and obtain similar results concerning solvability. We generalize the model due to Villar (2003), without requiring any dimensional requirements on the activity matrices and by introducing a model of activity analysis in which each activity may (or may … Read more

A primal-dual majorization-minimization method for large-scale linear programs

We present a primal-dual majorization-minimization method for solving large-scale linear programs. A smooth barrier augmented Lagrangian (SBAL) function with strict convexity for the dual linear program is derived. The majorization-minimization approach is naturally introduced to develop the smoothness and convexity of the SBAL function. Our method only depends on a factorization of the constant matrix … Read more

A Sparse Interior Point Method for Linear Programs arising in Discrete Optimal Transport

Discrete Optimal Transport problems give rise to very large linear programs (LP) with a particular structure of the constraint matrix. In this paper we present an interior point method (IPM) specialized for the LP originating from the Kantorovich Optimal Transport problem. Knowing that optimal solutions of such problems display a high degree of sparsity, we … Read more

Lexicographic Branch-and-Bound Column Search

We present an exact generic method for solving the pricing problem in a column generation approach, which we call branch-and-bound column search. It searches the space of all feasible columns via a branch-and-bound tree search and returns all columns with a reduced-cost value below a certainthreshold. The approach is based on an idea from Krumke … Read more