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 ...
- 154k
6
votes
Nonexistence of short integer program sequence which generates squares
If you can do this efficiently, you can factor integers efficiently.
Set $X-Y=N$.
If $X=u^2,Y=v^2$ then $(u^2-v^2)=(u-v)(u+v)=N$ will give the factorization of $N$.
To avoid the trivial solution, add ...
- 25.9k
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^{&...
- 51.8k
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 ...
- 5,760
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 ...
- 5,760
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, factor ...
- 7,946
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 ...
- 17.5k
4
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 ...
- 4,903
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 ...
- 2,486
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{...
- 39.4k
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:
...
- 5,760
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 ...
- 39.4k
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 $...
- 39.4k
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_{...
- 5,760
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-...
- 5,760
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 ...
- 25.2k
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 ...
- 3,583
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
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,547
2
votes
Accepted
How do I solve this integer programming problem with non convex constraints?
The nonlinear constraint
$$(L_{ij} - D_{ik})(L_{ik} - D_{ij}) \le 0$$
is a disjunction:
$$\left(L_{ij} - D_{ik} \ge 0 \wedge L_{ik} - D_{ij} \le 0\right) \bigvee \left(L_{ij} - D_{ik} \le 0 \wedge L_{...
- 5,760
2
votes
Accepted
Constructivity of two problems on a standard simplex?
You make an erroneous assumption in your question, as already in dimension 1 you need LLPO to know that the maximum is actually attained at some point.
We work constructively.
Theorem: LLPO is ...
- 52.1k
2
votes
Accepted
Knapsack problem with capacity constraint
I assume that your constraint should read $\sum_{h=1}^i p_h w_h < B < 2 \sum_{h=1}^i p_h w_h$, not $\sum_{h=1}^i w_h < B$ otherwise the trivial solution $p_h \equiv 1$ always applies.
There ...
- 3,734
2
votes
Accepted
Knapsack problem with value range constraint
It is easy to enforce this constraint for a generic knapsack problem.
Indeed, it is enough just to multiply all $w_h$ and $B$ by $c:=\max_h \frac{v_h}{w_h}$. Then for any $h$,
$$v_h = \frac{v_h}{w_h} ...
- 39.4k
2
votes
Integer linear constraint(s) for y= x1 XOR x2
You can derive the desired constraints somewhat automatically via conjunctive normal form as follows:
$$(\lnot x_1 \land \lnot x_2) \implies \lnot y \\
\lnot (\lnot x_1 \land \lnot x_2) \lor \lnot y \\...
- 5,760
2
votes
Integer linear constraint(s) for y= x1 XOR x2
Under the constraints $x_1,x_2,y\in\{0,1\}$, the equality $y=x_1\oplus x_2$ is equivalent to
$$\begin{cases}
y \geq x_1 - x_2, \\
y \geq x_2 - x_1, \\
y \leq x_1 + x_2, \\
y \leq 2 - x_1 - x_2.
\end{...
- 39.4k
2
votes
Accepted
Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs
Yes, we can get $\exp(\omicron(n))$.
Assume for a moment that $n$ is a perfect square and $m=\sqrt{n}$.
The general case is essentially the same, just a bit more complicated.
The idea is to partition ...
- 186
2
votes
Accepted
Algorithm to find a number B with same modulus as A with prime P and specific binary positions set to zero
If you interpret the bit mask as encoding a finite set $S = \{2^{b_i}\}$ of powers of $2$, you are precisely asking whether there exists a subset of $S$ which sums to $A$ modulo $p$. This is known as ...
- 13.6k
2
votes
Accepted
How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?
Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize
$$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$
subject to $A < B < C$ ...
- 5,760
2
votes
Accepted
How to integrate an indicator function/constraint into the cost function of a linear program?
I will simplify the notation to illustrate the idea. You want to minimize $$\sigma \max\left(\sum_{i,j} d_{ij} x_i x_j - \alpha, 0\right).$$
Introduce binary decision variable $y_{ij}$ to represent ...
- 5,760
Only top scored, non community-wiki answers of a minimum length are eligible