The linear programming polytope of binary constraint problems with bounded tree-width

Sellmann, M.;Mercier, L.;Leventhal, D.H.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Sellmann, M.
    Author
  • Mercier, L.
    Author
  • Leventhal, D.H.
    Author
Abstract
We show how to efficiently model binary constraint problems (BCP) as integer programs. After considering tree-structured BCPs first, we show that a Sherali-Adams-like procedure results in a polynomial-size linear programming description of the convex hull of all integer feasible solutions when the BCP that is given has bounded tree-width.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Sellmann, M., Mercier, L., & Leventhal, D. H. (2007). The linear programming polytope of binary constraint problems with bounded tree-width. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 275-287). Springer-verlag. https://hdl.handle.net/2078.5/222307