Relaxations and cutting planes for linear programs with complementarity constraints

DOI10.1007/S10898-024-01397-XMaRDI QIDQ6607018zbMATH OpenFDO

Authors Alberto Del Pia, Jeff Linderoth, Haoran Zhu

Publication date 17 September 2024

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10898-024-01397-X

zbMATH Keywords

Boolean quadric polytopecomplementarity constraintsconvex hullcutting-planesdisjunctive programming

Mathematics Subject Classification ID

Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Recommendations

• Obtaining tighter relaxations of mathematical programs with complementarity constraints
• Convexification techniques for linear complementarity constraints
• Solving linear programs with complementarity constraints using branch-and-cut
• Branch-and-cut for complementarity and cardinality constrained linear programs
• Convexification techniques for linear complementarity constraints

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A polyhedral study of the cardinality constrained knapsack problem
• A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints
• APPROXIMATE ALGORITHMS FOR THE MULTIPLE-CHOICE CONTINUOUS KNAPSACK PROBLEMS
• Branch-and-cut for combinatorial optimisation problems without auxiliary binary variables
• Branch-and-cut for complementarity-constrained optimization
• Branch-and-cut for linear programs with overlapping SOS1 constraints
• Conflict graphs in solving integer programming problems
• Convexification techniques for linear complementarity constraints
• Cover by disjoint cliques cuts for the knapsack problem with conflicting items
• Cutting-Planes for Complementarity Constraints
• Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
• Disjunctive programming: Properties of the convex hull of feasible points
• Engineering and Economic Applications of Complementarity Problems
• Enhanced intersection cutting-plane approach for linear complementarity problems
• Enumeration of the facets of cut polytopes over some highly symmetric graphs
• Facets of the Complementarity Knapsack Polytope
• scientific article; zbMATH DE number 1944141 (Why is no real title available?)
• Integer Programming
• Intersection Cuts—A New Type of Cutting Planes for Integer Programming
• New classes of facets for complementarity knapsack problems
• On linear programs with linear complementarity constraints
• On the facial structure of set packing polyhedra
• On the Global Solution of Linear Programs with Linear Complementarity Constraints
• Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem
• Simultaneous convexification of bilinear functions over polytopes with application to network interdiction
• Technical Note—The Use of Cuts in Complementary Programming
• The bipartite Boolean quadric polytope
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The Knapsack Problem with Conflict Graphs
• The mixed vertex packing problem.
• THE MULTIPLE-CHOICE KNAPSACK PROBLEM
• Transportation problem with nonlinear side constraints a branch and bound approach
• Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph

Cited in

(1)

• Simultaneous convexification for the planar obnoxious facility location problem

This page was built for publication: Relaxations and cutting planes for linear programs with complementarity constraints

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