Exercise 1.3

Question

Consider the problem of minimizing a cost function of the form $\mathbf{c}\mathbf{x} + f(\mathbf{d}'\mathbf{x})$, subject to the linear constraints $\mathbf{A}\mathbf{x} \geq \mathbf{b}$. Here, $\mathbf{d}$ is a given vector and the function $f:\mathfrak{R}	o\mathfrak{R}$ is as specified in the figure below. Provide a linear programming formulation of this problem.
\begin{figure}
\includegraphics[width=0.65	extwidth]{bertsimas_linopt_exercise_1-3.png}
\end{figure}

Elu Thingol · Accepted Answer

From the graph given in the exercise, we deduce the formula for $f$:
\begin{equation*}
f:\mathfrak{R} \to \mathfrak{R}, \quad x \mapsto
\left\{\begin{array}{l}
-x+1 &\text{for } x \in (-\infty,1]\
0 &\text{for } x \in (1,2)\
2(x-2) &\text{for } x \in [2,+\infty)
\end{array}\right.
\end{equation*}

The trick is to see that the above definition is equivalent to the following formula involving a maximum function
$$\forall x \in \mathfrak{R}: \quad f(x) = \max\left\{-x+1,0,2x-4\right\}.$$

As suggested in Section 1.3, we can equivalently rewrite this kind of minimization problems as
\begin{equation*}
\begin{array}{lllll}
\min &\mathbf{c}'\mathbf{x} + \max\left\{-\mathbf{d}'\mathbf{x}+1,0,2(\mathbf{d}'\mathbf{x}+2)\right\} & & \min& \mathbf{c}'\mathbf{x} + x_0\
\text{s.t. }& \mathbf{A}\mathbf{x} \geq \mathbf{b} & \ \iff\ & \text{s.t. }& \mathbf{A}\mathbf{x} \geq \mathbf{b}\
&&&&x_0 \geq -\mathbf{d}'\mathbf{x}+1\
&&&&x_0 \geq 0\
&&&&x_0 \geq 2\mathbf{d}'\mathbf{x}-4.
\end{array}
\end{equation*}

Moving variables to the left and constraints to the right, we rewrite the above as:
\begin{equation*}
\begin{array}{rl}
\text{minimize}\ & \mathbf{c}'\mathbf{x} + x_0\[5pt]
\text{subject to}\ &
\mathbf{A}\mathbf{x} + 0 x_0 \geq \mathbf{b}\
&\mathbf{d}'\mathbf{x} + x_0 \geq 1\
&\mathbf{0}'\mathbf{x} + x_0 \geq 0\
&-2\mathbf{d}'\mathbf{x} + x_0 \geq -4.
\end{array}
\end{equation*}

The above problem can be easily reformulated as a linear programming problem in $\mathfrak{R}^{n+1}$:
\begin{equation*}
\begin{array}{rl}
\text{minimize}\ & \begin{bmatrix} \mathbf{c}' & 1 \end{bmatrix} \begin{bmatrix} \mathbf{x} \ x_0 \end{bmatrix}\[5pt]
\text{subject to}\ &
\begin{bmatrix}
\mathbf{A} & 0\
\mathbf{d}' & 1\
\mathbf{0}' & 1\
-2\mathbf{d'} & 1
\end{bmatrix} \begin{bmatrix} \mathbf{x} \ x_0 \end{bmatrix} \geq \begin{bmatrix} \mathbf{b} \ 1 \ 0 \ -4 \end{bmatrix}.
\end{array}
\end{equation*}

Exercise 1.3

Answers

Comments

Exercise 1.3

Answers

Comments

Add answer