Reformulation of min constraints with binary decision variable inside the min()?

Question

I am trying to reformulate a mix integer problem with a binary decision variable lies within the min constraint.

That is ${x_1} = \min \left( {c,\frac{d}{\alpha }} \right)$ where $c$ and $d$ are two positive decision variable and $\alpha \in \left\{ {0,1} \right\}$ is a binary decision variable.

And also in the case of ${x_1} \le \min \left( {c,\frac{d}{\alpha }} \right)$ or ${x_1} \ge \min \left( {c,\frac{d}{\alpha }} \right)$ does a reformulation exist ?

My first attemp was ${x_1} = \left( {1 - \alpha } \right)c + \alpha \min \left( {c,d} \right)$ but the min() still persist

I am quite uncertain how to continue with this situation any help would be really appreciated ! Thank you very much !

Answer 1

A simple non-optimized representation starts with the initial logic

$1-\alpha=1 \rightarrow x_1 = c$

$\alpha=1 \rightarrow x_1 = \min(c,d) = x_2$

The min is also a logic condition

$c \leq d \rightarrow x_2 = c$

$c \geq d \rightarrow x_2 = d$

Introduce two binary variables $\delta$ to represent the two cases (constrained to sum to 1)

$\delta_1=1 \rightarrow x_2 = c,c \leq d $

$\delta_2=1 \rightarrow x_2 = d,c \geq d $

You now have four binary condition implies linear condition which you can represent using standard big-M modelling

$q=1 \rightarrow f = 0 \Rightarrow -M(1-q) \leq f \leq M(1-q)$

$q=1 \rightarrow f \leq 0 \Rightarrow f \leq M(1-q)$

Since you asked about high-level languages in the comment, with the MATLAB Toolbox YALMIP (disclaimer: developed by me) you would write

Model = [implies(alpha, x1 == min(c,d)), implies(1-alpha, x1 == c)]