Optimization Online


Tight MIP formulations for bounded length cyclic sequences

Thomas Kalinowski (tkalinow***at***une.edu.au)
Tomas Lidén (tomas.liden***at***liu.se)
Hamish Waterer (hamish.waterer***at***newcastle.edu.au)

Abstract: We study cyclic binary strings with bounds on the lengths of the intervals of consecutive ones and zeros. This is motivated by scheduling problems where such binary strings can be used to represent the state (on/off) of a machine. In this context the bounds correspond to minimum and maximum lengths of on- or off-intervals, and cyclic strings can be used to model periodic schedules. Extending results for non-cyclic strings is not straight forward. We present a non-trivial tight compact extended network flow formulation, as well as valid inequalities in the space of the state and start-up variables some of which are shown to be facet-defining. Applying a result from disjunctive programming, we also convert the extended network flow formulation into an extended formulation over the space of the state and start-up variables.

Keywords: Production sequencing; Bounded up/down times; Extended formulations; Convex hulls

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Applications -- OR and Management Sciences (Scheduling )


Download: [PDF]

Entry Submitted: 09/05/2018
Entry Accepted: 09/05/2018
Entry Last Modified: 09/06/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society