3
$\begingroup$

I'm a solving a model that has the following constraint:

$$ c_{p,n} = \sum_{s\in S}\sum_{i \in \{1,2,3\} } x_{p,s,i-1} x_{n,s,i}, \forall (p,n) \in C $$ where both the $c$ and $x$ variables are binary, $S$ is a set of indices. The indices $p$ and $n$ stand for "previous" and "next" and represent the same entity, i.e. they both belong to a set $T$, $p \in T$, $n \in T$. Their combinations are listed in $C$. The constraint above is used to know whether any combination of $p$ and $n$ is chosen. The variables $c_{p,n}$ appear in the cost function weighted by a cost $w_{p,n}\in \mathbb{R}$.

Other relevant constraints in the problem are: $$\begin{align} \sum_{s\in S}\sum_{i \in I} x_{p,s,i} &\leq 1, \forall p \in T \\ \sum_{p\in T} x_{p,s,i} &\leq 1, \forall s \in S, \forall i \in I \\ \sum_{p\in T} x_{p,s,i} &\leq \sum_{p\in T} x_{p,s,i-1}, \forall s \in S, \forall i \in \{1,2,3\}, \\ \end{align}$$ where $I=\{0,1,2,3\}$. Note that in the last constraint, both the left-hand-size and the right-hand-size can sum up to 1 at most (due to the second constraint).

The bilinear constraints above make my problem slow to solve in certain (large) instances. I tried to reformulate them using a linear reformulation. I created binary variables $y_{p,n,s,i}$ to replace the above variables $c$ and added the three following constraints: $$\begin{align} y_{p,n,s,i} &\leq x_{p,s,i-1}, \forall (p, n) \in C, \forall s \in S, \forall i\in \{1,2,3\} \\ y_{p,n,s,i} &\leq x_{n,s,i}, \forall (p, n) \in C, \forall s \in S, \forall i\in \{1,2,3\} \\ y_{p,n,s,i} &\geq x_{p,s,i-1} + x_{n,s,i} - 1, \forall (p, n) \in C, \forall s \in S, \forall i\in \{1,2,3\} \\ \end{align}$$

However, after doing so, the problem is even slower to solve on the same large instances mentioned before. The issue is that there are many more variables now (one order of magnitude more) and many more constraints. Gurobi, which is the solver I'm using, needs to spend a lot of time in the presolve phase making the problem smaller. Then, when solving the problem, it also spends a large amount of time in the root node and after that starts exploring the tree, where there are now many more nodes to explore, and thus it takes more time to reach the optimal solution.

I tried using a lot of different parameters of Gurobi to no avail. I also added my own cuts with information on the $y$ variables and on the model to help Gurobi but again I didn't succeed in speeding up the optimization.

Is there any other reformulation I could use to remove the bilinear constraint?

Improve this question
$\endgroup$
2
  • $\begingroup$ Some hints that might be worth trying are, 1) Check the problem if, it may have the integrality property. If so, you can relax the integrality and go ahead with an LP. 2) Why not try to solve the problem as a QCP directly instead of linearizing it? In some cases, Gurobi can solve the QCP faster than its equivalent MIP. 3) Some tips on this material-p311 would be helpful to reduce the model size. $\endgroup$
    – A.Omidi
    Commented Mar 11, 2023 at 12:55
  • $\begingroup$ My problem has more constraints and variables than the ones mentioned, but these bilinear constraints make the problem quite complex to solve in certain instances, so I focused on those in the question. Regarding your comments: 1) Yes, the problem is definitely MIP, I cannot relax the integrality; 2) Main reason: I am using a multi-objective approach and Gurobi wants linear objectives. Either case, I tried it and it didn't help; 3) Thanks, I'll check it out! $\endgroup$
    – cholo14
    Commented Mar 11, 2023 at 17:41

2 Answers 2

Reset to default
3
$\begingroup$

If the cost $w_{p,n}$ is nonnegative, you should be able to get by with no additional variables and the following linear constraints: $$ c_{p,n} \ge x_{p,s,i-1} + x_{n,s,i} - 1 $$ These arise from the following logical proposition: $$\bigvee_{s,i} (x_{p,s,i-1} \land x_{n,s,i}) \implies c_{p,n}$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Unfortunately, the cost $w_{p,n} \in \mathbb{R}$, I forgot to add it to the question. Anyway, I tried making each cost $w_{p,n}$ non-negative and implement your solution, but unfortunately I didn't notice any speed up $\endgroup$
    – cholo14
    Commented Mar 11, 2023 at 9:06
0
$\begingroup$

If sum $\sum_{s\in S}\sum_{i \in \{1,2,3\} } x_{p,s,i-1} x_{n,s,i}$ is $\le 1$ then you can modify as
$ y_{s}\le \sum_i x_{p,s,i-1} $.
$ y_s\le \sum_i x_{n,s,i}$
$\sum_i x_{p,s,i-1}+\sum_s x_{n,s,i}\le y_{s}+1 \ \ \forall (p,n) \in C \ \ \forall s$.

Elsif $\sum_s x_{n,s,i}\ge 1$
$x_{n,s,i}\le M\sum_i x_{p,s,i-1}$
Then for $c$ use only $x_{n,s,i}$

The above will reduce your constraints and thus size of the model.

In addition the following links from Gurobi may be helpful.
Link1,
Link2

Improve this answer
$\endgroup$
3
  • $\begingroup$ Your suggestion wouldn't work because while $\sum_{s}\sum_{i} x_{p,s,i-1} \leq 1$ and $\sum_{s}\sum_{i} x_{n,s,i} \leq 1$, the $s$ index for which $x_{p,s,i-1}$ and $x_{n,s,i}$ are non-zero are different. However, I only need to penalize the combination when the index $s$ is the same for both, hence the bilinear constraint in my question $\endgroup$
    – cholo14
    Commented Mar 12, 2023 at 9:02
  • $\begingroup$ Regarding the meaning of $p$ and $n$, they are different than $i$. For a specific $s$, if $p$ is assigned at an index $i$ and $n$ is assigned to the index $i+1$, then they $p$ and $n$ are an adjacent combination and thus take the meaning of "previous" and "next". However, $n$ could also be assigned to index $i$, not necessarily to index $i+1$. Moreover, $p$ and $n$ could be assigned to two different indices $s$, e.g. $s_1$ and $s_2$, both in index (let's say) $i$. Therefore, it could be that $x_{p,s_{1},i} = 1$ and $x_{n,s_{2},i} = 1$ $\endgroup$
    – cholo14
    Commented Mar 12, 2023 at 9:06
  • $\begingroup$ @cholo14 Ok then let's not sum over s. Check if it improves the speed. $\endgroup$
    – Sutanu Majumdar
    Commented Mar 12, 2023 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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