Optimization Examples

 by Seungchul LeeiSystems Design Labhttp://isystems.unist.ac.kr/UNIST

General or Standard Forms

1. Linear programming \begin{align*} \min_{x} \quad & f^Tx \\ \text{subject to} \quad & Ax \leq b\\ & A_{eq}x = b_{eq}\\ & LB \leq x \leq UB \end{align*}

2. Integer programming \begin{align*} \min_{x} \quad & f^Tx \\ \text{subject to} \quad & Ax \leq b\\ & A_{eq}x = b_{eq}\\ & LB \leq x \leq UB\\ & x \in \mathbb{Z} \;\text{(integer)} \end{align*}

3. Mixed integer linear programming \begin{align*} \min_{x,z} \quad & f^T \begin{bmatrix} x \\ z \end{bmatrix} \\ \text{subject to} \quad & A \begin{bmatrix} x \\ z \end{bmatrix} \leq b \\ & A_{eq} \begin{bmatrix} x \\ z \end{bmatrix} = b_{eq}\\ & LB \leq \begin{bmatrix} x \\ z \end{bmatrix} \leq UB \\ & x \in \mathbb{R} \;\text{(real)} \\ & z \in \mathbb{Z} \end{align*}

4. Binary integer programming \begin{align*} \min_{x} \quad & f^Tx \\ \text{subject to} \quad & Ax \leq b \\ & A_{eq}x = b_{eq} \\ & LB \leq x \leq UB \\ & x \in \{0,1\} \end{align*}

5. Quadratic programming \begin{align*} \min_{x} \quad & \frac{1}{2}x^THx + f^Tx \\ \text{subject to} \quad & Ax \leq b \\ & A_{eq}x = b_{eq} \\ & LB \leq x \leq UB \end{align*}

# 1. Mixed Integer Linear Programming (MILP)¶

• Matlab command: intlinprog (available from MATLAB R2014b)

## 1.1. Knapsack problems¶

• There is a container (knapsack) of capacity C = 20.
• Furthermore, there is a set 6 of objects.
• Each object has a weight and a value.
• Determine the number of each item to include in a collection so that the total size is less than or equal to 20 and the total value is as large as possible.
items 1 2 3 4 5 6
weights 10 9 4 2 1 20
values 175 90 20 50 10 200

Question: Can we formulate this knapsack problem into a binary integer program?

$\Rightarrow$ decision variables $\quad x_{i} \in \{0,1\} \quad i = 1,\cdots,6$

\begin{align*} \max_{x} \quad & 175x_1 + 90x_2 + 20x_3 + 50x_4 + 10x_5 + 200x_6 \\ \text{subject to} \quad & 10x_1 + 9x_2 + 4x_3 + 2x_4 + x_5 + 20x_6 \leq 20 \\ \end{align*}

$\Rightarrow$ intlinprog in Matlab to solve

In [4]:
% given
n = 6;  % # of items
weights = [10 9 4 2 1 20];
values = [175 90 20 50 10 200];
maxWeight = 20;

% in a form of MILP
f = -values;        % max
A = weights;
b = maxWeight;
intcon = 1:n;
lb = zeros(n,1);
ub = ones(n,1);

x = intlinprog(f,intcon,A,b,[],[],lb,ub)
Out[4]:
LP:                Optimal objective value is -305.000000.

Cut Generation:    Applied 1 strong CG cut.
Lower bound is -275.000000.
Relative gap is 0.00%.

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.TolGapAbs = 0
(the default value). The intcon variables are integer within tolerance, options.TolInteger = 1e-05 (the default value).

x =

1.0000
1.0000
0
0
1.0000
0

## 1.2. Factory and warehouse¶

• A campany wants to

1) build new factory in Ulsan, Busan, or both

2) build new warehouse (only one has to be built)

3) warehouse must be built in a city of a new factory

• Available capital to build is 10. We want to maximize total profit.
Profit Cost to build
1 Build a factory in Ulsan 7 5
2 Build a factory in Busan 5 3
3 Build a warehouse in Ulsan 6 5
4 Build a warehouse in Busan 4 2
• Form a binary integer programming to find the optimal locations of new factory and warehouse, and solve it using intlinprog in MATLAB.

(Hint: define binary decision variables, then use them to define objective function and constraints.)

In [5]:
f = -[7 5 6 4]';
intcon = [1 2 3 4];
A = [5 3 5 2;
-1 -1 0 0;
-1 0 1 0;
0 -1 0 1];
b = [10;
-1;
0;
0];

Aeq = [0 0 1 1];
beq = [1];

lb = [0 0 0 0]';
ub = [1 1 1 1]';
[x fval] = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
Out[5]:
LP:                Optimal objective value is -16.000000.

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.TolGapAbs = 0
(the default value). The intcon variables are integer within tolerance, options.TolInteger = 1e-05 (the default value).

x =

1.0000
1.0000
0
1.0000

fval =

-16

## 1.3. Shortest path¶

• Binary integer programming can be applied to finding the shortest path in the graph.
• Define the binary decision variables and form the binary integer programming. Then you can solve it using intlinprog command in MATLAB

In [6]:
f = [1 4 2 4 8 11 3]';
Aeq = [1 1 0 0 0 0 0
1 0 -1 0 0 -1 0
0 1 1 -1 -1 0 0
0 0 0 1 0 0 -1
0 0 0 0 1 1 1];
beq = [1 0 0 0 1]';

intcon = 1:7;
lb = zeros(7,1);
ub = ones(7,1);

x = intlinprog(f,intcon,[],[],Aeq,beq,lb,ub)
Out[6]:
LP:                Optimal objective value is 10.000000.

Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.TolGapAbs = 0
(the default value). The intcon variables are integer within tolerance, options.TolInteger = 1e-05 (the default value).

x =

1
0
1
1
0
0
1

## 2.1. Best location at a concert¶

Question: Find the best location to listen to singer's voice

\begin{align*} \Rightarrow \quad \min \quad & \sqrt{(x_1-3)^{2}+(x_2-3)^{2}} \\ \Rightarrow \quad \min \quad & (x_1-3)^{2} + (x_2-3)^{2} \\ \text{subject to} \quad & x_1 + x_2 \leq 3 \\ & x_1 \geq 0 \\ & x_2 \geq 0 \end{align*}

\begin{align*} \Rightarrow \quad & x_1^{2} - 6x_1 + 9 + x_2^{2} - 6x_2 + 9 \\ & = x_1^{2} + x_2^{2} - 6 x_1 - 6x_2 + 18 \\ & = \frac{1}{2} \begin{bmatrix} x_1 & x_2 \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} - \begin{bmatrix} 6 & 6 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + 18 \\ & \begin{bmatrix} 1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \leq 3 \\ & \begin{bmatrix} 0 \\ 0 \end{bmatrix} \leq \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \leq \begin{bmatrix} \\ \\ \end{bmatrix} \end{align*}

In [11]:
H = [2 0;
0 2];
f = -[6 6]';
A = [1 1];
b = 3;
lb = [0 0]';

Out[11]:
Minimum found that satisfies the constraints.

Optimization completed because the objective function is non-decreasing in
feasible directions, to within the default value of the function tolerance,
and constraints are satisfied to within the default value of the constraint tolerance.

x =

1.5000
1.5000

# 3. Convex Problems (CVX)¶

## 3.1. Shortest distance¶

$$\min \; d_1 + d_2 = \min \left\rVert \vec{a} - \begin{bmatrix}x\\0\end{bmatrix}\right\rVert_2 + \left\rVert \vec{b} - \begin{bmatrix}x\\0\end{bmatrix}\right\rVert_2$$
• $\vec{a} \rightarrow \begin{bmatrix}x\\0\end{bmatrix}$: walk with an empty bucket
• $\begin{bmatrix}x\\0\end{bmatrix} \rightarrow \vec{b}$: walk with a water-filled bucket
$$\implies \min d_1 + \mu d_2$$
• can use cvx to find $x$
In [8]:
clear all,  clc

pt1 = [0 2]';
pt2 = [4 1]';
mu = 1;         % can give different weight

cvx_begin quiet
variable x
minimize norm([x 0]'-pt1,2) + mu*norm([x 0]'-pt2,2)
cvx_end

x
cvx_optval
Out[8]:
x =

2.6665

cvx_optval =

5.0000

## 3.2. Weber problems¶

• Find a point in the plane that minimizes the sum of the transportation costs (or distance) from this point to $n$ destination points
In [1]:
clear all
clc

A = [sqrt(3) 0]';
B = [-sqrt(3) 0]';
C = [0 1+2]';

cvx_begin quiet
variable x(2,1)
minimize norm(x-A,2) + norm(x-B,2) + norm(x-C,2)
cvx_end
x
cvx_optval
Out[1]:
x =

-0.0000
1.0000

cvx_optval =

6.0000
In [2]:
pts = [A B C];
plot(pts(1,:),pts(2,:),'o'), hold on
plot(x(1),x(2),'s'), hold off
axis equal
xlim([-3,3])
Out[2]:
In [13]:
P = [A;B;C];
Phi = repmat(eye(2),[3,1]);

cvx_begin quiet
variable x(2,1)
minimize norm(Phi*x-P,1)
cvx_end
x
cvx_optval
Out[13]:
x =

1.0e-08 *

-0.0005
0.1935

cvx_optval =

6.4641

## 3.3. Piece-wise linear programming¶

Linear vs. Affine

• Linear
$$f(x)=a^Tx$$
• Affine
$$f(x) = a^Tx + b$$

$L_1$ norm optimization

• $L_1$ norm
$$\lVert y \rVert_{1} = \sum_{i} \,\lvert y_i \rvert = \sum_{i} \, \max \left(-y_i,y_i \right)$$
• Fitting/Approximation Problem, i.e., sum of (absolute) residuals
$$\min \; \lVert Ax-b \rVert_1 = \lvert r_1 \rvert + \cdots + \lvert r_m \rvert$$
• LP Equivalent

• $t = \begin{bmatrix} t_1 & t_2 & \cdots & t_m \end{bmatrix}^T$ \begin{align*} \min \quad & t_1 + \cdots + t_m \\ \text{subject to} \quad & Ax - b \leq t \\ & -(Ax - b) \leq t \end{align*}
• LP Equivalent in Matrix Form

\begin{align*} \min \quad & \begin{bmatrix} \mathbb{0} & \mathbb{1} \end{bmatrix}^T \begin{bmatrix} x \\ t \end{bmatrix} \\ \text{subject to} \quad & \begin{bmatrix} A & -I \\ -A & -I \end{bmatrix}\begin{bmatrix} x \\ t \end{bmatrix} \leq \begin{bmatrix} b \\ -b \end{bmatrix} \end{align*}
• can convert it to LP or just simply use cvx
In [14]:
p1 = [sqrt(3) 0]';
p2 = [-sqrt(3) 0]';
p3 = [0 1+2]';

cvx_begin quiet
variable x(2,1)
% minimize norm(x-p1,2) + norm(x-p2,2) + norm(x-p3,2)
minimize norm(x-p1,1) + norm(x-p2,1) + norm(x-p3,1)
cvx_end
x
cvx_optval

pts = [p1 p2 p3];
plot(pts(1,:),pts(2,:),'o'), hold on
plot(x(1),x(2),'s'), hold off
axis equal
xlim([-3,3])
Out[14]:
x =

1.0e-08 *

-0.0005
0.3541

cvx_optval =

6.4641
In [29]:
% weber problem in 2-norm

m = 10;
pts = 10*rand(2,10);
plot(pts(1,:),pts(2,:),'o'), axis equal, xlim([-1 11]), hold on

b = reshape(pts,[2*m,1]);
A = repmat(eye(2),[m,1]);

%w = inv(A'*A)*A'*b

cvx_begin quiet
variables w(2,1)
minimize norm(A*w-b,2)
cvx_end
plot(w(1),w(2),'s'), hold off
Out[29]:
In [41]:
% weber problem in 2-norm

m = 10;
pts = 10*rand(2,10);
pts = [pts [20 20]' [19 19]']
Out[41]:
pts =

9.5163    0.5268    2.6912    5.4787    4.1774    3.0145    6.6634    6.9811    1.7813    9.9908   20.0000   19.0000
9.2033    7.3786    4.2284    9.4274    9.8305    7.0110    5.3913    6.6653    1.2801    1.7112   20.0000   19.0000
In [42]:
plot(pts(1,:),pts(2,:),'o'),
%axis equal, xlim([-1 22]),
hold on

b = reshape(pts,[2*(m+2),1]);
A = repmat(eye(2),[m+2,1]);

%w = inv(A'*A)*A'*b

cvx_begin quiet
variables w(2,1)
minimize norm(A*w-b,2)
cvx_end
plot(w(1),w(2),'s'), hold off
Out[42]:
In [43]:
plot(pts(1,:),pts(2,:),'o'),
%axis equal, xlim([-1 22]),
hold on

b = reshape(pts,[2*(m+2),1]);
A = repmat(eye(2),[m+2,1]);

%w = inv(A'*A)*A'*b

cvx_begin quiet
variables w(2,1)
minimize norm(A*w-b,1)
cvx_end
plot(w(1),w(2),'s'), hold off
Out[43]:
In [1]:
%%javascript
\$.getScript('https://kmahelona.github.io/ipython_notebook_goodies/ipython_notebook_toc.js')