Advances in Integer Linear Programming and Closure Techniques

Elementary Closures in Nonlinear
Elementary Closures in Nonlinear
Integer Programming
Integer Programming
Daniel Dadush
CWI
Santanu Dey – 
Georgia Tech
Juan Pablo Vielma  – 
MIT
Cutting Planes for Integer Linear
Cutting Planes for Integer Linear
Programs
Programs
Mixed and Non Linear Models?
Mixed and Non Linear Models?
Convex Integer Programming
Convex Integer Programming
Chvátal-Gomory (CG) Cuts
Chvátal-Gomory (CG) Cuts
Chvátal-Gomory Closure
Chvátal-Gomory Closure
Chvátal-Gomory Closure
Chvátal-Gomory Closure
Chvátal-Gomory Closure
Chvátal-Gomory Closure
Split Cuts
Split Cuts
Split Cuts
Split Cuts
Split Closure
Split Closure
Split Closure
Split Closure
Split Closure
Split Closure
Generating the CG Closure
Generating the CG Closure
Generating the CG Closure
Generating the CG Closure
Generating the CG Closure
Generating the CG Closure
Generating the CG Closure
Generating the CG Closure
Generating the Split Closure
Generating the Split Closure
Generating the Split Closure
Generating the Split Closure
Generating the Split Closure
Generating the Split Closure
Non Polyhedral Split Closure
Non Polyhedral Split Closure
D., Dey, Vielma 11
Theorem:
The split closure
of an ellipsoid can
be non polyhedral.
Generating the CG Closure
Generating the CG Closure
Generating the Split Closure
Generating the Split Closure
Generating the CG Closure
Generating the CG Closure
Thin Convex Sets
Thin Convex Sets
Thin
Not Thin
Thin Convex Sets
Thin Convex Sets
Totally Closed Sets
Totally Closed Sets
Not Totally 
Closed
Totally 
Closed
Totally Closed Sets
Totally Closed Sets
Thin &
Totally Closed
Totally Closed Sets
Totally Closed Sets
Building the CG Closure
Building the CG Closure
 
Most difficult step (trivial for rational polytopes). Need
tools from Convex Analysis and Geometry of Numbers.
Building the CG Closure
Building the CG Closure
Building the CG Closure
Building the CG Closure
 
All remaining cuts have
bounded norm.
Lifting CG cuts
Lifting CG cuts
Removing Irrational Parts
Removing Irrational Parts
 
Rational Polytope
Removing Irrational Parts
Removing Irrational Parts
Kronecker’s Approximation Theorem
Fractional part is dense.
Removing Irrational Parts
Removing Irrational Parts
Removing Irrational Parts
Removing Irrational Parts
Extending to General Convex Sets
Extending to General Convex Sets
Main Technical Issues
:
1.
Can only build CG cuts in integer directions where the
objective value is finite.
     (need thinness and rational polyhedral recession cone)
2.
To lift CG cuts from faces must show fine continuity
properties of the objective function.
     (need total closedness)
 
Is the split closure of a compact convex set
finitely generated?
Thank You!
Thank You!
Slide Note
Embed
Share

Explore cutting planes, convex integer programming, Chvátal-Gomory cuts, and closure methods in nonlinear integer programming. Discover how these techniques enhance the efficiency and effectiveness of integer programming models, leading to substantial progress and improved solutions.


Uploaded on Aug 01, 2024 | 1 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Elementary Closures in Nonlinear Integer Programming Daniel Dadush CWI Santanu Dey Georgia Tech Juan Pablo Vielma MIT

  2. Cutting Planes for Integer Linear Programs min??? s.t. ?? ? ? ? ? (c,A,b rational) ? Cutting plane: valid inequality for integer hull. Use to get tighter relaxations important component in practical solvers. Very well developed theory within ILP..

  3. Mixed and Non Linear Models? min? ?,? s.t. ??(?,?) 0 ? ? ? ?,? ? ? ? Many other important Integer Programming models. Substantial Progress in recent years: Solvers, Complexity, Heuristics, etc. Cutting planes poorly understood, even when objective and constraints are convex.

  4. Convex Integer Programming min? ? s.t. ??? 0 ? ? ? ? (?,?? ? ? ??????) Goal: understand basic behavior for fundamental classes of cutting planes. Issue: most current theory depends heavily on rational linear structure. Plan: Develop stronger / more robust Analytical Tools.

  5. Chvtal-Gomory (CG) Cuts ? ?compact convex ? ? Support function of ?: ??? = max? ? ??,? ? ? For ? ? ?,CG cut: CG ?,? = {?: ?,? ??? }

  6. Chvtal-Gomory Closure ? ?compact convex ?1 CG closure of ?: ?6 CG ? = CG(?,?) ? ?2 ? ? ? ?3 ?5 ?4

  7. Chvtal-Gomory Closure ? ?compact convex ?1 CG closure of ?: ?6 CG ? = CG(?,?) ? ?2 ? ? ? ?3 ?5 ?4

  8. Chvtal-Gomory Closure ? ?compact convex ?1 CG closure of ?: ?6 CG ? = CG(?,?) CG(?) ?2 ? ? ? Chv tal `73: Converge to integer hull after finitely many iterations. ?3 ?5 ?4

  9. Split Cuts ? ?compact convex Elementary disjunction: ? ? ? ? ?? ? ? ? + 1 ? ? ?,? ?

  10. Split Cuts ? ?compact convex Elementary disjunction: ? ? ? ? ?? ? ? ? + 1 ? ? ?,? ? Split Cut: SC ?,?,? = conv(? ? ? ? ? ? ? ? + 1 )

  11. Split Closure ? ?compact convex Split Closure: SC ? = SC(?,?,?) ? ?? ?,??

  12. Split Closure ? ?compact convex Split Closure: CG(?) SC ? = SC(?,?,?) ?? ?,??

  13. Split Closure ? ?compact convex Split Closure: SC(?) SC ? = SC(?,?,?) ?? ?,??

  14. Generating the CG Closure Schrijver 1980 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then CG(?) is finitely generated. ?1 CG ? = CG(?,?) ?4 ? ? ? ? ?2 ?3

  15. Generating the CG Closure Schrijver 1980 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then CG(?) is finitely generated. ?1 CG ? = CG(?,?) ?4 ? ? ? CG(?) ?2 ?3

  16. Generating the CG Closure Schrijver 1980 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then CG(?) is finitely generated. ?1 Question: Is this true in general? ?4 CG(?) ?2 ?3

  17. Generating the CG Closure Schrijver 1980 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then CG(?) is finitely generated. Question: Is this true in general? Not always. 2?1 ?2 .1 ?2 0

  18. Generating the Split Closure Cook, Kannan, Schrijver 1990 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then SC(?) is finitely generated. ?1 SC ? = SC(?,?,?) ?4 ?? ?, ?? ? ?2 ?3

  19. Generating the Split Closure Cook, Kannan, Schrijver 1990 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then SC(?) is finitely generated. ?1 SC ? = SC(?,?,?) ?4 ?? ?, ?? SC(?) ?2 ?3

  20. Generating the Split Closure Cook, Kannan, Schrijver 1990 Theorem: If ? = {? ?:?? ?}is a rational polyhedron, then SC(?) is finitely generated. ?1 Question: ?4 SC(?) Is the Split Closure always polyhedral? ?2 ?3 No.

  21. Non Polyhedral Split Closure D., Dey, Vielma 11 Theorem: The split closure of an ellipsoid can be non polyhedral.

  22. Generating the CG Closure D., Dey, Vielma 11 Theorem: If ? ?is compact convex, then CG(?) is proper and finitely generated. ?1 CG ? = CG(?,?) ? ? ? ?4 ? ?2 ?3

  23. Generating the Split Closure D., Dey, Vielma 11 Theorem: If ? ?is compact strictly convex, then SC(?) is proper and finitely generated. ?1 SC ? = SC(?,?,?) ?? ?, ?? ?4 ? ? is strictly convex if ?? does not contain lines. ?2 ?3

  24. Generating the CG Closure D., Dey, Vielma 13 Theorem: If ? ?is a thin, totally closed convex set with rational polyhedral ???(?), then CG ? is proper and finitely generated. ?1 CG ? = CG(?,?) ? ? ? ?4 ? If ? is closed convex with CG ? proper, non-empty & rational polyhedral then: 1. ? is thin. 2. ???(?) is rational polyhedral. ?3

  25. Thin Convex Sets Definition: Closed convex set ? is thin if ? ??? ? + ??2 for some finite radius ? 0. ? Thin Not Thin

  26. Thin Convex Sets Definition: Closed convex set ? is thin if ? ??? ? + ??2 for some finite radius ? 0. ? Lemma: If ???(?) is polyhedral, then ? is thin for generators cone ?1, ,?? =rec ? , max i [?] max ? ? for some constant M 0. ?,? ?

  27. Totally Closed Sets Definition: A convex set ? ?is totally closed if ProjW(?) is closed for any subspace ? of ?. Not Totally Closed Totally Closed

  28. Totally Closed Sets Definition: A convex set ? ?is totally closed if ProjW(?) is closed for any subspace ? of ?. Thin & Totally Closed

  29. Totally Closed Sets Definition: A convex set ? ?is totally closed if ProjW(?) is closed for any subspace ? of ?. Lemma: If ???(?) is polyhedral, then ? is totally closed for every face ? of ??? ? , the projection of ? onto span(F) is closed.

  30. Building the CG Closure ? ? denotes the partial closure. 1. Achieve Containment: CG ?,? ? ? Most difficult step (trivial for rational polytopes). Need tools from Convex Analysis and Geometry of Numbers.

  31. Building the CG Closure ? ? denotes the partial closure. ?? ?,? ?? 1. Achieve Containment: CG ?,? ? ? 2. Complete the Boundary: CG ?,? ?? ?? ? ?? Only a finite number of faces of ? need fixing. Use induction on each face.

  32. Building the CG Closure ? ? denotes the partial closure. 1. Achieve Containment: CG ?,? ? ? ? ? 2. Complete the Boundary: CG ?,? ?? ?? ? ?? ? ? ? 3. Complete the Closure: Add all cuts separating a vertex of CG(?,?). All remaining cuts have bounded norm.

  33. Lifting CG cuts D., Dey, Vielma 11 Theorem: Let ? be an exposed face of ?. Then CG ? = CG ? ?. ? ? Goal: Lift CG(?,?) to ?. ? ? ? Find ? : CG(?,?) = CG(?,? ) 1. on rational part of ?. 2. Remove irrational parts of ? using additional CG cuts. ?? ?

  34. Removing Irrational Parts Since ? is an irrational line segment, a rational polytope contained in ? can only intersect ? at 0. Need CG cuts that remove irrational parts of ?. (3 2,2 3) Rational Polytope 0 ? ? ?

  35. Removing Irrational Parts Kronecker s Approximation Theorem Fractional part is dense. (3 2,2 3) 0 ? ? ?

  36. Removing Irrational Parts 3 2 Integers close to ( nearly same inequality for K. 3) line give 2, (3 2,2 3) 0 ? ? ?

  37. Removing Irrational Parts Use density to find close cuts biased towards opposite sides of ?. Cuts remove irrational parts of ?. (3 2,2 3) 0 ? ? ?

  38. Extending to General Convex Sets Main Technical Issues: 1. Can only build CG cuts in integer directions where the objective value is finite. (need thinness and rational polyhedral recession cone) 2. To lift CG cuts from faces must show fine continuity properties of the objective function. (need total closedness)

  39. Open Question Is the split closure of a compact convex set finitely generated?

  40. Thank You!

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#