[Math] Optimization Technique for Step function in constraints and objective function

linear programmingnonlinear optimizationoptimization

I've the non linear optimization problem which involve using a step function.
The simplified version of the problem is shown below:

$\max (3u_1 + 4u_2 + 5u_3)$
Subjected to

$u_1v_1 + u_2v_2 + u_3v_3\leq C$

$u_1 = 1$ if $v_1 \geq a$; else $u_1=0$
$u_2 = 1$ if $v_2 \geq b$; else $u_2=0$
$u_3 = 1$ if $v_3 \geq c$; else $u_3=0$
where $C, a, b, c$ are all constant

by adjusting $v_1$,$v_2$,$v_3$

Is there a way to convert this into LP ?.
Otherwise what's the best technique to solve the problem ? Btw I'm doing this in R

Best Answer

No, it can not be done as an LP, but easily written as a mixed-integer LP through big-M modelling.

With $u_1$ defined as a binary variable, your first logic constraint can for instance be written as $Mu_1 \geq v_1 - a \geq -M(1-u_1)$ where $M$ is a small-but-sufficiently-large constant such that no optimal solutions are cut off (called big-M constant).

Your bilinear constraints can be handled by replacing the product $u_iv_i$ with a new variables $w_i$ and introducing the big-M constraints $-M(1-u_i) \leq w_i-v_i \leq M(1-u_i), -Mu_i \leq w_i \leq Mu_i$.

Related Question