Mathematical Programming Models and Exact Algorithms

DOI10.1007/978-3-031-04520-2_6zbMath1506.90198OpenAlexW4285026753MaRDI QIDQ5050146

Abraham P. Punnen, Renata Sotirov

Publication date: 15 November 2022

Published in: The Quadratic Unconstrained Binary Optimization Problem (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-04520-2_6

zbMATH Keywords

mixed integer linear programming formulationssemidefinite programming approaches

Mathematics Subject Classification ID

Semidefinite programming (90C22) Mixed integer programming (90C11) Quadratic programming (90C20) Boolean programming (90C09)

Uses Software

• SCIP
• CPLEX
• Gurobi
• Biq Mac
• SDPNAL+
• BiqCrunch

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• An exact solution method for unconstrained quadratic 0--1 programming: a geometric approach
• Solving VLSI design and DNA sequencing problems using bipartization of graphs
• The indefinite zero-one quadratic problem
• An improved enumerative algorithm for solving quadratic zero-one programming
• Handbook on semidefinite, conic and polynomial optimization
• The maximum \(k\)-colorable subgraph problem and orbitopes
• An improved linearization technique for a class of quadratic 0-1 programming problems
• A new linearization technique for multi-quadratic 0-1 programming problems.
• SCIP: solving constraint integer programs
• Computational comparison of exact solution methods for 0-1 quadratic programs: recommendations for practitioners
• A maximum edge-weight clique extraction algorithm based on branch-and-bound
• Unconstrained quadratic bivalent programming problem
• A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• Bounds for the quadratic assignment problem using the bundle method
• Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
• Upper-bounds for quadratic 0-1 maximization
• Analyzing quadratic unconstrained binary optimization problems via multicommodity flows
• A linearization framework for unconstrained quadratic (0-1) problems
• Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
• A global continuation algorithm for solving binary quadratic programming problems
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Geometric algorithms and combinatorial optimization
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• On the equivalence between roof duality and Lagrangian duality for unconstrained \(0\)-\(1\) quadratic programming problems
• Laplacian eigenvalues and the maximum cut problem
• Connection between semidefinite relaxations of the max-cut and stable set problems
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems
• ADMM for the SDP relaxation of the QAP
• On the Lovász theta function and some variants
• Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem
• Seizure warning algorithm based on optimization and nonlinear dynamics
• A MAX-CUT formulation of 0/1 programs
• A simple recipe for concise mixed 0-1 linearizations
• Application of cut polyhedra. I
• Applications of cut polyhedra. II
• On a positive semidefinite relaxation of the cut polytope
• A branch-and-cut method for 0-1 mixed convex programming
• \texttt{MADAM}: a parallel exact solver for max-cut based on semidefinite programming and ADMM
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
• Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Compact linearization for binary quadratic problems
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems
• The spectral bundle method with second-order information
• Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry
• BiqCrunch
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• On the Significance of Solving Linear Programming Problems with Some Integer Variables
• Technical Note—Linearization in 0-1 Variables: A Clarification
• An algorithm for quadratic zero-one programs
• Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations
• Roof duality, complementation and persistency in quadratic 0–1 optimization
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• A comparison of the Delsarte and Lovász bounds
• A Linearization Procedure for Quadratic and Cubic Mixed-Integer Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Computational Experience with Stable Set Relaxations
• A Spectral Bundle Method for Semidefinite Programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Nonpolyhedral Relaxations of Graph-Bisection Problems
• A Decomposition Method for Quadratic Zero-One Programming
• Base-2 Expansions for Linearizing Products of Functions of Discrete Variables
• Fixing Variables in Semidefinite Relaxations
• SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
• The Maximum k-Colorable Subgraph Problem and Related Problems
• The Generalized Lattice-Point Problem
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Solving Lift-and-Project Relaxations of Binary Integer Programs
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Decomposition and linearization for 0-1 quadratic programming

This page was built for publication: Mathematical Programming Models and Exact Algorithms