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

| improve this answer | |
$\endgroup$
  • $\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 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 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 at 23:09
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.

| improve this answer | |
$\endgroup$
  • $\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 at 17:22
  • $\begingroup$ b(i) >= w(i), I have updated the answer. $\endgroup$ – anoop Mar 11 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$ – anoop Mar 11 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.