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 ...
- 145k
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^{&...
- 39.3k
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 ...
- 3,770
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 ...
- 3,770
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$.
- 26k
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 ...
- 51.3k
4
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 ...
- 141
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 ...
- 15.3k
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, ...
- 7,388
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 ...
- 29.5k
3
votes
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
3
votes
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
3
votes
Minimal solution of simultaneous congruences
Let $A_i$ be the set of allowed values for $a_i$. Then $x$ satisfying the system of congruences represents a zero of the following polynomial modulo $M$:
$$f(x) := \sum_{i=1}^n \frac{M}{p_i} \prod_{a\...
- 26k
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 ...
- 6,990
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.$$
- 26k
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}=\...
- 52.9k
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 ...
- 722
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 ...
- 3,012
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{...
- 26k
2
votes
Accepted
Find base of kernel with as many 0 as possible
It sounds like you're describing an instance of the "sparse null basis problem" – this was the title of what (I believe is) the seminal work on this problem, by Coleman and Pothen. You can find their ...
- 1,493
2
votes
Accepted
Algorithm to minimally connect line segments in Euclidean plane
Another way to solve the problem might be to reduce it to a traditional version of the TSP and then use a free, off-the-shelf solver like one of these. At the very least, it should be a relatively ...
- 3,306
2
votes
Sufficient condition for solvability of linear diophantine system
This can certainly be done in polynomial time using the
Smith
normal form (SNF) of $A$, which is a diagonal matrix $D = SAT$ for some
integer matrices $S,T$ of determinant $\pm 1$ (and thus whose ...
- 71.6k
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)...
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_{...
- 21.5k
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 ...
- 2,610
2
votes
Maximize the determinant of Boolean combinations of positive definite matrices
Given $n$ symmetric positive definite matrices $\mathrm W_1, \mathrm W_2, \dots, \mathrm W_n \in \mathbb R^{m \times m}$ and $s \in \mathbb N$, where $s < n$,
$$\begin{array}{ll} \text{maximize} &...
- 2,162
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 ...
- 1,563
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 ...
- 29.5k
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 ...
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 ...
- 1,397
Only top scored, non community-wiki answers of a minimum length are eligible