Decision diagrams have been successfully used to help solve several classes of discrete optimization problems. We explore an approach to incorporate them into integer programming solvers, motivated by the wide adoption of integer programming technology in practice. The main challenge is to map generic integer programming models to a recursive structure that is suitable for decision diagram compilation. We propose a framework that opportunistically constructs decision diagrams for suitable substructures, if present. In particular, we explore the use of a prevalent substructure in integer programming solvers known as the conflict graph, which we show to be amenable to decision diagrams. We use Lagrangian relaxation and constraint propagation to consider constraints that are not represented directly by the substructure. We use the decision diagrams to generate dual and primal bounds to improve the pruning process of the branch-and-bound tree of the solver. Computational results on the independent set problem with side constraints indicate that our approach can provide substantial speedups when conflict graphs are present.

Full Text: PDF

We describe a generalization of the Sums-of-AM/GM-Exponential (SAGE) methodology for relative entropy relaxations of constrained signomial and polynomial optimization problems. Our approach leverages the fact that SAGE certificates conveniently and transparently blend with convex duality, in a way which enables partial dualization of certain structured constraints. This more general approach retains key properties of ordinary SAGE relaxations (e.g. sparsity preservation), and inspires a projective method of solution recovery which respects partial dualization. We illustrate the utility of our methodology with a range of examples from the global optimization literature, along with a publicly available software package.

Full Text: PDF.

A Publisher Correction to this article was published on 09 February 2021

In the original publication of the article, the reference list in the pdf version has been published with an error. The correct reference list is given in this correction.
The original article has been updated.

Full Text: PDF

AuthorsWe present a flexible framework for general mixed-integer nonlinear programming (MINLP), called Minotaur, that enables both algorithm exploration and structure exploitation without compromising computational efficiency. This paper documents the concepts and classes in our framework and shows that our implementations of standard MINLP techniques are efficient compared with other state-of-the-art solvers. We then describe structure-exploiting extensions that we implement in our framework and demonstrate their impact on solution times. Without a flexible framework that enables structure exploitation, finding global solutions to difficult nonconvex MINLP problems will remain out of reach for many applications.

Full Text: PDF

The Alternating Direction Method of Multipliers (ADMM) has gained a lot of attention for solving large-scale and objective-separable constrained optimization. However, the two-block variable structure of the ADMM still limits the practical computational efficiency of the method, because one big matrix factorization is needed at least once even for linear and convex quadratic programming. This drawback may be overcome by enforcing a multi-block structure of the decision variables in the original optimization problem. Unfortunately, the multi-block ADMM, with more than two blocks, is not guaranteed to be convergent. On the other hand, two positive developments have been made: first, if in each cyclic loop one randomly permutes the updating order of the multiple blocks, then the method converges in expectation for solving any system of linear equations with any number of blocks. Secondly, such a randomly permuted ADMM also works for equality-constrained convex quadratic programming even when the objective function is not separable. The goal of this paper is twofold. First, we add more randomness into the ADMM by developing a randomly assembled cyclic ADMM (RAC-ADMM) where the decision variables in each block are randomly assembled. We discuss the theoretical properties of RAC-ADMM and show when random assembling helps and when it hurts, and develop a criterion to guarantee that it converges almost surely. Secondly, using the theoretical guidance on RAC-ADMM, we conduct multiple numerical tests on solving both randomly generated and large-scale benchmark quadratic optimization problems, which include continuous, and binary graph-partition and quadratic assignment, and selected machine learning problems. Our numerical tests show that the RAC-ADMM, with a variable-grouping strategy, could significantly improve the computation efficiency on solving most quadratic optimization problems.

Full Text: PDF

We describe the computation of polytope volumes by descent in the face lattice, its implementation in Normaliz, and the connection to reverse-lexicographic triangulations. The efficiency of the algorithm is demonstrated by several high dimensional polytopes of different characteristics. Finally, we present an application to voting theory where polytope volumes appear as probabilities of certain paradoxa.

Full Text: PDF

For the imprint and privacy statement we refer to the Imprint of ZIB.

© 2008-2021 by Zuse Institute Berlin (ZIB).