Dual relaxations of the time-indexed ILP formulation for min-sum scheduling problems
Yunpeng Pan (yunpeng.pangmail.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.
Entry Submitted: 08/04/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|