1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – giulatona Sep 29 '14 at 14:09
  • $\begingroup$ 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. $\endgroup$ – Johan Löfberg Sep 29 '14 at 14:35
  • $\begingroup$ 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 $\endgroup$ – giulatona Sep 30 '14 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.