Discrete optimal transport problems give rise to very large linear programs (LPs) with a particular structure of the constraint matrix. In this paper, we present a hybrid algorithm that mixes an interior point method (IPM) and column generation, 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 propose a column generation–like technique to force all intermediate iterates to be as sparse as possible. The algorithm is implemented nearly matrix-free. Indeed, most of the computations avoid forming the huge matrices involved and solve the Newton system using only a much smaller Schur complement of the normal equations. We prove theoretical results about the sparsity pattern of the optimal solution, exploiting the graph structure of the underlying problem. We use these results to mix iterative and direct linear solvers efficiently in a way that avoids producing preconditioners or factorizations with excessive fill-in and at the same time guaranteeing a low number of conjugate gradient iterations. We compare the proposed method with two state-of-the-art solvers and show that it can compete with the best network optimization tools in terms of computational time and memory use. We perform experiments with problems reaching more than four billion variables and demonstrate the robustness of the proposed method. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Funding: F. Zanetti received funding from the University of Edinburgh, in the form of a PhD scholarship. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0184 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0184 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Abstract A new framework for portfolio diversification is introduced which goes beyond the classical mean-variance approach and portfolio allocation strategies such as risk parity. It is based on a novel concept called portfolio dimensionality that connects diversification to the non-Gaussianity of portfolio returns and can typically be defined in terms of the ratio of risk measures which are homogenous functions of equal degree. The latter arises naturally due to our requirement that diversification measures should be leverage invariant. We introduce this new framework and argue the benefits relative to existing measures of diversification in the literature, before addressing the question of optimizing diversification or, equivalently, dimensionality. Maximising portfolio dimensionality leads to highly non-trivial optimization problems with objective functions which are typically non-convex and potentially have multiple local optima. Two complementary global optimization algorithms are thus presented. For problems of moderate size and more akin to asset allocation problems, a deterministic Branch and Bound algorithm is developed, whereas for problems of larger size a stochastic global optimization algorithm based on Gradient Langevin Dynamics is given. We demonstrate analytically and through numerical experiments that the framework reflects the desired properties often discussed in the literature.

Abstract A standard quadratic program is an optimization problem that consists of minimizing a (nonconvex) quadratic form over the unit simplex. We focus on reformulating a standard quadratic program as a mixed integer linear programming problem. We propose two alternative formulations. Our first formulation is based on casting a standard quadratic program as a linear program with complementarity constraints. We then employ binary variables to linearize the complementarity constraints. For the second formulation, we first derive an overestimating function of the objective function and establish its tightness at any global minimizer. We then linearize the overestimating function using binary variables and obtain our second formulation. For both formulations, we propose a set of valid inequalities. Our extensive computational results illustrate that the proposed mixed integer linear programming reformulations significantly outperform other global solution approaches. On larger instances, we usually observe improvements of several orders of magnitude.

This paper studies the combined problem of base station location and optimal power allocation, in order to optimize the energy efficiency of a cellular wireless network. Recent work has suggested that moving from a network of a small number of high power macrocells to a larger number of smaller microcells may improve the energy efficiency of the network. This paper investigates techniques to optimize the number of base stations and their locations, in order to minimize energy consumption. An important contribution of the paper is that it takes into account non-uniform user distributions across the coverage area, which is likely to be encountered in practice. The problem is solved using approaches from optimization theory that deal with the facility location problem. Stochastic programming techniques are used to deal with the expected user distributions. An example scenario is presented to illustrate how the technique works and the potential performance gains that can be achieved.

In this note we point out that the assumptions of Propositions 1 and 2 in Gondzio (1997) are not sufficiently restrictive. We give an example that demonstrates the lack of precision in these propositions and discuss the necessary modifications of the propositions.

Several issues concerning an analysis of large and sparse linear programming problems prior to solving them with an interior point based optimizer are addressed in this paper. Three types of presolve procedures are distinguished. Routines from the first class repeatedly analyze an LP problem formulation: eliminate empty or singleton rows and columns, look for primal and dual forcing or dominated constraints, tighten bounds for variables and shadow prices or just the opposite, relax them to find implied free variables. The second type of analysis aims at reducing a fill-in of the Cholesky factor of the normal equations matrix used to compute orthogonal projections and includes a heuristic for increasing the sparsity of the LP constraint matrix and a technique of splitting dense columns in it. Finally, routines from the third class detect, and remove, different linear dependecies of rows and columns in a constraint matrix. Computational results on problems from the Netlib collection, including some recently added infeasible ones, are given.

A method for handling the inverse of linear programming bases is presented. The method extensively exploits the fact that the original problem data (i.e., the constraint matrix) must be stored anyway. It then builds the basis inverse representation of two matrices: an easily invertible submatrix of the constraint matrix (fundamental basis) and a Schur complement containing information on the difference between the fundamental and the current bases. Since the fundamental basis does not have to be stored, the memory space required by the method is limited to that for a small, dense Schur complement. Computational comparisons are made with advanced implementations of LU factorizations with Bartels-Golub updating. Tests performed on real-life linear programs from the Netlib collection indicate that the method may be used for solving large problems. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.