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 (...
Issouf's user avatar
  • 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 ...
RobPratt's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
RobPratt's user avatar
  • 29.8k

Only top scored, non community-wiki answers of a minimum length are eligible