MPC

MPC 2014, ISSUE 4



Mathematical Programming Computation, Volume 6, Issue 4, December 2014

qpOASES: a parametric active-set algorithm for quadratic programming

Hans Joachim Ferreau, Christian Kirches, Andreas Potschka, Hans Georg Bock, Moritz Diehl

Many practical applications lead to optimization problems that can either be stated as quadratic programming (QP) problems or require the solution ofQP problems on a lower algorithmic level. One relatively recent approach to solve QP problems are parametric active-set methods that are based on tracing the solution along a linear homotopy between a QP problem with known solution and the QP problem to be solved. This approach seems to make them particularly suited for applications where a-priori information can be used to speed-up the QP solution or where high solution accuracy is required. In this paper we describe the open-source C++ software package qpOASES,which implements a parametric active-setmethod in a reliable and efficient way. Numerical tests show that qpOASES can outperform other popular academic and commercial QP solvers on small- to medium-scale convex test examples of theMaros-Mészáros QP collection. Moreover, various interfaces to third-party software packages make it easy to use, even on embedded computer hardware. Finally, we describe how qpOASES can be used to compute critical points of nonconvex QP problems.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 4, December 2014

Branch-and-cut for complementarity-constrained optimization

Ismael R. de Farias Jr., Ernee Kozyreff, Ming Zhao

We report and analyze the results of our computational testing of branch-and-cut for the complementarity-constrained optimization problem (CCOP). Besides theMIP cuts commonly present in commercial optimization software,weused inequalities that explore complementarity constraints. To do so,we generalized two families of cuts proposed earlier by de Farias, Johnson, and Nemhauser that had never been tested computationally. Our test problems consisted of linear, binary, and general integer programs with complementarity constraints. Our results on the use of complementarity cuts within a major commercial optimization solver show that they are of critical importance to tackling difficult CCOP instances, typically reducing the computational time required to solve them tremendously.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 4, December 2014

Using symmetry to optimize over the Sherali–Adams relaxation

James Ostrowski

In this paper we examine the impact of using the Sherali–Adams procedure on highly symmetric integer programming problems. Linear relaxations of the extended formulations generated by Sherali–Adams can be very large, containing O ((n,d)) many variables for the level-d closure. When large amounts of symmetry are present in the problem instance however, the symmetry can be used to generate a much smaller linear program that has an identical objective value. We demonstrate this by computing the bound associated with the level 1, 2, and 3 relaxations of several highly symmetric binary integer programming problems. We also present a class of constraints, called counting constraints, that further improves the bound, and in some cases provides a tight formulation. A major advantage of the Sherali–Adams formulation over the traditional formulation is that symmetry-breaking constraints can be more efficiently implemented. We show that using the Sherali–Adams formulation in conjunction with the symmetry breaking tool isomorphism pruning can lead to the pruning of more nodes early on in the branch-and-bound process.

Full Text: PDF



MPC 2014, ISSUE 3



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

An exact cooperative method for the uncapacitated facility location problem

Marius Posta, Jacques A. Ferland, Philippe Michelon

In this paper, we present a cooperative primal-dual method to solve the uncapacitated facility location problem exactly. It consists of a primal process, which performs a variation of a knownand effective tabu search procedure, and a dual process, which performs a lagrangian branch-and-bound search. Both processes cooperate by exchanging information which helps them find the optimal solution. Further contributions include new techniques for improving the evaluation of the branch-and-bound nodes: decision-variable bound tightening rules applied at each node, and a subgradient caching strategy to improve the bundle method applied at each node.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

Optimization of algorithms with OPAL

Charles Audet, Kien-Cong Dang, Dominique Orban

Opal is a general-purpose system for modeling and solving algorithm optimization problems. Opal takes an algorithm as input, and as output it suggests parameter values that maximize some user-defined performance measure. In order to achieve this, the user provides a Python script describing how to launch the target algorithm, and defining the performance measure. Opal then models this question as a blackbox optimization problem which is then solved by a state-of-the-art direct search solver. Opal handles a wide variety of parameter types, it can exploit multiple processors in parallel at different levels, and can take advantage of a surrogate blackbox. Several features of Opal are illustrated on a problem consisting in the design of a hybrid sort strategy.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

Boosting the feasibility pump

Natashia L. Boland, Andrew C. Eberhard, Faramroze G. Engineer, Matteo Fischetti, Martin W. P. Savelsbergh, Angelos Tsoukalas

The feasibility pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimize the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of enhancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 3, September 2014

A partial proximal point algorithm for nuclear norm regularized matrix least squares problems

Kaifeng Jiang, Defeng Sun, Kim-Chuan Toh

We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semismoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.

Full Text: PDF



MPC 2014, ISSUE 2



Mathematical Programming Computation, Volume 6, Issue 2, June 2014

A first-order block-decomposition method for solving two-easy-block structured semidefinite programs

Renato D. C. Monteiro, Camilo Ortiz, Benar F. Svaiter

In this paper, we consider a first-order block-decomposition method for minimizing the sum of a convex differentiable function with Lipschitz continuous gradient, and two other proper closed convex (possibly, nonsmooth) functions with easily computable resolvents. The method presented contains two important ingredi- ents from a computational point of view, namely: an adaptive choice of stepsize for performing an extragradient step; and the use of a scaling factor to balance the blocks. We then specialize the method to the context of conic semidefinite programming (SDP) problems consisting of two easy blocks of constraints. Without putting them in standard form, we show that four important classes of graph-related conic SDP problems auto- matically possess the above two-easy-block structure, namely: SDPs for O-functions and O+-functions of graph stable set problems, and SDP relaxations of binary inte- ger quadratic and frequency assignment problems. Finally, we present computational results on the aforementioned classes of SDPs showing that our method outperforms the three most competitive codes for large-scale conic semidefinite programs, namely: the boundary point (BP) method introduced by Povh et al., a Newton-CG augmented Lagrangian method, called SDPNAL, by Zhao et al., and a variant of the BP method, called the SPDAD method, by Wen et al.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 2, June 2014

A Newton’s method for the continuous quadratic knapsack problem

Roberto Cominetti, Walter F. Mascarenhas, Paulo J. S. Silva

We introduce a new efficient method to solve the continuous quadratic knapsack problem. This is a highly structured quadratic program that appears in dif- ferent contexts. The method converges after O(n) iterations with overall arithmetic complexity O(n2). Numerical experiments show that in practice the method con- verges in a small number of iterations with overall linear complexity, and is faster than the state-of-the-art algorithms based on median finding, variable fixing, and secant techniques.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 2, June 2014

A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows

Andrea Bettinelli, Alberto Ceselli, Giovanni Righini

The growing cost of transportation and distribution pushes companies, especially small and medium transportation enterprises, to form partnership and to exploit economies of scale. On the other hand, to increase their competitiveness on the market, companies are asked to consider preferences of the customers as well. Therefore, tools for logistics management need to manage collective resources, as many depots and heterogeneous fleets, providing flexible preference handling at the same time. In this paper we tackle a pickup and delivery vehicle routing problem involving such aspects; customers place preferences on visiting time (represented as soft time windows), and their violation is allowed at a price. Our interest in this problem stems from an ongo- ing industrial project. First we propose an exact branch-and-price algorithm, having as a core advanced dynamic programming techniques. Then we analyze through a computational campaign the impact of soft time windows management on the optimal solution in terms of both routing and overall distribution costs. Our experiments show that our approach can solve instances of real size, and clarify the practical usefulness of soft time windows management.

Full Text: PDF



MPC 2014, ISSUE 1



Mathematical Programming Computation, Volume 6, Issue 1, March 2014

Matrix-free interior point method for compressed sensing problems

Kimon Fountoulakis, Jacek Gondzio, Pavel Zhlobich

We consider a class of optimization problems for sparse signal reconstruction which arise in the field of compressed sensing (CS). A plethora of approaches and solvers exist for such problems, for example GPSR, FPC_AS, SPGL1, NestA, 1 L(1)_L(s), PDCO to mention a few. CS applications lead to very well conditioned optimization problems and therefore can be solved easily by simple first-order methods. Interior point methods (IPMs) rely on the Newton method hence they use the second-order information. They have numerous advantageous features and one clear drawback: being the second-order approach they need to solve linear equations and this operation has (in the general dense case) an O(n3) computational complexity. Attempts have been made to specialize IPMs to sparse reconstruction problems and they have led to interesting developments implemented in L(1)_L(s) and PDCO softwares. We go a few steps further. First, we use the matrix-free IPM, an approach which redesigns IPM to avoid the need to explicitly formulate (and store) the Newton equation systems. Secondly, we exploit the special features of the signal processing matrices within the matrix-free IPM. Two such features are of particular interest: an excellent conditioning of these matrices and the ability to perform inexpensive (low complexity) matrix–vector multiplications with them. Computational experience with large scale one-dimensional signals confirms that the new approach is efficient and offers an attractive alternative to other state-of-the-art solvers.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 1, March 2014

RENS

Timo Berthold

This article introduces rens, the relaxation enforced neighborhood search, a large neighborhood search algorithm for mixed integer nonlinear programs (MINLPs). It uses a sub-MINLP to explore the set of feasible roundings of an optimal solution ¯ x of a linear or nonlinear relaxation. The sub-MINLP is constructed by fixing integer variables x j with ¯ x j ? Z and bounding the remaining integer variables to x j ? {¯x j ,  ¯x j }. We describe two different applications of rens: as a standalone algorithm to compute an optimal rounding of the given starting solution and as a primal heuristic inside a complete MINLP solver. We use the former to compare different kinds of relaxations and the impact of cutting planes on the so-called roundability of the corresponding optimal solutions. We further utilize rens to analyze the performance of three rounding heuristics implemented in the branch-cut-and-price framework scip. Finally, we study the impact of rens when it is applied as a primal heuristic inside scip. All experiments were performed on three publicly available test sets of mixed integer linear programs (MIPs), mixed integer quadratically constrained programs (MIQCPs), and MINLPs, using solely software which is available in source code. It turns out that for these problem classes 60 to 70% of the instances have roundable relaxation optima and that the success rate of rens does not depend on the percentage of fractional variables. Last but not least, rens applied as primal heuristic complements nicely with existing primal heuristics in scip.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 1, March 2014

Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem

Pouya Baniasadi, Vladimir Ejov, Jerzy A. Filar, Michael Haythorpe, Serguei Rossomakhine

We present a polynomial complexity, deterministic, heuristic for solving the Hamiltonian cycle problem (HCP) in an undirected graph of order n. Although finding a Hamiltonian cycle is not theoretically guaranteed, we have observed that the heuristic is successful even in cases where such cycles are extremely rare, and it also performs very well on all HCP instances of large graphs listed on the TSPLIB web page. The heuristic owes its name to a visualisation of its iterations. All vertices of the graph are placed on a given circle in some order. The graph’s edges are classified as either snakes or ladders, with snakes forming arcs of the circle and ladders forming its chords. The heuristic strives to place exactly n snakes on the circle, thereby forming a Hamiltonian cycle. The Snakes and Ladders Heuristic uses transformations inspired by k-opt algorithms such as the, now classical, Lin–Kernighan heuristic to reorder the vertices on the circle in order to transform some ladders into snakes and vice versa. The use of a suitable stopping criterion ensures the heuristic terminates in polynomial time if no improvement is made in n3 major iterations.

Full Text: PDF



Mathematical Programming Computation, Volume 6, Issue 1, March 2014

Block splitting for distributed optimization

Neal Parikh, Stephen Boyd

This paper describes a general purposemethod for solving convex optimization problems in a distributed computing environment. In particular, if the problem data includes a large linear operator or matrix A, the method allows for handling eachsub-block of A on a separatemachine. The approach works as follows. First, we define a canonical problem form called graph form, in which we have two sets of variables related by a linear operator A, such that the objective function is separable across these two sets of variables. Many types of problems are easily expressed in graph form, including cone programs and a wide variety of regularized loss minimization problems from statistics, like logistic regression, the support vector machine, and the lasso. Next, we describe graph projection splitting, a form of Douglas–Rachford splitting or the alternating direction method of multipliers, to solve graph form problems serially. Finally, we derive a distributed block splitting algorithm based on graph projection splitting. In a statistical or machine learning context, this allows for training models exactly with a huge number of both training examples and features, such that each processor handles only a subset of both. To the best of our knowledge, this is the only general purpose method with this property. We present several numerical experiments in both the serial and distributed settings.

Full Text: PDF



Imprint and privacy statement

For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2020 by Zuse Institute Berlin (ZIB).