All Questions

The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...

Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...

There is a problem that I can not solve. Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...

Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP) $$ \begin{split} f^* = &\max \; ...

My question is motivated by the fact, that among other ways, it is possible to restrict a variable to two discrete values, e.g. the prototypical $0$ and $1$, via an optimization constraint: $$\max(\...

Suppose I am solving the generalized assignment problem, so that I am given matrices $U$ and $W$ and a vector $c$ (all three of which have, say, positive entries), and I want to solve $$\text{...