3

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

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
Clement
  • 2,252
  • 7
  • 13
  • 3
    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. – Mark L. Stone Mar 08 '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. – Clement Mar 08 '20 at 20:49

3 Answers3

2

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

RobPratt
  • 32,006
  • 1
  • 44
  • 84
  • 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. – Clement Mar 08 '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. – RobPratt Mar 08 '20 at 22:01
  • Ok, I can pretend not to accept arbitrarily low B-Values and see how the solver behaves. Thank you again! – Clement Mar 08 '20 at 23:09
2

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.

Simon
  • 1,132
  • 8
  • 16
1

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.

ooo
  • 1,589
  • 4
  • 12
  • 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. – Clement Mar 10 '20 at 17:22
  • b(i) >= w(i), I have updated the answer. – ooo Mar 11 '20 at 03:44
  • since you are trying to solve similar to minmax problem (I think so) that is why it is taking time. https://or.stackexchange.com/questions/143/why-are-integer-minimax-problems-hard – ooo Mar 11 '20 at 03:49