# Tag Info

You could try and get rid of variables $Y_{p,t,j,c}$: remove constraints $(6)-(7)$; constraints $(6)$ simply link $x$ and $Y$ variables, so removing them should not have any impact on the feasibility of the solution (assuming you remove $Y$ variables) ; constraints $(7)$ are not mandatory if my understanding is correct replace constraints $(5)$ by $$\sum_{... 2 If I understand the problem correctly, it might be modeled as a variant of the resource-constrained project schedule in which you have some parallel machines and the tasks should be performed with some limitation. From the above-given data, some noisy things should be considered. First, limiting the start time of a task by being started from the same point ... 1 The question can be understand as determining the truth value of$$(\forall \text{assignments}: \text{relaxation feasible} )\implies \text{problem has integer solution}.$$However since setting up many LP problems is more expensive then solving a small MILP (or even cheaper 1-in-3 SAT). I instead try to show the opposite:$$(\forall \text{assignments}: \text{...
If I am not mistaken the answer is NO unless $P=NP$. We can reduce Exactly-1 3-satisfiability to your problem. For a proof of 1-IN-3SAT is NP-complete see NP-Completeness of 3SAT, 1-IN-3SAT and MAX 2SAT. Given an instance $I$ of the Exactly-1 3-satisfiability problem. For each variable $x_i$ check whether there is a solution setting it to $1$ and $0$. This ...