MPC 2018, ISSUE 4
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Cubic regularization in symmetric rank-1 quasi-Newton methods
Hande Y. Benson, David F. Shanno
Quasi-Newton methods based on the symmetric rank-one (SR1) update have been known to be fast and provide better approximations of the true Hessian than popular rank-two approaches, but these properties are guaranteed under certain conditions which frequently do not hold. Additionally, SR1 is plagued by the lack of guarantee of positive definiteness for the Hessian estimate. In this paper, we propose cubic regularization as a remedy to relax the conditions on the proofs of convergence for both speed and accuracy and to provide a positive definite approximation at each step. We show that the n-step convergence property for strictly convex quadratic programs is retained by the proposed approach. Extensive numerical results on unconstrained problems from the CUTEr test set are provided to demonstrate the computational efficiency and robustness of the approach.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
Daniel Juhl, David M. Warme, Pawel Winter, Martin Zachariasen
The GeoSteiner software package has for about 20 years been the fastest (publicly available) program for computing exact solutions to Steiner tree problems in the plane. The computational study by Warme, Winter and Zachariasen, published in 2000, documented the performance of the GeoSteiner approach—allowing the exact solution of Steiner tree problems with more than a thousand terminals. Since then, a number of algorithmic enhancements have improved the performance of the software package significantly. We describe these (previously unpublished) enhancements, and present a new computational study wherein we run the current code on the largest problem instances from the 2000-study, and on a number of larger problem instances. The computational study is performed using the commercial GeoSteiner 4.0 code base, and the performance is compared to the publicly available GeoSteiner 3.1 code base as well as the code base from the 2000-study. The software studied in the paper is being released as GeoSteiner 5.0 under an open source license.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming
Yunhai Xiao, Liang Chen, Donghui Li
In this paper, we propose a generalized alternating direction method of multipliers (ADMM) with semi-proximal terms for solving a class of convex composite conic optimization problems, of which some are high-dimensional, to moderate accuracy. Our primary motivation is that this method, together with properly chosen semi-proximal terms, such as those generated by the recent advance of block symmetric Gauss–Seidel technique, is capable of tackling these problems. Moreover, the proposed method, which relaxes both the primal and the dual variables in a natural way with a common relaxation factor in the interval of (0, 2), has the potential of enhancing the performance of the classic ADMM. Extensive numerical experiments on various doubly non-negative semidefinite programming problems, with or without inequality constraints, are conducted. The corresponding results showed that all these multi-block problems can be successively solved, and the advantage of using the relaxation step is apparent.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Matrix minor reformulation and SOCP-based spatial branch-and-cut method for the AC optimal power flow problem
Burak Kocuk, Santanu S. Dey, X. Andy Sun
Alternating current optimal power flow (AC OPF) is one of the most fundamental optimization problems in electrical power systems. It can be formulated as a semidefinite program (SDP) with rank constraints. Solving AC OPF, that is, obtaining near optimal primal solutions as well as high quality dual bounds for this non-convex program, presents a major computational challenge to today’s power industry for the real-time operation of large-scale power grids. In this paper, we propose a new technique for reformulation of the rank constraints using both principal and non-principal 2-by-2 minors of the involved Hermitian matrix variable and characterize all such minors into three types. We show the equivalence of these minor constraints to the physical constraints of voltage angle differences summing to zero over three- and four-cycles in the power network. We study second-order conic programming (SOCP) relaxations of this minor reformulation and propose strong cutting planes, convex envelopes, and bound tightening techniques to strengthen the resulting SOCP relaxations. We then propose an SOCP-based spatial branch-and-cut method to obtain the global optimum of AC OPF. Extensive computational experiments show that the proposed algorithm significantly outperforms the state-of-the-art SDP-based OPF solver and on a simple personal computer is able to obtain on average a 0.71% optimality gap in no more than 720 s for the most challenging power system instances in the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
RBFOpt: an open-source library for black-box optimization with costly function evaluations
Alberto Costa, Giacomo Nannicini
We consider the problem of optimizing an unknown function given as an oracle over a mixed-integer box-constrained set. We assume that the oracle is expensive to evaluate, so that estimating partial derivatives by finite differences is impractical. In the literature, this is typically called a black-box optimization problem with costly evaluation. This paper describes the solution methodology implemented in the open-source library RBFOpt, available on COIN-OR. The algorithm is based on the Radial Basis Function method originally proposed by Gutmann (J Glob Optim 19:201–227, 2001. https://doi.org/10.1023/A:1011255519438), which builds and iteratively refines a surrogate model of the unknown objective function. The two main methodological contributions of this paper are an approach to exploit a noisy but less expensive oracle to accelerate convergence to the optimum of the exact oracle, and the introduction of an automatic model selection phase during the optimization process. Numerical experiments show that RBFOpt is highly competitive on a test set of continuous and mixed-integer nonlinear unconstrained problems taken from the literature: it outperforms the open-source solvers included in our comparison by a large amount, and performs slightly better than a commercial solver. Our empirical evaluation provides insight on which parameterizations of the algorithm are the most effective in practice. The software reviewed as part of this submission was given the Digital Object Identifier (DOI) https://doi.org/10.5281/zenodo.597767.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
ADMM for the SDP relaxation of the QAP
Danilo Elias Oliveira, Henry Wolkowicz, Yangyang Xu
Semidefinite programming, SDP, relaxations have proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem, QAP, arguably one of the hardest NP-hard discrete optimization problems. There are several difficulties that arise in efficiently solving the SDP relaxation, e.g., increased dimension; inefficiency of the current primal–dual interior point solvers in terms of both time and accuracy; and difficulty and high expense in adding cutting plane constraints. We propose using the alternating direction method of multipliers ADMM in combination with facial reduction, FR, to solve the SDP relaxation. This first order approach allows for: inexpensive iterations, a method of cheaply obtaining low rank solutions; and a trivial way of exploiting the FR for adding cutting plane inequalities. In fact, we solve the doubly nonnegative, DNN, relaxation that includes both the SDP and all the nonnegativity constraints. When compared to current approaches and current best available bounds we obtain robustness, efficiency and improved bounds.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
Learning customized and optimized lists of rules with mathematical programming
Cynthia Rudin, Seyda Ertekin
We introduce a mathematical programming approach to building rule lists, which are a type of interpretable, nonlinear, and logical machine learning classifier involving IF-THEN rules. Unlike traditional decision tree algorithms like CART and C5.0, this method does not use greedy splitting and pruning. Instead, it aims to fully optimize a combination of accuracy and sparsity, obeying user-defined constraints. This method is useful for producing non-black-box predictive models, and has the benefit of a clear user-defined tradeoff between training accuracy and sparsity. The flexible framework of mathematical programming allows users to create customized models with a provable guarantee of optimality. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) https://doi.org/10.5281/zenodo.1344142.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 4, December 2018
QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
Xudong Li, Defeng Sun, Kim-Chuan Toh
In this paper, we present a two-phase augmented Lagrangian method, called QSDPNAL, for solving convex quadratic semidefinite programming (QSDP) problems with constraints consisting of a large number of linear equality and inequality constraints, a simple convex polyhedral set constraint, and a positive semidefinite cone constraint. A first order algorithm which relies on the inexact Schur complement based decomposition technique is developed in QSDPNAL-Phase I with the aim of solving a QSDP problem to moderate accuracy or using it to generate a reasonably good initial point for the second phase. In QSDPNAL-Phase II, we design an augmented Lagrangian method (ALM) wherein the inner subproblem in each iteration is solved via inexact semismooth Newton based algorithms. Simple and implementable stopping criteria are designed for the ALM. Moreover, under mild conditions, we are able to establish the rate of convergence of the proposed algorithm and prove the R-(super)linear convergence of the KKT residual. In the implementation of QSDPNAL, we also develop efficient techniques for solving large scale linear systems of equations under certain subspace constraints. More specifically, simpler and yet better conditioned linear systems are carefully designed to replace the original linear systems and novel shadow sequences are constructed to alleviate the numerical difficulties brought about by the crucial subspace constraints. Extensive numerical results for various large scale QSDPs show that our two-phase algorithm is highly efficient and robust in obtaining accurate solutions. The software reviewed as part of this submission was given the DOI (Digital Object Identifier) https://doi.org/10.5281/zenodo.1206980.
Full Text: PDF
MPC 2018, ISSUE 3
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
Asynchronously parallel optimization solver for finding multiple minima
Jeffrey Larson, Stefan M. Wild
We propose and analyze an asynchronously parallel optimization algorithmfor finding multiple, high-quality minima of nonlinear optimization problems. Ourmultistart algorithm considers all previously evaluated points when determining where to start or continue a local optimization run. Theoretical results show that when there are finitely many minima, the algorithm almost surely starts a finite number of local optimization runs and identifies every minimum. The algorithm is applicable to general optimization settings, but our numerical results focus on the case when derivatives are unavailable. In numerical tests, a Python implementation of the algorithm is shown to yield good approximations of many minima (including a global minimum), and this ability is shown to scale well with additional resources. Our implementation’s time to solution is shown also to scale well even when the time to perform the function evaluation is highly variable. An implementation of the algorithm is available in the libEnsemble library at https://github.com/Libensemble/libensemble.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods
Pierre Bonami, Oktay Günlük, Jeff Linderoth
We present effective linear programming based computational techniquesfor solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
A hybrid LP/NLP paradigm for global optimization relaxations
Aida Khajavirad, Nikolaos V. Sahinidis
Polyhedral relaxations have been incorporated in a variety of solvers for theglobal optimization of mixed-integer nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the branch-and-bound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 3, September 2018
Intersection cuts for single row corner relaxations
Ricardo Fukasawa, Laurent Poirrier, Álinson S. Xavier
We consider the problem of generating inequalities that are valid for one-row relaxations of a simplex tableau, with the integrality constraints preserved for one or more non-basic variables. These relaxations are interesting because they can be used to generate cutting planes for general mixed-integer problems. We first consider the case of a single non-basic integer variable. This relaxation is related to a simple knapsack set with two integer variables and two continuous variables. We study its facial structure by rewriting it as a constrained two-row model, and prove that all its facets arise from a finite number of maximal (Z × Z + )-free splits and wedges. The resulting cuts generalize both MIR and 2-step MIR inequalities. Then, we describe an algorithm for enumerating all the maximal (Z × Z + )-free sets corresponding to facet-defining inequalities, and we provide an upper bound on the split rank of those inequalities. Finally, we run computational experiments to compare the strength of wedge cuts against MIR cuts. In our computations, we use the so-called trivial fill-in function to exploit the integrality of more non-basic variables. To that end, we present a practical algorithm for computing the coefficients of this lifting function.
Full Text: PDF
MPC 2018, ISSUE 2
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
Detecting almost symmetries of graphs
Ben Knueven, Jim Ostrowski, Sebastian Pokutta
We present a branch-and-bound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that minimizes the number of vertex orbits. We call the symmetries on such a subgraph “almost symmetries” of G. We implement our branch-and-bound framework in PEBBL to allow for parallel enumeration and demonstrate good scaling up to 16 cores. We show that the presented branching strategy is much better than a random branching strategy on the tested graphs. Finally, we consider the presented strategy as a heuristic for quickly finding almost symmetries of a graph G. The software that was reviewed as part of this submission has been issued the Digital Object Identifier DOI:10.5281/zenodo.840558.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
pyomo.dae: a modeling and automatic discretization framework for optimization with differential and algebraic equations
Bethany Nicholson, John D. Siirola, Jean-Paul Watson, Victor M. Zavala, Lorenz T. Biegler
We describe pyomo.dae, an open source Python-based modeling framework that enables high-level abstract specification of optimization problems with differential and algebraic equations. The pyomo.dae framework is integrated with the Pyomo open source algebraic modeling language, and is available at http://www. pyomo.org. One key feature of pyomo.dae is that it does not restrict users to stan- dard, predefined forms of differential equations, providing a high degree of modeling flexibility and the ability to express constraints that cannot be easily specified in other modeling frameworks. Other key features of pyomo.dae are the ability to specify optimization problems with high-order differential equations and partial differential equations, defined on restricted domain types, and the ability to automatically trans- form high-level abstract models into finite-dimensional algebraic problems that can be solved with off-the-shelf solvers. Moreover, pyomo.dae users can leverage existing capabilities of Pyomo to embed differential equation models within stochastic and integer programming models and mathematical programs with equilibrium constraint formulations. Collectively, these features enable the exploration of new modeling con- cepts, discretization schemes, and the benchmarking of state-of-the-art optimization solvers.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
Algorithmic innovations and software for the dual decomposition method applied to stochastic mixed-integer programs
Kibaek Kim, Victor M. Zavala
We present algorithmic innovations for the dual decomposition method to address two-stage stochastic programs with mixed-integer recourse and provide an open-source software implementation that we call DSP. Our innovations include the incorporation of Benders-like cuts in a dual decomposition framework to tighten Lagrangian subproblems and aid the exclusion of infeasible first-stage solutions for problems without (relative) complete recourse. We also use an interior-point cutting- plane method with new termination criteria for solving the Lagrangian master problem. We prove that the algorithm converges to an optimal solution of the Lagrangian dual problem in a finite number of iterations, and we also prove that convergence can be achieved even if the master problem is solved suboptimally. DSP can solve instances specified in C code, SMPS files, and Julia script. DSP also implements a standard Benders decomposition method and a dual decomposition method based on subgradi- ent dual updates that we use to perform benchmarks. We present extensive numerical results using SIPLIB instances and a large unit commitment problem to demonstrate that the proposed innovations provide significant improvements in the number of iter- ations and solution times. The software reviewed as part of this submission has been given the Digital Object Identifier (DOI) https://doi.org/10.5281/zenodo.998971.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 2, June 2018
mplrs: A scalable parallel vertex/facet enumeration code
David Avis, Charles Jordan
We describe a new parallel implementation, mplrs, of the vertex enumer- ation code lrs that uses the MPI parallel environment and can be run on a network of computers. The implementation makes use of a C wrapper that essentially uses the existing lrs code with only minor modifications. mplrs was derived from the earlier parallel implementation plrs, written by G. Roumanis in C++ which runs on a shared memory machine. By improving load balancing we are able to greatly improve performance for medium to large scale parallelization of lrs. We report computational results comparing parallel and sequential codes for vertex/facet enu- meration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. For most problems tested, the results clearly show the advantage of using the parallel implementation mplrs of the reverse search based code lrs, even when as few as 8 cores are available. For some problems almost linear speedup was observed up to 1200 cores, the largest number of cores tested. The software that was reviewed as part of this submission is included in lrslib-062.tar.gz which has MD5 hash be5da7b3b90cc2be628dcade90c5d 1b9.
Full Text: PDF
MPC 2018, ISSUE 1
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
Sparse-BSOS: a bounded degree SOS hierarchy for large scale polynomial optimization with sparsity
Tillmann Weisser, Jean B. Lasserre, Kim-Chuan Toh
We provide a sparse version of the bounded degree SOS hierarchy BSOS (Lasserre et al. in EURO J Comp Optim:87–117, 2017) for polynomial optimization problems. It permits to treat large scale problems which satisfy a structured sparsity pattern. When the sparsity pattern satisfies the running intersection property this Sparse-BSOS hierarchy of semidefinite programs (with semidefinite constraints of fixed size) converges to the global optimum of the original problem.Moreover, for the class of SOS-convex problems, finite convergence takes place at the first step of the hierarchy, just as in the dense version.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
Branch-and-cut for linear programs with overlapping SOS1 constraints
Tobias Fischer, Marc E. Pfetsch
SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, preprocessing, primal heuristics, and cutting planes. In an extensive computational study, we evaluate the components of our implementation on instances for three different applications. We also demonstrate the effectiveness of this approach by comparing it to the solution of a mixedinteger programming formulation, if the variables appearing in SOS1 constraints arbounded.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
A robust and scalable algorithm for the Steiner problem in graphs
Thomas Pajor, Eduardo Uchoa, Renato F. Werneck
We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recently-proposed fast local searches. We also propose a fast implementation of a well-known dual ascent algorithm that not only makes our heuristics more robust (by dealing with easier cases quickly), but can also be used as a building block of an exact branch-and-bound algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.
Full Text: PDF
Mathematical Programming Computation, Volume 10, Issue 1, March 2018
Parallelizing the dual revised simplex method
Q. Huangfu, J. A. J. Hall
This paper introduces the design and implementation of two parallel dual simplex solvers for general large scale sparse linear programming problems. One approach, called PAMI, extends a relatively unknown pivoting strategy called suboptimization and exploits parallelism across multiple iterations. The other, called SIP, exploits purely single iteration parallelism by overlapping computational components when possible. Computational results show that the performance of PAMI is superior to that of the leading open-source simplex solver, and that SIP complements PAMI in achieving speedup when PAMI results in slowdown. One of the authors has implemented the techniques underlying PAMI within the FICO Xpress simplex solver and this paper presents computational results demonstrating their value. In developing the first parallel revised simplex solver of general utility, this work represents a significant achievement in computational optimization.
Full Text: PDF
Imprint and privacy statement
For the imprint and privacy statement we refer to the Imprint of ZIB.
© 2008-2024 by Zuse Institute Berlin (ZIB).