New answers tagged

4

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{...


2

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 ...


Top 50 recent answers are included