DOS Optimization Seminars: Modeling Disjunctive Constraints

Event Details
  • Date/Time:
    • Thursday April 10, 2008
      3:00 pm - 4:00 pm
  • Location: ISyE Pool boardroom
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    $0.00
  • Extras:
Contact
Juan Pablo Vielma
ISyE
Contact Juan Pablo Vielma
404-894-2300
Summaries

Summary Sentence: DOS Optimization Seminars: Modeling Disjunctive Constraints

Full Summary: Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints.

Title: Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints

Speaker: Juan Pablo Vielma

Abstract: Many combinatorial constraints over continuous variables such as SOS1 and SOS2 constraints can be interpreted as disjunctive constraints that restrict the variables to lie in the union of m specially structured polyhedra. Known mixed integer binary formulations for these constraints have a number of binary variables and extra constraints that is linear in m. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints that is logarithmic in m. Using these conditions we introduce the first mixed integer binary formulations for SOS1 and SOS2 constraints that use a number of binary variables and extra constraints that is logarithmic in the number of continuous variables.We also introduce the first mixed integer binary formulations for piecewise linear functions of one and two variables that use a number of binary variables and extra constraints that is logarithmic in the number of linear pieces of the functions. We prove that the new formulations for piecewise linear functions have favorable tightness properties and present computational results showing that they can significantly outperform other mixed integer binary formulations. Joint work with Prof. George L. Nemhauser

Contact: ISyE DOS Optimization Seminars http://www2.isye.gatech.edu/dos/

Additional Information

In Campus Calendar
No
Groups

H. Milton Stewart School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints
Status
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 12, 2009 - 5:20pm
  • Last Updated: Oct 7, 2016 - 9:47pm