2
$\begingroup$

I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?

But the answers to that questions didn't help me find a solution for my problem.

I have the following constraints

\begin{align}\sum_{i=1}^{N}\sum_{k=1}^{M}{{(x_{i,k,t}\cdot r_i)}}&\le C_t\\ r_i&\le R_i \end{align} where $r_i\ge 0$ is an integer variable, $x_{i, k, t}\in\{0,1\}$ is a binary variable, $C_t$ and $R_i$ are known numbers.

Can I linearize this?

Some background: At period $t$ I have a capacity of $C_t$ for the resources. A certain number of resources $r_i$ perform job $i$. $x_{i,k,t}$ tells us, if job $i$ is performed at time $t$ with a different type of resource $k$.

$\endgroup$
  • 1
    $\begingroup$ The answers in the link you posted are relevant. $\endgroup$ – Kuifje Apr 24 at 12:29
  • 1
    $\begingroup$ Why doesn't the solution of how to linearize the product of integer and binary variables help you.? Just apply it to each term within the double summation. $\endgroup$ – Mark L. Stone Apr 24 at 12:29
4
$\begingroup$

The linked answer depends on an equality constraint that doesn’t appear here. You can still use the same idea of introducing a nonnegative variable, say $y_{i,k,t}$, to represent the product. Because your constraint is $\le$, you need to enforce only that $$x_{i,k,t}=1\implies y_{i,k,t}\ge r_i,$$ which you can do with a big-M constraint: $$r_i-y_{i,k,t}\le R_i (1-x_{i,k,t})$$

| improve this answer | |
$\endgroup$
  • $\begingroup$ Seeing it now, the problem was the actually not so difficult formulation of the relationship between x and y. Thanks for help. - eddited the title: "Inequality" $\endgroup$ – Dav Apr 24 at 13:35

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.