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

被引：77

作者：

Akturk, M. Selim ^{[2
]}

Atamturk, Alper ^{[1
]}

Gurel, Sinan ^{[2
]}

机构：

[1] Univ Calif Berkeley, Dept Ind Engn & Operat Res, Berkeley, CA 94720 USA

[2] Bilkent Univ, Dept Ind Engn, TR-06800 Ankara, Turkey

来源：

OPERATIONS RESEARCH LETTERS | 2009年 / 37卷 / 03期

基金：

美国国家科学基金会;

关键词：

Separable convex functions; Conic quadratic integer programming; SEMIDEFINITE; PROGRAMS; CUTS;

D O I：

10.1016/j.orl.2008.12.009

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

we describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based only on the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：187 / 191

页数：5

共 17 条

[1] Second-order cone programming [J].

Alizadeh, F ;

Goldfarb, D .

MATHEMATICAL PROGRAMMING, 2003, 95 (01) :3-51

[2] Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem [J].

Anjos, MF ;

Wolkowicz, H .

DISCRETE APPLIED MATHEMATICS, 2002, 119 (1-2) :79-106

[3]

ATAMTURK A, 2006, MATH PROGRA IN PRESS, DOI DOI 10.1007/SI0107-008-0239-4

[4]

Ben-Tal A, 2001, LECT MODERN CONVEX O, V2

[5] Cuts for mixed 0-1 conic programming [J].

Çezik, MT ;

Iyengar, G .

MATHEMATICAL PROGRAMMING, 2005, 104 (01) :179-202

[6] Perspective cuts for a class of convex 0-1 mixed integer programs [J].

Frangioni, A ;

Gentile, C .

MATHEMATICAL PROGRAMMING, 2006, 106 (02) :225-236

[7] Semidefinite programming in combinatorial optimization [J].

Goemans, MX .

MATHEMATICAL PROGRAMMING, 1997, 79 (1-3) :143-161

[8]

GUNLUK O, 2007, RC24213 IBM TJ WATS

[9] Considering manufacturing cost and scheduling performance on a CNC turning machine [J].

Gurel, Sinan ;

Akturk, M. Selim .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2007, 177 (01) :325-343

[10] Solving quadratic (0,1)-problems by semidefinite programs and cutting planes [J].

Helmberg, C ;

Rendl, F .

MATHEMATICAL PROGRAMMING, 1998, 82 (03) :291-315

← 1 2 →