Complete formulations of polytopes related to extensions of assignment matrices

DOI10.1016/J.DISOPT.2018.04.002MaRDI QIDQ1662654zbMATH OpenOpenAlexFDO

Authors Walid Ben-Ameur, Antoine Glorieux, José Neto

Publication date 20 August 2018

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2018.04.002

zbMATH Keywords

assignment problemspolytopecompact formulationseparationcomplete formulation

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Special polytopes (linear programming, centrally symmetric, etc.) (52B12)

Recommendations

• A full description of polytopes related to the index of the lowest nonzero row of an assignment matrix
• On the extension complexity of scheduling polytopes
• Extended formulations in combinatorial optimization
• Extended formulations in combinatorial optimization
• On the facial structure of scheduling polyhedra

Cites work

• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Disjunctive programming: Properties of the convex hull of feasible points
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Extended and discretized formulations for the maximum clique problem
• On the most imbalanced orientation of a graph
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(2)

• The k-assignment polytope
• A full description of polytopes related to the index of the lowest nonzero row of an assignment matrix

Describes a project that uses

Uses Software

• PORTA

This page was built for publication: Complete formulations of polytopes related to extensions of assignment matrices

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