# How can I direct the behaviour of a MILP Solver

I have a model involving constraints of the form $$d(i) = a \cdot W(i) + b \cdot B(i)$$ where $$W(i)$$ is binary and $$d(i), B(i)$$ are positive reals.

The objective function is $$\max\sum B(i)$$.

While solving the problem, the solver sets some $$W(i)$$ to $$1$$ but keeps the corresponding $$B(i)$$ at zero. In other words the solver 'prefers' to fulfill the constraint $$d(i) = a \cdot W(i) + b \cdot 0$$. Advancing towards the optimum is extremely slow.

The question is, how can I "persuade" the solver to set $$B(i)$$ well above $$0$$ whenever it decides to set $$W(i)$$ to $$1$$? Because I am asking to maximize $$\sum B(i)$$ I would expect that the solver does what I am asking. The solver should understand that it can only reach the optimum, if it set the values $$B(i)$$ to appropriate values $$> 0$$.

• You haven't provided much information. For example, if b > 0 and a >,d(i), W(i) must be zero to be feasible. So I suggest you provide more info about your complete model. Once readers understand what your model is, they may be in a better position to make suggestions about solver strategy. Mar 8 '20 at 19:58
• a, b are preset constants that cannot make the equation be infeasible, whatever the value of W(i) is. An additional feature of the model is that, B(i) = 0 if W(i) = 0. But this makes the behavior of the solver even more strange. The only rational behavior of the solver should be, make B(i) positive whenever W(i) = 1. Mar 8 '20 at 20:49

If "well above 0" means $$\ge m_i$$, you can impose the constraint $$B(i)\ge m_i\cdot W(i)$$ to enforce $$W(i)=1 \implies B(i) \ge m_i.$$

• Hi Rob. Unfortunately this is not the case. The constraint is: 0<= B(i) <= W(i) . M(i), B(i) = 0 if W(i)=0 and the solver has to determine the optimal value of B(i) lying between 0 and M(i) if W(i) = 1. What I don't like is that the solver sets B(i) = 0 when W(i) = 1, because this is certainly not optimal. The solver should only set B(i)=0 if W(i)=0. This is the only situation, where B(i) = 0 makes sense. The incentive for the solver to set B(i) > 0 is there, since it has to maximize the sum of B(i) but the solver doesn't react to that. Well, I will see if I can do something about it. Mar 8 '20 at 21:58
• My suggestion is to add the constraint I provided, in addition to your original constraints. It will force the solver to return a solution that behaves the way you want. Mar 8 '20 at 22:01
• Ok, I can pretend not to accept arbitrarily low B-Values and see how the solver behaves. Thank you again! Mar 8 '20 at 23:09

Most solvers will accept additional information about variables like $$B(i)$$. Some may be useful. Here are some examples for Gurobi, which let you influence the search:

• You can use the parameter BranchDir to tell Gurobi to always first explore the "up" branch. This means that non-zero values will be tried first. Unfortunately, this is a global setting - so Gurobi will always try non-zero values first for all variables.
• The variable attribute VarHintVal let's you provide hints of "expected optimal values" for variables. If you're certain that $$B(i) = 7$$, you can set b[i].VarHintVal = 7.
• Setting the a high BranchPriority instructs the solver to first branch on a specific variable. The solver will try non-zero values sooner for variables with a high branch priority.

Other solvers offer similar settings with similar effects.

Here is the small implementation with one extra constraint

$$B(i) \geq W(i)$$

import docplex.mp.model as cpx
import pandas as pd

opt_model = cpx.Model(name="MIP Model")
set_n = range(5)
W = {i: opt_model.binary_var(name="W_{0}".format(i)) for i in set_n}
B = {i: opt_model.continuous_var(name="B_{0}".format(i)) for i in set_n}
d = {i: opt_model.continuous_var(name="d_{0}".format(i)) for i in set_n}

a = 1
b = 5

objective = opt_model.sum(B[i] for i in set_n)

for i in set_n:

for i in set_n:
opt_model.add_constraint(d[i] == a * W[i] + b * B[i])

opt_model.maximize(objective)

opt_model.solve()


if you have $$a,b >0$$, you will always get $$B(i)$$ as 1.

• This constraint doesn't solve the problem. If W(i) = 1 --> B(i) <= 1 is not what I want. I introduced the constraint: d(i) <= B(i) . BigM So, if B(i) = 0 then W(i) = 0 and d(i) = 0. If B(i) > 0 then W(i) = 1, and d = a . 1 + b . B(i) However, the solver behaves still the same way. It follows a solution path, which is extremely slow. Mar 10 '20 at 17:22
• b(i) >= w(i), I have updated the answer.
– ooo
Mar 11 '20 at 3:44
• since you are trying to solve similar to minmax problem (I think so) that is why it is taking time. or.stackexchange.com/questions/143/…
– ooo
Mar 11 '20 at 3:49