In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Liftand-Project, Flow and Knapsack cover): onMIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.

Quadratic programs obtained for optimal control problems of dynamic or discrete-time processes usually involve highly block structured Hessian and constraints matrices, to be exploited by efficient numerical methods. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite factorization codes. For active set methods, however, conventional dense matrix techniques suffer from the need to update base matrices in every active set iteration, thereby loosing the sparsity structure after a few updates. This contribution presents a new factorization of a KKT matrix arising in active set methods for optimal control. It fully respects the block structure without any fill-in. For this factorization, matrix updates are derived for all cases of active set changes. This allows for the design of a highly efficient block structured active set method for optimal control and model predictive control problems with long horizons or many control parameters.

Finding good (or even just feasible) solutions forMixed-Integer Nonlinear Programming problems independently of the specific problem structure is a very hard but practically important task, especially when the objective and/or the constraints are nonconvex. With this goal in mind, we present a general-purpose heuristic based on Variable Neighborhood Search, Local Branching, a local Nonlinear Programming algorithm and Branch-and-Bound.We test the proposed approach on MINLPLib, comparing with several existing heuristic and exact methods. An implementation of the proposed heuristic is freely available and can employ all NLP/MINLP solvers with an AMPL interface as the main search tools.

This paper develops a general framework for solving a variety of convex cone problems that frequently arise in signal processing, machine learning, statistics, and other fields. The approach works as follows: first, determine a conic formulation of the problem; second, determine its dual; third, apply smoothing; and fourth, solve using an optimal first-order method. A merit of this approach is its flexibility: for example, all compressed sensing problems can be solved via this approach. These include models with objective functionals such as the total-variation norm, ||Wx||1 where W is arbitrary, or a combination thereof. In addition, the paper introduces a number of technical contributions such as a novel continuation scheme and a novel approach for controlling the step size, and applies results showing that the smooth and unsmoothed problems are sometimes formally equivalent. Combined with our framework, these lead to novel, stable and computationally efficient algorithms. For instance, our general implementation is competitive with state-of-the-art methods for solving intensively studied problems such as the LASSO. Further, numerical experiments show that one can solve the Dantzig selector problem, for which no efficient large-scale solvers exist, in a few hundred iterations. Finally, the paper is accompanied with a software release. This software is not a single, monolithic solver; rather, it is a suite of programs and routines designed to serve as building blocks for constructing complete algorithms.

We describe Pyomo, an open source software package for modeling and solving mathematical programs in Python. Pyomo can be used to define abstract and concrete problems, create problem instances, and solve these instances with standard open-source and commercial solvers. Pyomo provides a capability that is commonly associated with algebraic modeling languages such as AMPL, AIMMS, and GAMS. In contrast, Pyomo’s modeling objects are embedded within a full-featured highlevel programming language with a rich set of supporting libraries. Pyomo leverages the capabilities of the Coopr software library, which together with Pyomo is part of IBM’s COIN-OR open-source initiative for operations research software. Coopr integrates Python packages for defining optimizers, modeling optimization applications, and managing computational experiments. Numerous examples illustrating advanced scripting applications are provided.

We solve for the first time to proven optimality the small instances in the classical literature benchmark of Minimum Linear Arrangement. This is achieved by formulating the problem as an ILP in a somehow unintuitive way, using variables expressing the fact that a vertex is between two other adjacent vertices in the arrangement. Using (only) these variables appears to be the key idea of the approach. Indeed, with these variables already the use of very simple constraints leads to good results, which can however be improvedwith amore detailed study of the underlying polytope.

Gomory mixed-integer cuts (GMICs) are widely used in modern branchand-cut codes for the solution of mixed-integer programs. Typically, GMICs are iteratively generated from the optimal basis of the current linear programming (LP) relaxation, and immediately added to the LP before the next round of cuts is generated. Unfortunately, this approach is prone to instability. In this paper we analyze a different scheme for the generation of rank-1 GMICs read from a basis of the original LP—the one before the addition of any cut.We adopt a relax-and-cut approach where the generated GMICs are not added to the current LP, but immediately relaxed in a Lagrangian fashion. Various elaborations of the basic idea are presented, that lead to very fast—yet accurate—variants of the basic scheme. Very encouraging computational results are presented, with a comparison with alternative techniques from the literature also aimed at improving the GMIC quality. We also show how our method can be integrated with other cut generators, and successfully used in a cut-and-branch enumerative framework.

This paper reports on the fifth version of theMixed Integer Programming Library. The miplib 2010 is the first miplib release that has been assembled by a large group from academia and from industry, all of whom work in integer programming. There was mutual consent that the concept of the library had to be expanded in order to fulfill the needs of the community. The new version comprises 361 instances sorted into several groups. This includes the main benchmark test set of 87 instances, which are all solvable by today’s codes, and also the challenge test set with 164 instances, many of which are currently unsolved. For the first time, we include scripts to run automated tests in a predefined way. Further, there is a solution checker to test the accuracy of provided solutions using exact arithmetic.

We consider the (block-angular) min–max resource sharing problem, which is defined as follows. Given finite sets of resources and of customers, a convex set c, called block, and a convex function gc:cR+ for every c, the task is to find bcc (c) approximately attaining :=infmaxrc(gc(bc))rbcc (c) . As usual we assume that g c can be computed efficiently and we have a constant ? ? 1 and oracle functions fc:R+c, called block solvers, which for c and yR+ return an element bcc with ygc(bc)infbcygc(b). We describe a simple algorithm which solves this problem with an approximation guarantee ?(1 + ?) for any ? > 0, and whose running time is O((+)log(loglog+?2)) for any fixed ? ? 1, where ? is the time for an oracle call. This generalizes and improves various previous results. We also prove other bounds and describe several speed-up techniques. In particular, we show how to parallelize the algorithm efficiently. In addition we review another algorithm, variants of which were studied before. We show that this algorithm is almost as fast in theory, but it was not competitive in our experiments. Our work was motivated mainly by global routing in chip design. Here the blocks are mixed-integer sets (whose elements are associated with Steiner trees), and we combine our algorithm with randomized rounding. We present experimental results on instances resulting from recent industrial chips, with millions of customers and resources. Our algorithm solves these instances nearly optimally in less than two hours.

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.

We consider the following natural heuristic for the Symmetric Traveling Salesman Problem: solve the subtour relaxation, yielding a solution x?, and then find the best tour ¯ x that is compatible with x?, where compatible means that every subtour elimination constraint that is satisfied at equality at x? is also satisfied at equality at ¯ x. We prove that finding the best compatible tour is NP-hard and show that the tour can have a cost approaching 5/3 that of the optimal tour. We then describe a branch-and-cut algorithm for computing the best compatible tour, and present extensive computational results for TSPLIB instances. It turns out that, in practice, the tour is usually of very good quality. Moreover, the computational effort for computing the compatible tour is considerably smaller than that of solving the full problem with the best available software, i.e., Concorde.