I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The constraints are:

$$ \sum_{m} z_{j,m} = 1 \quad \forall j$$ $$ (1-z_{i,m}) + (1-z_{j,m}) + w^1_{i,j} + w^2_{i,j} \geq 1 \quad \forall i,j, m$$

where all of the decision variables are binary and the only constraints $z_{j,m}$ appears is the above. Also, the indices $i$ and $j$ inherit from the same set.

P.S: The mentioned constraints are a portion of a scheduling model. When the problem is solved in the relaxed form, the variable $z_{j,m}$ tasks a fractional solution. Now, I would like to know if there is a way to reformulate these constraints in which after solving the problem as the relaxed form, the variable $z_{j,m}$ still takes an integer value ($0$ or $1$).

  • $\begingroup$ Is the second constraint maybe for $i<j$ or $i\not= j$? $\endgroup$
    – RobPratt
    May 12 at 1:53
  • $\begingroup$ Dear @RobPratt, yes. It is for $i \lt j$. $\endgroup$
    – A.Omidi
    May 12 at 4:34
  • $\begingroup$ I don't understand what you mean by "in which one can relax... and the solution still being". Can you rephrase that? Perhaps break it apart into multiple sentences, so the structure of the grammar and reasoning is clearer. Also, please don't put clarifications/corrections in the comments. Instead, please edit the question to address the feedback and include all information in the post, and then flag the comment as 'no longer needed'. $\endgroup$
    – D.W.
    May 14 at 9:51
  • $\begingroup$ @D.W., I am unsure If the question really being unclear, but I will try rephrasing some parts. $\endgroup$
    – A.Omidi
    May 14 at 13:42
  • 1
    $\begingroup$ Rather than using "P.S.", please edit the question so it reads well for someone who encounters it for the first time, flows in a logical order, and the information is presented in a manner that is appropriate for a first-time reader. What does "tasks" mean? Do you mean "takes"? Please indicate whether the $w$'s are variables or constants, and incorporate the restriction $i<j$ into the question. Please edit the question to incorporate all relevant information into the question then flag comments as 'no longer needed' once you've done so. $\endgroup$
    – D.W.
    May 14 at 18:31


Your Answer

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