# 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 ...
• 145k
Accepted

• 15.3k
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, ...

### An interesting problem which I think only needs elementary number theory

I am not sure about only using elementary number theory but here is an approach using the Bateman-Horn conjecture. Maybe one can get by with a bit less using sieve methods but I will leave that to the ...
• 29.5k
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 ...
• 16.5k

### 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: ...
• 2,406

• 52.9k
Accepted

### Gröbner basis via integer programming

ILP is $NP$-complete, while computing a Grobner Basis is $EXPSPACE$-complete. As one has the containments $NP\subseteq PSPACE\subsetneq EXPSPACE$, one should expect that you can reduce ILP to ...
• 722
Accepted

### Reliability of ILP approach to number-theoretic optimization

Well, the question is broad, but let us address at least some of it. Q1. What is the cause of failure for ILP solvers in this problem? Let's concentrate in the GLPK failure with $n=27$. Here is a ...
• 3,012
Accepted