New answers tagged combinatorial-optimization
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