Three formulations of the multi-type capacitated facility location problem

Andreas Klose

Abstract

The "multi-type" or "modular" capacitated facility location problem is a discrete location model that addresses non-convex piecewise linear production costs as, for instance, staircase cost functions. The literature basically distinguishes three different ways to formulate non-convex piecewise linear cost minimization problems: the convex combination model, the incremental model and the multiple choice model. All three models are generally equivalent, but in case of the MCFLP, the latter one allows to include additional variable upper bounds (implied bounds) that strengthen the LP relaxation. We show that the latter formulation, with these inequalities included, strictly dominates the other two ways of formulating the problem. We additionally investigate different strategies of including these variable upper bounds within the model using a common MIP solver.

Originalsprog	Engelsk
Publikationsdato	31 aug. 2011
Antal sider	1
Status	Udgivet - 31 aug. 2011
Begivenhed	International Conference on Operations Research - Zürich, Schweiz Varighed: 30 aug. 2011 → 2 sep. 2011

Konference

Konference	International Conference on Operations Research
Land/Område	Schweiz
By	Zürich
Periode	30/08/2011 → 02/09/2011

Citationsformater

@conference{08e4add20e0b4d4cb8897322fffd4515,

title = "Three formulations of the multi-type capacitated facility location problem",

abstract = "The {"}multi-type{"} or {"}modular{"} capacitated facility location problem is a discrete location model that addresses non-convex piecewise linear production costs as, for instance, staircase cost functions. The literature basically distinguishes three different ways to formulate non-convex piecewise linear cost minimization problems: the convex combination model, the incremental model and the multiple choice model. All three models are generally equivalent, but in case of the MCFLP, the latter one allows to include additional variable upper bounds (implied bounds) that strengthen the LP relaxation. We show that the latter formulation, with these inequalities included, strictly dominates the other two ways of formulating the problem. We additionally investigate different strategies of including these variable upper bounds within the model using a common MIP solver.",

author = "Andreas Klose",

year = "2011",

month = aug,

day = "31",

language = "English",

note = "International Conference on Operations Research ; Conference date: 30-08-2011 Through 02-09-2011",

}

TY - ABST

T1 - Three formulations of the multi-type capacitated facility location problem

AU - Klose, Andreas

PY - 2011/8/31

Y1 - 2011/8/31

N2 - The "multi-type" or "modular" capacitated facility location problem is a discrete location model that addresses non-convex piecewise linear production costs as, for instance, staircase cost functions. The literature basically distinguishes three different ways to formulate non-convex piecewise linear cost minimization problems: the convex combination model, the incremental model and the multiple choice model. All three models are generally equivalent, but in case of the MCFLP, the latter one allows to include additional variable upper bounds (implied bounds) that strengthen the LP relaxation. We show that the latter formulation, with these inequalities included, strictly dominates the other two ways of formulating the problem. We additionally investigate different strategies of including these variable upper bounds within the model using a common MIP solver.

AB - The "multi-type" or "modular" capacitated facility location problem is a discrete location model that addresses non-convex piecewise linear production costs as, for instance, staircase cost functions. The literature basically distinguishes three different ways to formulate non-convex piecewise linear cost minimization problems: the convex combination model, the incremental model and the multiple choice model. All three models are generally equivalent, but in case of the MCFLP, the latter one allows to include additional variable upper bounds (implied bounds) that strengthen the LP relaxation. We show that the latter formulation, with these inequalities included, strictly dominates the other two ways of formulating the problem. We additionally investigate different strategies of including these variable upper bounds within the model using a common MIP solver.

M3 - Conference abstract for conference

T2 - International Conference on Operations Research

Y2 - 30 August 2011 through 2 September 2011

ER -

Three formulations of the multi-type capacitated facility location problem

Abstract

Konference

Fingeraftryk

Citationsformater