\texttt{EXPEDIS}: an exact penalty method over discrete sets

DOI10.1016/J.DISOPT.2021.100622MaRDI QIDQ2673244zbMATH OpenOpenAlexFDO

Authors Nicolò Gusmeroli, Angelika Wiegele

Publication date 9 June 2022

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.09739

zbMATH Keywords

branch-and-boundcombinatorial optimizationexact penalty methodquadratic programmingsemidefinite programming

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• An exact penalty approach for solving a class of minimization problems with boolean variables
• An Exact Penalty Approach to the Quadratic Assignment Problem
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Penalty parameter for linearly constrained 0--1 quadratic programming
• An exact penalty function approach for nonlinear integer programming problems

Cites work

• A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A MAX-CUT formulation of 0/1 programs
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• An exact algorithm for nonconvex quadratic integer minimization using ellipsoidal relaxations
• BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
• Branching and bounds tighteningtechniques for non-convex MINLP
• Combinatorial optimization: the interplay of graph theory, linear and integer programming illustrated on network flow
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Gap inequalities for the cut polytope
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Handbook on semidefinite, conic and polynomial optimization
• scientific article; zbMATH DE number 4070633 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On the solution of nonconvex cardinality Boolean quadratic programming problems: a computational study
• Optimizing a polyhedral-semidefinite relaxation of completely positive programs
• Semidefinite relaxations for non-convex quadratic mixed-integer programming
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• The unconstrained binary quadratic programming problem: a survey
• Using a conic bundle method to accelerate both phases of a quadratic convex reformulation

Cited in

(5)

• BiqBin: A Parallel Branch-and-bound Solver for Binary Quadratic Problems with Linear Constraints
• Solving SDP relaxations of max-cut problem with large number of hypermetric inequalities by L-BFGS-B
• EXPEDIS: An Exact Penalty Method over Discrete Sets
• On the numerical solution of Lasserre relaxations of unconstrained binary quadratic optimization problem
• Edge expansion of a graph: SDP-based computational strategies

Describes a project that uses

Uses Software

• CPLEX
• SCIP
• Gurobi
• Biq Mac
• MIQCR-CB
• BiqCrunch

This page was built for publication: \texttt{EXPEDIS}: an exact penalty method over discrete sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2673244)