Contents
1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
1
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
2
2 Layout on a Single Row . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
3
2.1 Introductory Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
3
2.1.1 On Convexity and Linearity . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
6
2.2 Single-Row Layout as a General Class of Problems .. . . . . . . . . . . . . . . .
8
2.3 Mixed-Integer Linear Optimization Approach . . .. . . . . . . . . . . . . . . . . . . .
9
2.3.1 Linearization of the Distance . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
9
2.3.2 Linearization of the Nonoverlap Constraints.. . . . . . . . . . . . . . . . 10
2.3.3 Choosing M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 11
2.3.4 Mixed-Integer Linear Optimization Formulation .. . . . . . . . . . . 12
2.4 Betweenness-Based Binary Linear Optimization Formulation .. . . . . 13
2.5 Binary Quadratic Optimization Formulation .. . . .. . . . . . . . . . . . . . . . . . . . 17
2.6 Linearizing the Binary Quadratic Optimization Formulation . . . . . . . 18
2.6.1 Initial Linearization . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 18
2.6.2 Improving the Linearized Formulation .. .. . . . . . . . . . . . . . . . . . . . 20
2.7 Semidefinite Optimization Formulation . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 21
2.7.1 Improving the Semidefinite Formulation .. . . . . . . . . . . . . . . . . . . . 25
2.8 Inequality Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 26
2.9 SRFLP with Departments of Equal Length . . . . . .. . . . . . . . . . . . . . . . . . . . 27
2.10 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 29
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 30
3 Layout on Several Rows .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 33
3.1 Double-Row Facility Layout .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 34
3.1.1 Initial Mixed-Integer Linear Optimization Model . . . . . . . . . . . 35
3.1.2 Improved Mixed-Integer Linear Optimization
Model with Betweenness Variables . . . . . .. . . . . . . . . . . . . . . . . . . . 37
vii
1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
1
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
2
2 Layout on a Single Row . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
3
2.1 Introductory Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
3
2.1.1 On Convexity and Linearity . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
6
2.2 Single-Row Layout as a General Class of Problems .. . . . . . . . . . . . . . . .
8
2.3 Mixed-Integer Linear Optimization Approach . . .. . . . . . . . . . . . . . . . . . . .
9
2.3.1 Linearization of the Distance . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .
9
2.3.2 Linearization of the Nonoverlap Constraints.. . . . . . . . . . . . . . . . 10
2.3.3 Choosing M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 11
2.3.4 Mixed-Integer Linear Optimization Formulation .. . . . . . . . . . . 12
2.4 Betweenness-Based Binary Linear Optimization Formulation .. . . . . 13
2.5 Binary Quadratic Optimization Formulation .. . . .. . . . . . . . . . . . . . . . . . . . 17
2.6 Linearizing the Binary Quadratic Optimization Formulation . . . . . . . 18
2.6.1 Initial Linearization . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 18
2.6.2 Improving the Linearized Formulation .. .. . . . . . . . . . . . . . . . . . . . 20
2.7 Semidefinite Optimization Formulation . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 21
2.7.1 Improving the Semidefinite Formulation .. . . . . . . . . . . . . . . . . . . . 25
2.8 Inequality Separation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 26
2.9 SRFLP with Departments of Equal Length . . . . . .. . . . . . . . . . . . . . . . . . . . 27
2.10 References and Further Reading . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 29
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 30
3 Layout on Several Rows .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 33
3.1 Double-Row Facility Layout .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . 34
3.1.1 Initial Mixed-Integer Linear Optimization Model . . . . . . . . . . . 35
3.1.2 Improved Mixed-Integer Linear Optimization
Model with Betweenness Variables . . . . . .. . . . . . . . . . . . . . . . . . . . 37
vii