Converting a basic MILP into LP

Question

I have a MILP looks like following:

$$ min \sum_i capacity[i] * weight[i] $$

where i=[Mid_North_1, Mid_North_2, North_Mid_1, North_Mid_2]

Basically I got 2 sites called Mid and North, and 2 paths between those sites each 1 and 2.

For path 1 and 2, I got a weight associating with it. (Mid_North_1 is the same path with North_Mid_1, so same weight.)

I am trying to move some value between sites Mid and North, using the less weighted path 1 and 2 via:

$s.t.: (for Mid) - flow(Mid\_North_1) - flow(Mid\_North_2) + flow(North\_Mid_1) + flow(North\_Mid_2) = -0.001$ $s.t.: (for North) + flow(Mid\_North_1) + flow(Mid\_North_2) - flow(North\_Mid_1) - flow(North\_Mid_2) = 0.001$

So basically Mid has extra 0.001, and North needs 0.001. It will be transfered via flow variables, and flow variables are restricted via capacity variables like following:

$s.t.: flow[i] <= capacity[i]$

Here what get problematic, which is: my capacity variables should be 0 or 1 (binary), in order me to calculate the correct costs. However it also reduces the computational efficiency.

Therefore I would like to convert this MILP into LP, without losing the binary speciality of capacity variable.

For example: If I add the following constraint to my optimization, it would work however then the problem becomes QP. I am not sure MILP or QP would be better.

$capacity[i] - capacity[i]^2 = 0$

Is there any way to turn this MILP to LP?

Answer 1

The idea to use the constraint

$$x(1-x) = 0$$

to make $x$ a binary variable is not new. It is not a good idea, however. This is a non-convex quadratic constraint. Here are some classes of quadratic solvers one may think of as candidates:

• Convex quadratic solvers. These solvers cannot be used. They will refuse the model, or will just get into problems.
• Local solvers will likely get stuck in a local optimum (often a bad one). Sometimes a multi-start approach may help preventing returning at least very bad points.
• You could use a global solver. These global NLP solvers often use a form of (spatial) branch-and-bound. So you would not gain anything. Actually, you lose linearity, which is heavily exploited by MIP solvers. So the non-convex NLP problem is way harder to solve than the linear MIP.