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

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

Accepted

### programming to compute kernel quotient image of a $\mathbb{Z}$-module endomorphism

Ok, not really beautiful, but the lines below are a simple SAGE implementation of the map $\partial$, computing both the representing matrix and the elementary divisors. In the implementation I ...

### Algorithm that solves every Mixed Integer Linear Program (to optimality)?

I sometimes read the claim that Gomory cuts alone (without any branch-and-X) are sufficient for finding integer solutions to linear programs in a finite number of steps. E.g. at the bottom of page 2: ...

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

Although the brute force solution of Alex is certainly possible, it is not very efficient. It would be easier in practice to use Hermite's normal form: First, find a linear map $A \in \mathbb{Z}^{(L-K)... 2 votes Accepted ### On linear integer inequalities with infinitely many solutions Let the constraints be numbered 1 to$m$. Let the$i$th constraint be$a^{(i)}\cdot x\le b$. Let$S$be the set of solutions. Inductively refine the constraints as follows: either there are$\limsup_{...
I'm confused. Why not $x = 0$ and $y=(0, 0, \ldots , 0, 1)$? This has $f(y) - f(x) = e -1$, which is clearly best possible [though not unique]. (As you note, $f$ is an injection, so different ...
We always have $\mathcal L_\Bbb Q=\mathcal L_\Bbb R:$ For any particular $v \in\Bbb Z^n$ consider how we determine $\{u \in \Bbb R^n \mid uB=v\}.$ The method, if the set is nonempty, will yield one or ...