New answers tagged

4 votes

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

It is false. Consider the following (2 variable) LP: \begin{align} \max&& 3x+2y & \\ && 2x+y &\leq 2 \\ && 0 \leq x &\leq 1 \\ && 0 \leq y &\leq 1 \end{...
NaturalLogZ's user avatar
2 votes

Hamiltonian Cycle as an integer linear programming problem

Here's a simple ILP that nobody has mentioned yet. Given the undirected graph $G=(V, E)$, use binary variables $\pi_{iv}$ for $(i, v)\in [n]\times V$, where $n=|V|$. Variable $\pi_{iv}$ indicates ...
Neal Young's user avatar
  • 10.8k

Top 50 recent answers are included