# Tag Info

### Is Binary Integer Linear Programming solvable in polynomial time?

Often called Binary Integer Programming (BIP). Wikipedia: Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and ...
• 150k

### Under what conditions does an Integer Programming problem run in polynomial time?

The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed ...
• 151
Accepted

• 16.8k
Accepted

### Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way

Copying from http://mathworld.wolfram.com/SumofSquaresFunction.html: To find in how many ways a positive integer $n>1$ can be expressed as a sum of $k=2$ squares ignoring order and signs, ...
Accepted

• 5,219
Accepted

### Benefit of adding a trivial constraint to ILPs

This question is addressed in a few OR StackExchange questions: https://or.stackexchange.com/questions/419/feeding-known-lower-bounds-to-solvers https://or.stackexchange.com/questions/3777/how-to-...
• 5,219
Accepted

### Existence of some lattice path connecting all given lattice paths

Let us draw a checkered table with $N$ columns and $n$ rows, such that the cell $(i,j)$ (that is, the one in the $i$th row and the $j$th column) contains the number $q_i^j$. Paint all cells with ...
• 22.6k
Accepted

### Direct algorithm for an integer program

This is an extremely difficult non-linear integer programming problem. The difficulty consists in the restriction $h_1^{x_1}-h_2^{x_2}=kp$ which is hardly handled by known methods. I don't know any ...
• 3,407