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 subproblem 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 simultaneously returns all columns with a reduced-cost value below a certain threshold. The approach is based on an idea … Read more

A Reduced Jacobian Scheme with Full Convergence for Multicriteria Optimization

In this paper, we propose a variant of the reduced Jacobian method (RJM) introduced by El Maghri and Elboulqe in [JOTA, 179 (2018) 917–943] for multicriteria optimization under linear constraints. Motivation is that, contrarily to RJM which has only global convergence to Pareto KKT-stationary points in the classical sense of accumulation points, this new variant … Read more

Robust Explainable Prescriptive Analytics

We propose a new robust explainable prescriptive analytics framework that minimizes a risk-based objective function under distributional ambiguity by leveraging the data collected on the past realizations of the uncertain parameters affecting the decision model and the side information that have some predictive power on those uncertainties. The framework solves for an explainable response policy … Read more

Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization

Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have … Read more

Tight Probability Bounds with Pairwise Independence

While useful probability bounds for $n$ pairwise independent Bernoulli random variables adding up to at least an integer $k$ have been proposed in the literature, none of these bounds are tight in general. In this paper, we provide several results towards finding tight probability bounds in this direction. Firstly, when $k = 1$, the tightest … Read more