Undercover: a primal MINLP heuristic exploring a largest sub-MIP

DOI10.1007/s10107-013-0635-2zbMath1291.90144OpenAlexW2048251068MaRDI QIDQ2452383

Ambros M. Gleixner, Timo Berthold

Publication date: 2 June 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-013-0635-2

zbMATH Keywords

nonconvex optimizationlarge neighborhood searchmixed-integer nonlinear programmingprimal heuristicmixed-integer quadratically constrained programming

Mathematics Subject Classification ID

Mixed integer programming (90C11) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Quadratic programming (90C20) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Three ideas for a feasibility pump for nonconvex MINLP, Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Inexact feasibility pump for mixed integer nonlinear programming, A storm of feasibility pumps for nonconvex MINLP, A feasible rounding approach for mixed-integer optimization problems, A partial outer convexification approach to control transmission lines, Feasible rounding based diving strategies in branch-and-bound methods for mixed-integer optimization, SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework, Computing feasible points for binary MINLPs with MPECs, Generating Feasible Points for Mixed-Integer Convex Optimization Problems by Inner Parallel Cuts, A computational study of primal heuristics inside an MI(NL)P solver, A primal heuristic for optimizing the topology of gas networks based on dual information, Experiments with conflict analysis in mixed integer programming, RENS. The optimal rounding, Granularity in nonlinear mixed-integer optimization, Computational aspects of infeasibility analysis in mixed integer programming, Generalized relax-and-fix heuristic, Deterministic upper bounds for spatial branch-and-bound methods in global minimization with nonconvex constraints

Uses Software

• SCIP
• CPLEX
• LINDO
• Bonmin
• MINLP
• FEASPUMP
• Ipopt
• CppAD
• MINLPLib
• LINDOGlobal
• SBB
• GloMIQO
• MINOTAUR
• Chaff
• DINS

Cites Work

• Unnamed Item
• Unnamed Item
• GLOMIQO: global mixed-integer quadratic optimizer
• A recipe for finding good solutions to MINLPs
• Heuristics for convex mixed integer nonlinear programs
• SCIP: solving constraint integer programs
• RENS. The optimal rounding
• On the hardness of approximating minimum vertex cover
• An algorithmic framework for convex mixed integer nonlinear programs
• A feasibility pump for mixed integer nonlinear programs
• Feasibility pump 2.0
• Reduction of indefinite quadratic programs to bilinear programs
• Local branching
• Rounding-based heuristics for nonconvex MINLPS
• Exploring relaxation induced neighborhoods to improve MIP solutions
• Global optimization of mixed-integer nonlinear programs: a theoretical and computational study
• Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations
• Conflict analysis in mixed integer programming
• Improving the feasibility pump
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• The feasibility pump
• MINLPLib—A Collection of Test Models for Mixed-Integer Nonlinear Programming
• Extending a CIP Framework to Solve MIQCPs
• A better approximation ratio for the vertex cover problem
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• An Automatic Method of Solving Discrete Programming Problems
• Branching and bounds tighteningtechniques for non-convex MINLP
• The global solver in the LINDO API
• Evaluating Derivatives
• A cutting plane algorithm for solving bilinear programs
• DINS, a MIP Improvement Heuristic