Gomory mixed-integer cuts are one of the key components in Branch-and-Cut solvers for mixed-integer linear programs. The textbook formula for generating these cuts is not used directly in open-source and commercial software that work in finite precision: Additional steps are performed to avoid the generation of invalid cuts due to the limited numerical precision of the computations. This paper studies the impact of some of these steps on the safety of Gomory mixed-integer cut generators. As the generation of invalid cuts is a relatively rare event, the experimental design for this study is particularly important. We propose an experimental setup that allows statistically significant comparisons of generators. We also propose a parameter optimization algorithm and use it to find a Gomory mixed-integer cut generator that is as safe as a benchmark cut generator from a commercial solver even though it generates many more cuts.

We study solution approaches for the design of reliably connected networks. Specifically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satisfied is at least 1?, where  is a risk tolerance.We consider two types of connectivity requirements. We first study the problem of requiring an s-t path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability.We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branch-and-cut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to define the set of feasible solutions and violated inequalities in this class can be found efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability.

We describe a set of extensions to the AMPL modeling language to conveniently model mixed-integer optimal control problems forODEorDAE dynamic processes. These extensions are realized as AMPL user functions and suffixes and do not require intrusive changes to theAMPL language standard or implementation itself. We describe and provide TACO, a Toolkit for AMPL Control Optimization that reads AMPL stub.nl files and detects the structure of the optimal control problem. This toolkit is designed to facilitate the coupling of existing optimal control software packages to AMPL.We discuss requirements, capabilities, and the current implementation. Using the example of the multiple shooting code for optimal control MUSCOD-II, a direct and simultaneous method for DAE-constrained optimal control, we demonstrate how the problem information provided by the TACO toolkit is interfaced to the solver. In addition, we show how the MS-MINTOC algorithm for mixed-integer optimal control can be used to efficiently solve mixed-integer optimal control problems modeled in AMPL. We use the AMPL extensions to model three control problem examples and we discuss how those extensions affect the representation of optimal control problems. Solutions to these problems are obtained by usingMUSCOD-II and MS-MINTOC inside the AMPL environment. A collection of further AMPL control models is provided on the web site http://mintoc.de. MUSCOD-II and MS-MINTOC have been made available on the NEOS Server for Optimization, using the TACO toolkit to enable input of AMPL models

For appropriate matrix ensembles, greedy algorithms have proven to be an efficient means of solving the combinatorial optimization problem associated with compressed sensing. This paper describes an implementation for graphics processing units (GPU) of hard thresholding, iterative hard thresholding, normalized iterative hard thresholding, hard thresholding pursuit, and a two-stage thresholding algorithm based on compressive sampling matching pursuit and subspace pursuit. The GPU acceleration of the former bottleneck, namely the matrix–vector multiplications, transfers a significant portion of the computational burden to the identification of the support set. The software solves high-dimensional problems in fractions of a second which permits large-scale testing at dimensions currently unavailable in the literature. The GPU implementations exhibit up to 70× acceleration over standard Matlab central rocessing unit implementations using automatic multi-threading.

We present an exact rational solver for mixed-integer linear programming that avoids the numerical inaccuracies inherent in the floating-point computations used by existing software. This allows the solver to be used for establishing theoretical results and in applications where correct solutions are critical due to legal and financial consequences. Our solver is a hybrid symbolic/numeric implementation of LP-based branch-and-bound, using numerically-safe methods for all binding computations in the search tree. Computing provably accurate solutions by dynamically choosing the fastest of several safe dual bounding methods depending on the structure of the instance, our exact solver is only moderately slower than an inexact floating-point branch-and-bound solver. The software is incorporated into the SCIP optimization framework, using the exact LP solver QSopt_ex and theGMParithmetic library. Computational results are presented for a suite of test instances taken from the Miplib and Mittelmann libraries and for a new collection of numerically difficult instances.

We consider a class of infeasible, path-following methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An implementation, CQP, is available as part of GALAHAD. We illustrate the advantages of our approach on the CUTEr and Maros–Meszaros test sets.

We present two algorithms to solve the Group Lasso problem (Yuan and Lin in, J R Stat Soc Ser B (Stat Methodol) 68(1):49–67, 2006). First, we propose a general version of the Block Coordinate Descent (BCD) algorithm for the Group Lasso that employs an efficient approach for optimizing each subproblem exactly.We show that it exhibits excellent performance when the groups are of moderate size. For groups of large size, we propose an extension of ISTA/FISTA SIAM (Beck and Teboulle in, SIAM J Imag Sci 2(1):183–202, 2009) based on variable step-lengths that can be viewed as a simplified version of BCD. By combining the two approaches we obtain an implementation that is very competitive and often outperforms other state-of-the-art approaches for this problem. We show how these methods fit into the globally convergent general block coordinate gradient descent framework in Tseng and Yun (Math Program 117(1):387–423, 2009). We also show that the proposed approach is more efficient in practice than the one implemented in Tseng and Yun (Math Program 117(1):387–423, 2009). In addition, we apply our algorithms to the Multiple Measurement Vector (MMV) recovery problem, which can be viewed as a special case of the Group Lasso problem, and compare their performance to other methods in this particular instance.

A general framework for cutting-plane generation was proposed by Applegate et al. in the context of the traveling salesman problem. The process considers the image of a problem space under a linear mapping, chosen so that a relaxation of the mapped problem can be solved efficiently. Optimization in the mapped space can be used to find a separating hyperplane, if one exists, and via substitution this gives a cutting plane in the original space.We extend this procedure to general mixed-integer programming problems, obtaining a range of possibilities for new sources of cutting planes. Some of these possibilities are explored computationally, both in floating-point arithmetic and in rational arithmetic.

This paper develops Jellyfish, an algorithm for solving data-processing problems with matrix-valued decision variables regularized to have low rank. Particular examples of problems solvable by Jellyfish include matrix completion problems and least-squares problems regularized by the nuclear norm or ?2-norm. Jellyfish implements a projected incremental gradient method with a biased, random ordering of the increments. This biased ordering allows for a parallel implementation that admits a speed-up nearly proportional to the number of processors. On large-scale matrix completion tasks, Jellyfish is orders of magnitude more efficient than existing codes. For example, on the Netflix Prize data set, prior art computes rating predictions in approximately 4 h, while Jellyfish solves the same problem in under 3 min on a 12 core workstation.

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity.We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30–75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.

The time dependent traveling salesman problem (TDTSP) is a generalization of the classical traveling salesman problem (TSP), where arc costs depend on their position in the tour with respect to the source node. While TSP instances with thousands of vertices can be solved routinely, there are very challenging TDTSP instances with less than 100 vertices. In this work, we study the polytope associated to the TDTSP formulation by Picard and Queyranne, which can be viewed as an extended formulation of the TSP.We determine the dimension of the TDTSP polytope and identify several families of facet-defining cuts.We obtain good computational results with a branch-cut-and-price algorithm using the new cuts, solving almost all instances from the TSPLIB with up to 107 vertices.

This paper describes implementation and computational results of a polynomial test of total unimodularity. The test is a simplified version of a prior method. The program also decides two related unimodularity properties. The software is available free of charge in source code form under the Boost Software License.

We report and analyze the results of our computational testing of branchand-cut for piecewise linear optimization using the cutting planes given recently by Zhao and de Farias. Besides evaluating the performance of the cuts, we evaluate the effect of formulation on the performance of branch-and-cut. Finally, we report and analyze results on piecewise linear optimization problems with semi-continuous constraints.