On generalized surrogate duality in mixed-integer nonlinear programming
From MaRDI portal
Abstract: The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global epsilon-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solver can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate strong dual bounds through extensive computational experiments.
Recommendations
- On generalized surrogate duality in mixed-integer nonlinear programming
- A result in surrogate duality for certain integer programming problems
- Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation
- Convex relaxations for mixed-integer nonlinear programs
- Disjunctive Cuts for Nonconvex MINLP
Cites work
- A global optimization algorithm for linear fractional and bilinear programs
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A surrogate relaxation based algorithm for a general quadratic multi- dimensional knapsack problem
- An Aggregate Constraint Method for Non-Linear Programming
- AN IMPROVED SURROGATE CONSTRAINTS METHOD FOR SEPARABLE NONLINEAR INTEGER PROGRAMMING
- bliss
- Calculating surrogate constraints
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
- Discrete Programming by the Filter Method
- Disjunctive programming: Properties of the convex hull of feasible points
- Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
- Enhancing RLT relaxations via a new class of semidefinite cuts
- Exact algorithm for the surrogate dual of an integer programming problem: Subgradient method approach
- scientific article; zbMATH DE number 4072712 (Why is no real title available?)
- scientific article; zbMATH DE number 914364 (Why is no real title available?)
- scientific article; zbMATH DE number 7124428 (Why is no real title available?)
- Inexact stabilized Benders' decomposition approaches with application to chance-constrained problems with finite support
- Lagrangean/surrogate relaxation for generalized assignment problems
- Mixed integer programming: analyzing 12 years of progress
- On mathematical programming with indicator constraints
- On the choice of explicit stabilizing terms in column generation
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
- SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework
- SCIP: solving constraint integer programs
- Small and strong formulations for unions of convex sets from the Cayley embedding
- Some relationships between lagrangian and surrogate duality in integer programming
- Stabilized column generation
- Surrogate Constraint Duality in Mathematical Programming
- Surrogate Constraints
- Surrogate Dual Multiplier Search Procedures in Integer Programming
- Surrogate duality relaxation for job shop scheduling
- Surrogate Mathematical Programming
- The Cutting-Plane Method for Solving Convex Programs
- Trust Region Methods
- Tutorial on surrogate constraint approaches for optimization in graphs
- Zero duality gap in surrogate constraint optimization: a concise review of models
Cited in
(7)- On generalized surrogate duality in mixed-integer nonlinear programming
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- scientific article; zbMATH DE number 4039640 (Why is no real title available?)
- On obtaining the convex hull of quadratic inequalities via aggregations
- Aggregations of Quadratic Inequalities and Hidden Hyperplane Convexity
- Tighter relaxations in mixed-integer nonlinear programming
- A topological approach to simple descriptions of convex hulls of sets defined by three quadrics
This page was built for publication: On generalized surrogate duality in mixed-integer nonlinear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041755)
