6
2 Layout on a Single Row
We now have all the ingredients to express our machine placement problem using
a mathematical optimization model:
minimize
11
i=1
12
j =i+1
c ij |x i − x j |,
(2.3)
subject to |x i − x j | ≥
1
2
(( i + j ), i, j = 1, . . . , 12, i < j,
(2.4)
1
2
i ≤ x i ≤ L −
1
2
i , i = 1, . . . , 12.
(2.5)
We will sometimes use the abbreviation “min” and write below it the variables
involved in the optimization.
2.1.1 On Convexity and Linearity
Even though the mathematical optimization problem (2.3–2.5) is a correct model for
the example, there are better formulations in practice. We advocate the use whenever
possible of convex optimization formulations because they have two important
advantages. First, for a convex optimization problem (defined below), any local
optimal solution is also a global optimal solution. Second, there exist polynomialtime interior-point algorithms for convex optimization that have been shown to work
well in practice. An algorithm is said to run in polynomial time if the number of
steps required to complete the algorithm for a given input is bounded above by
a polynomial function (of fixed degree) of the size of the input. Polynomial-time
algorithms are generally considered to be efficient.
A convex optimization problem consists of minimizing a convex objective
function (or maximizing a concave function) over a convex set of possible solutions.
These concepts are defined as follows.
Definition 2.1 (See Fig. 2.3.) A function f : : n → → is convex if its domain is
convex and if for all x, y in its domain and τ ∈ [0, 1],
f (τ x + (1 − τ )y) ≤ τf (x) + (1 − τ )f (y).
Definition 2.2 (See Fig. 2.4.) A set C is convex if for all x, y ∈ C, the convex
combination τ x + (1 − τ )y ∈ C for all τ ∈ (0, 1).
Checking whether a given optimization problem is convex is not straightforward
in general. Moreover, not all convex problems can be directly solved by the existing
software. For these reasons, in practice it is best to focus on well-known forms
of convex optimization. For example, linear optimization is convex. Semidefinite
2 Layout on a Single Row
We now have all the ingredients to express our machine placement problem using
a mathematical optimization model:
minimize
11
i=1
12
j =i+1
c ij |x i − x j |,
(2.3)
subject to |x i − x j | ≥
1
2
(( i + j ), i, j = 1, . . . , 12, i < j,
(2.4)
1
2
i ≤ x i ≤ L −
1
2
i , i = 1, . . . , 12.
(2.5)
We will sometimes use the abbreviation “min” and write below it the variables
involved in the optimization.
2.1.1 On Convexity and Linearity
Even though the mathematical optimization problem (2.3–2.5) is a correct model for
the example, there are better formulations in practice. We advocate the use whenever
possible of convex optimization formulations because they have two important
advantages. First, for a convex optimization problem (defined below), any local
optimal solution is also a global optimal solution. Second, there exist polynomialtime interior-point algorithms for convex optimization that have been shown to work
well in practice. An algorithm is said to run in polynomial time if the number of
steps required to complete the algorithm for a given input is bounded above by
a polynomial function (of fixed degree) of the size of the input. Polynomial-time
algorithms are generally considered to be efficient.
A convex optimization problem consists of minimizing a convex objective
function (or maximizing a concave function) over a convex set of possible solutions.
These concepts are defined as follows.
Definition 2.1 (See Fig. 2.3.) A function f : : n → → is convex if its domain is
convex and if for all x, y in its domain and τ ∈ [0, 1],
f (τ x + (1 − τ )y) ≤ τf (x) + (1 − τ )f (y).
Definition 2.2 (See Fig. 2.4.) A set C is convex if for all x, y ∈ C, the convex
combination τ x + (1 − τ )y ∈ C for all τ ∈ (0, 1).
Checking whether a given optimization problem is convex is not straightforward
in general. Moreover, not all convex problems can be directly solved by the existing
software. For these reasons, in practice it is best to focus on well-known forms
of convex optimization. For example, linear optimization is convex. Semidefinite