[Math] Linearize if statement in linear programming

linear programmingoptimization

I am having trouble figuring out how to formulate the following objective function in LP

a + b + (if(c < d) then e else 0)

Where a, b, c, d and e are some sums or differences of variables multiplied by some real constants.
I thought that maybe by introducing a binary variable x I could redefine it as

a + b + xe

But that would no longer be linear, not to mention even then I couldnt come up with what constraints x would need to have…

Any help with this would be greatly appreciated, Ive been racking my brain and googling left and right for hours now, but with no clear solution in sight.

Edit:
For full context, I am trying to minimize distance and trying to use the last distance approximation formula found here: http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml

Best Answer

Let the objective be $a + b + q$ and use the big M trick.

Letting $\delta$ be the binary variable, we first define constraints such that $\delta = 0$ if $c \leq d$ and $\delta = 1$ otherwise.

$$ c \leq d + M \delta \\ c \geq d - M (1 - \delta) $$ where $M$ is a large number. Then we define constraints such that $q$ gives the values required.

$$ e - M\delta \leq q \leq e + M \delta \\ - M(1 - \delta) \leq q \leq e + M (1 + \delta) $$

Related Solutions

Fixing a minimal number of variables in linear programming problem to worsen objective

This is an instance of a bilevel program, as you can see it as an optimization problem where one of the constraints is that a variable is optimal in some other optimization problem. It can be represented as a MILP via KKT conditions.

Here is a test in the MATLAB Toolbox YALMIP https://yalmip.github.io/tutorial/bilevelprogramming/

A = randn(10,7);
b = 10*rand(10,1);
c = randn(7,1);
x = sdpvar(7,1);
optimize([0<=x<=1, A*x <= b],-c'*x)

z = value(c'*x);
y = binvar(7,1);
OuterC = [c'*x <= z - 0.1];
OuterO = sum(y);
InnerC = [0<=x<=1, x <= 1-y, A*x <= b]
InnerO = -c'*x;
solvebilevel(OuterC,OuterO,InnerC,InnerO,x)
value(x)
value(y)

This example uses the built-in naive bilevel solver. A typically better solution is to ask it to use an external MILP solver instead or manually use the kkt operator to define the MILP and then call the MILP solver

https://yalmip.github.io/example/bilevelprogrammingalternatives/

https://yalmip.github.io/command/kkt/

Best Answer

Related Solutions

Fixing a minimal number of variables in linear programming problem to worsen objective

Related Question