A strong conic quadratic reformulation for machine-job assignment with controllable processing times

M. Selim Akturk (akturkbilkent.edu.tr)
Alper Atamturk (atamturkberkeley.edu)
Sinan Gurel (sgurelbilkent.edu.tr)

Abstract: We consider a machine-job assignment problem with separable convex cost. A major source of difficulty with solving the problem using relaxation methods is that optimal solutions to its continuous relaxations are highly fractional as they are typically found in the interior of the relaxation due to the convex cost function. Here we give a polynomial-size conic quadratic reformulation of the problem so as to strengthen the bounds from its continuous relaxation. Of particular interest, we prove that the conic strengthening avoids all non-extreme solutions of the initial polyhedral relaxation; thus, it eliminates the source of difficulty of having a convex cost function. This property is important not only for improving the bounds, but also for making polyhedral inequalities that cut off fractional extreme points of the initial relaxation applicable. The results in the paper are sufficiently general so that they can also be applied to other mixed 0-1 optimization problems with separable convex cost functions. Our computational results on the machine-job assignment problem with controllable processing times demonstrate that the proposed conic reformulation is very effective for solving the problem to optimality.

Keywords:

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Citation: Research Report BCOL.07.01, IEOR, University of California-Berkeley. April 2007.

Download: [PDF]

Entry Submitted: 06/26/2007
Entry Accepted: 06/27/2007
Entry Last Modified: 06/27/2007

Modify/Update this entry