3
$\begingroup$

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$.

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Mar 8 '20 at 19:58
  • $\begingroup$ 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. $\endgroup$ – Clement Mar 8 '20 at 20:49
2
$\begingroup$

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.$$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Clement Mar 8 '20 at 21:58
  • $\begingroup$ 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. $\endgroup$ – RobPratt Mar 8 '20 at 22:01
  • $\begingroup$ Ok, I can pretend not to accept arbitrarily low B-Values and see how the solver behaves. Thank you again! $\endgroup$ – Clement Mar 8 '20 at 23:09
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:
    opt_model.add_constraint(B[i] >= W[i])

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – Clement Mar 10 '20 at 17:22
  • $\begingroup$ b(i) >= w(i), I have updated the answer. $\endgroup$ – ooo Mar 11 '20 at 3:44
  • $\begingroup$ 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/… $\endgroup$ – ooo Mar 11 '20 at 3:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.