Parsimonious Binary-Encoding in Integer Programming

Don Coppersmith (dcopperus.ibm.com)
Jon Lee (jonleeus.ibm.com)

Abstract: We describe an effective method for doing binary-encoded modeling, in the context of 0/1 linear programming, when the number of feasible configurations is not a power of two. Our motivation comes from modeling all-different restrictions.

Keywords: polytope, integer programming, coloring, all different

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Citation:

Download: [PDF]

Entry Submitted: 05/10/2005
Entry Accepted: 05/10/2005
Entry Last Modified: 05/10/2005

Modify/Update this entry