3
votes
How to identify constraints that make problem not solvable in polynomial time?
You can also see that the second part, constraints 13 to 16, contains more variables (IxI), more constraints (IxIxMxM) and a big M formulation (which is not good for MIP resolution). The first part (...
- 53
3
votes
How to identify constraints that make problem not solvable in polynomial time?
The motivation is the same as in the Jain and Grossmann reference [59]. After assigning jobs to machines, the problem decomposes into a separate feasibility subproblem for each machine. Jain and ...
- 29.8k
2
votes
Linearizing if else conditions in ILP
Besides @RobPratt's answer, the first condition would be (for simplicity I omitted indices $i$ and $j$ and continued with only two $y$ variables:
$$ x \implies (y_1 \oplus y_2) $$
$$ \lnot x \lor (y_1 ...
- 8,187
2
votes
Accepted
Linearizing if else conditions in ILP
Your first constraint enforces more than was asked. When $X_{ij}=0$, it forces $\sum_k Y_{jk}=0$, hence $Y_{jk}=0$ for all $k$. To enforce only $$X_{ij}=1 \implies \sum_k Y_{jk}=1,$$ you can instead ...
- 29.8k
Only top scored, non community-wiki answers of a minimum length are eligible