1

I have an optimization problem of the type:

$\min f(x) \\ s.t. Ax \le b \\ g(x)=0 $

where $g(x)$ is a piecewise-linear function defined as:

$g(x) = \begin{cases} c_1^Tx & \text{if $x_1+x_2-x_3 \ge 0$} \\ c_2^Tx & \text{otherwise} \end{cases} $

I would like to know how to express this problem into a MIP and solve it.

Davide Giraudo
  • 172,925
giulatona
  • 13

1 Answers1

2

Introduce binaries $\delta_1$and $\delta_2$ satisfying $\delta_1+\delta_2=1$. Now you have two cases, $\delta_1=1$, $c_1^Tx=0$, $x_1+x_2-x_3\geq 0$ and $\delta_2=1$, $c_2^Tx=0$, $x_1+x_2-x_3\leq -\epsilon$. Standard big-M modelling and you have something like

$$ -M(1-\delta_1) \leq c_1^Tx \leq M(1-\delta_1)\\ -M(1-\delta_2) \leq c_2^Tx \leq M(1-\delta_2)\\ x_1+x_2-x_3 \geq -M(1-\delta_1)\\ x_1+x_2-x_3 \leq -\epsilon + M(1-\delta_2) $$

Of course, in practice you use different big-M constants on each constraint and try to make them as small as possible.

$\delta_1+\delta_2 =1$ is redundant as the two sets are disjoint, but it never hurts to add simple constraints on binaries.

Johan Löfberg
  • 9,497
  • 1
  • 15
  • 15
  • Since I only have two cases, would it be correct to just use one binary variable $\delta$ and its complement $(1-\delta)$? Or could this cause errors? – giulatona Sep 29 '14 at 14:09
  • Sure, same thing. Just doesn't generalize as well. Also note that a MILP approach is a pretty large machinery to use if this is the complete model. Simply solve two LPs and you are done. – Johan Löfberg Sep 29 '14 at 14:35
  • Thank you, I cannot solve two LPs because my problem has more than one of these equality constraints (one for each time step). I am aware that it is a pretty heavy computation – giulatona Sep 30 '14 at 15:20