Skip to main content
7 votes

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 ...
Joseph O'Rourke's user avatar
5 votes

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 ...
kbala's user avatar
  • 151
5 votes
Accepted

What are the definable sets in Skolem arithmetic?

$\def\mr{\mathrm}$As it happens, quantifier elimination for Skolem arithmetic came up recently in my research. The concise description is that every formula $\phi(x_1,\dots,x_k)$ is in $(\mathbb N^{&...
Emil Jeřábek's user avatar
5 votes
Accepted

Correct way to conduct equilibrium scaling of linear/integer/MIP program

Regarding integer columns, it means the columns that correspond to integer variables. The $j\in \mathcal{I}$ notation makes that explicit. The idea is that scaling continuous variables preserves ...
RobPratt's user avatar
  • 5,219
5 votes

Maximally sparse integer solutions

Minimizing the sum of absolute values was covered in the comments. To instead minimize the number of nonzero variables, let $[\ell_j,u_j]$ be finite constant bounds on $x_j$, introduce binary ...
RobPratt's user avatar
  • 5,219
4 votes

Integer programming of free energy

Evaluating the minimum $\delta_k:=\min_{x\neq y}|f(y)-f(x)|$ over distinct strings $x, y\in \{0,1\}^k$ seems a hard diophantine problem. It is quite cheap to prove that $\delta_k$ is $O(1/k)$ and ...
Pietro Majer's user avatar
  • 57.9k
4 votes
Accepted

Sign Enumeration

The g.f. equals $$\frac1{1-y}\prod_{i=1}^n \left(xy^i + (xy^i)^{-1}\right).$$ That is, the number of solutions is given by the coefficient of $x^cy^b$.
Max Alekseyev's user avatar
4 votes

Bit complexity of Barvinok's algorithm

I looked into that at some point. The original paper says $N^{O(d^2)}$, where $d$ is the dimension and $N$ is the size of the input (sum of bit lengths of matrix entries in $A\overline x\le \overline ...
Igor Pak's user avatar
  • 16.8k
4 votes
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, ...
Konstantinos Kanakoglou's user avatar
3 votes
Accepted

Detection of gaps in binary vector through linear methods

OK, sorry for the delay. I just don't have too much free time nowadays. Let $a_0,\dots,a_{n-1}$ be your string. Note that for any $z=e^{it}$, we have $$ P_a(z)=a_0+a_1z+a_2z^2+\dots+a_{n-1}z^{n}=\...
fedja's user avatar
  • 60.9k
3 votes

Detection of gaps in binary vector through linear methods

Introduce binary variables $d_1,\dots,d_{N-1}$ and constraints: $$-d_i \leq a_i - a_{i+1} \leq d_i,\quad i=1,\dots,N-1$$ and $$a_1 + a_{N} + d_1 + \dots + d_{N-1} \leq 2.$$
Max Alekseyev's user avatar
3 votes
Accepted

On necessary condition for no integer points in polytope

The answer is $no$. In the plane, the circle of diameter $d$ greater than $1$ but smaller than $\sqrt2$ and centered at $({1\over2},{1\over2})$ contains no point with integer coordinates, and the ...
Wlodek Kuperberg's user avatar
3 votes

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 ...
Felipe Voloch's user avatar
3 votes
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 ...
Mark Schultz-Wu's user avatar
3 votes
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 ...
Jukka Kohonen's user avatar
3 votes
Accepted

Constructing an integer with small residues for two distinct primes in polynomial time

If such $m$ exists, then $m=up+a=vq+b$ for some $u,v\in O(T^{1/2+\epsilon})$ and $a,b\in O(\mathrm{polylog}(T))$. Then $up-vq=b-a$ and thus $\frac{p}q - \frac{v}u=\frac{b-a}{uq}$, implying that $\frac{...
Max Alekseyev's user avatar
3 votes

Fastest way to solve non-negative linear diophantine equations

Consider constraint programming for this. On my laptop, the constraint programming solver in SAS finds all the solutions in one second. Code: ...
RobPratt's user avatar
  • 5,219
3 votes

Fastest way to solve non-negative linear diophantine equations

Such problems are naturally expressed as finding integral points within a bounded polyhedron. There is a bunch of software available for this, e.g., Normaliz. Although my initial attempt to employ ...
Max Alekseyev's user avatar
3 votes

Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs

Below I show that $m$ cannot be constant. The given system of $m$ equations can be reduced to the case of $m=1$, that is, to a single equation: $$\sum_{j=1}^n y_j a'_{j} = \sum_{j=1}^n a'_{j}$$ where $...
Max Alekseyev's user avatar
3 votes

How quickly can this IQP or its MILP relaxation be solved

For binary $P$, we have $\min\{P_{k,i},P_{l,j}\} = P_{k,i} P_{l,j}$. In your linearization, you have introduced $r_{i,k,l,j}$ to represent this product. Because of the linear constraints $$\sum_k P_{...
RobPratt's user avatar
  • 5,219
3 votes
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-...
RobPratt's user avatar
  • 5,219
3 votes
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 ...
Ilya Bogdanov's user avatar
3 votes
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 ...
user64494's user avatar
  • 3,407
2 votes

basis of the lattice generated by the integer points inside a subspace of R^L

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)...
Kasper Dokter's user avatar
2 votes

Integer programming of free energy

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 ...
Pat Devlin's user avatar
  • 2,670
2 votes
Accepted

Integer points spanned by real, rational and integer combination of integer vectors

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 ...
Aaron Meyerowitz's user avatar
2 votes

Integer points spanned by real, rational and integer combination of integer vectors

This is only a partial answer. $\mathcal{L}_\mathbb{Q}=\mathcal{L}_\mathbb{R}$ for all $B$. Decompose $\mathbb{R}$ as a $\mathbb{Q}$-vector space into $\mathbb{Q}\oplus V$. Any $u\in\mathbb{R}^k$ can ...
MTyson's user avatar
  • 1,593
2 votes

Clarification on FPTAS optimization in a paper

Unfortunately, no. The form we use is very restrictive. The key is that the function $f(x)$ can be decomposed in a sign compatible way as $f(x) = g(x) h(x)$, where $g(x)$ is convex (or concave) and ...
Robert Hildebrand's user avatar
2 votes

Feasibility Mixed integer Linear programming with quadratic constraints?

Mixed integer Linear Program (MILP), i.e., with no quadratic constraints, is already in general NP hard, even without quadratic constraints. If the problem had only continuous variables, it could be ...
Mark L. Stone's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible