Optimization Online


Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems

Yunpeng Pan (yunpeng.pan***at***gmail.com)

Abstract: Linear programming (LP)-based relaxations have proven to be useful in enumerative solution procedures for NP-hard min-sum scheduling problems. We take a dual viewpoint of the time-indexed integer linear programming (ILP) formulation for these problems. Previously proposed Lagrangian relaxation methods and a time decomposition method are interpreted and synthesized under this view. Our new results aim to find optimal or near-optimal dual solutions to the LP relaxation of the time-indexed formulation, as recent advancements made in solving this ILP problem indicate the utility of dual information. Specifically, we develop a procedure to compute optimal dual solutions using the solution information from Dantzig-Wolfe decomposition and column generation methods, whose solutions are generally nonbasic. As a byproduct, we also obtain, in some sense, a crossover method that produces optimal basic primal solutions. Furthermore, the dual view naturally leads us to propose a new polynomial-sized relaxation that is applicable to both integer and real-valued problems. The obtained dual solutions are incorporated in branch-and-bound for solving the total weighted tardiness scheduling problem, and their efficacy is evaluated and compared through computational experiments involving test problems from OR-Library.

Keywords: min-sum scheduling; time-indexed formulation; duality; polynomial size

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

Category 2: Combinatorial Optimization

Category 3: Integer Programming (0-1 Programming )

Citation: working paper. submitted for publication.

Download: [PDF]

Entry Submitted: 08/04/2006
Entry Accepted: 08/04/2006
Entry Last Modified: 08/10/2006

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 Programming Society