Questions tagged [integer-programming]
Integer programming regards optimization problems, where one seeks to find integer values for a set of unknowns, that optimizes the objective function. A common subset of this type of problems are integer linear programming problems, where all inequalities, equalities and the objective function are linear in the unknowns.
198 questions
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
0
votes
1
answer
60
views
Optimizing sum of discrete minimum
Please consider the following optimization problem: Given a fixed positive natural $n < N$, and a set of functions $f_i$ over a finite domain of nonnegative outputs, s.t. $1 \le i \le N$, then we ...
- 103
1
vote
0
answers
67
views
System of linear diophantine equations with many small solutions?
Let $n$ be positive integer, $k$,$B$ fixed positive integers.
Let $f_i(x_1,x_2...x_n)$ be a system of $n-k$ linearly independent linear
equations over the integers.
Let $S(f_i,k,B)$ be the set of ...
- 25.4k
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
2
votes
0
answers
95
views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
- 13.9k
1
vote
0
answers
40
views
learning about split cut (Integer Programming)
Here is a part of Integer Programming (Graduate Texts in Mathematics, 271) 2014th Edition.
In lemma 5.9, aiming at showing that a finite number
of splits ${(\pi, \pi_0)}$ are sufficient to generate ...
- 11
3
votes
1
answer
329
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
- 13.9k
0
votes
1
answer
40
views
Lagrangian duals for the generalized assignment problem
I'm new to integer programming and I'm reading the book GTM 271: Integer Programming written by Michele Conforti, Gerard Cornuejols and Giacomo Zambelli.
I have trouble solving exercise 8.6:
Consider ...
- 1
1
vote
2
answers
192
views
Direct algorithm for an integer program
Let $p$ be a prime and let $h_1,h_2\in\{1,2,\dots,p-1\}$ be integers.
Is there any direct algorithm to solve for following in polynomial in $\log p$ time?
$$\min (x_1-x_2)^2$$
$$x_1,x_2,k\in\mathbb Z$$...
- 13.9k
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 101
3
votes
2
answers
215
views
Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$
Is there a closed-form solution for
$$\max_D \operatorname{Tr}(ADBD)$$
where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...
- 433
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 3
3
votes
0
answers
162
views
Why is this constrained quadratic-over-linear integer program separable?
Consider the following splitting problem. Given $Y$ balls of which $X\leqslant Y$ of them are blue balls. The goal is to split the balls by placing them in $K$ baskets based on the following quadratic-...
- 31
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
2
votes
1
answer
278
views
Can we say this nonlinear integer programming problem is NP-hard?
I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...
- 21
3
votes
1
answer
149
views
How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?
For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by
$$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...
- 745
0
votes
1
answer
82
views
Algorithm to find a number B with same modulus as A with prime P and specific binary positions set to zero
Given a prime $P$, an integer $A$ $(0\leq A<P$), and a set of legal positions (encoded as a binary mask $\text{mask}$), is there an efficient algorithm to find a number $B$ that has the same ...
- 3
1
vote
1
answer
111
views
Existence of some lattice path connecting all given lattice paths
My daily work concerns analysis on metric spaces and some time ago it turned out that the problem I am dealing with boils down to a certain combinatorial problem. I've checked a lot of examples and it ...
- 137
2
votes
0
answers
221
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
- 13.9k
1
vote
0
answers
96
views
On optimizing a multivariate quadratic function subject to certain conditions
The problem is to maximize $f(x_1,x_2,\cdots,x_n)=\sum\limits_{i=1}^{n}\Big(x_i-k_i\Big)^2$ for $n\ge 3$ subject to the conditions (1) $\sum\limits_{i=1}^{n}x_i=\sum\limits_{i=1}^{n}k_i\le n(n-1)$ ...
- 61
0
votes
0
answers
122
views
Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x]$ factoring?
There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.
Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in ...
- 13.9k
3
votes
0
answers
144
views
Hemisphere containing the maximum number of points scattered on a sphere
Consider a set of points $x_1, \ldots,x_n$ on $\mathbb{S}^{k-1}$ (the unit sphere in $\mathbb{R}^k$). The goal is finding the hemisphere which contains the maximum number of $x_i$'s. Basically, we ...
- 127
3
votes
0
answers
111
views
The matrix representation of an interval graph
It is well-known that many classes of graphs have matrix representations that can be written concisely. For example,
The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
- 4,049
0
votes
1
answer
36
views
Benefit of adding a trivial constraint to ILPs
let ILP be an integer linear program with constraints-matrix $\boldsymbol{\mathrm{M}}\in\mathbb{Z}^{m\times n}$ and cost vector $\boldsymbol{\mathrm{c}}\in\mathbb{Z}^n$,
${\boldsymbol{\mathrm{x}}^*}\...
- 13.2k
0
votes
1
answer
93
views
How quickly can this IQP or its MILP relaxation be solved
Let $A\in\{0,1\}^{(n,n)}$ be a $n$ by $n$ boolean matrix (in particular think of an adjacency matrix of a graph), and consider the following optimization problem:
$$\begin{align*}&&\max_{P\in\{...
- 71
4
votes
0
answers
104
views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is in ...
- 13.9k
1
vote
2
answers
204
views
Only trivial solutions to system of linear diophantine equations possibly related to hamiltonian cycles in graphs
This might be related to counting hamiltonian cycles.
@Peter Taylor gave negative result about the one dimensional case, but we believe his attack is
not directly applicable to this question.
Given ...
- 25.4k
0
votes
3
answers
827
views
Integer linear constraint(s) for y= x1 XOR x2 [closed]
Is there any way to convert $y=x_1~ \text{XOR} ~x_2$ to linear constraints? It means we write some linear relations with:
if $x_1=x_2 =0$ or $x_1=x_2=1$ $\to$ $y=0$,
else, $y=1$?
- 25
2
votes
1
answer
181
views
Only trivial solution to a pair of constrained linear diophantine equations
Given positive integer $n$, we are looking for a set
of $n$ positive integers $a_i$.
The following linear integer program must have only
the trivial integer solution of all ones.
$0 \le x_i \le \frac{...
- 25.4k
0
votes
2
answers
428
views
Fastest way to solve non-negative linear diophantine equations
Let $A$ be a matrix in $M_{n \times m}(\mathbb{Z}_{\ge 0})$ without zero column. Let $V$ be a vector in $\mathbb{Z}_{> 0}^m$.
Question: What is the fastest way to find all the solutions $X \in \...
1
vote
0
answers
86
views
Integer programming using the Steinitz lemma
I am trying to implement an algorithm that I read on the paper entitled: "Proximity results and faster algorithms for integer programming using the Steinitz lemma", published by Friedrich ...
- 111
3
votes
1
answer
126
views
Maximally sparse integer solutions
Suppose I have a system of $n$ inhomogeneous linear equations in $m$ variables, where $n$ and $m$ are of the order of a few hundred, and $m$ is significantly larger than $n$. All the coefficients are ...
- 56.9k
0
votes
1
answer
87
views
Constructing an integer with small residues for two distinct primes in polynomial time
Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer
Is it ...
- 13.9k
0
votes
1
answer
323
views
Correct way to conduct equilibrium scaling of linear/integer/MIP program
I would like to scale my linear/integer program and also mixed-integer program using the equilibrium scaling method. I have worked on two research papers and one research book. However, they did the ...
- 21
5
votes
2
answers
377
views
Reliability of ILP approach to number-theoretic optimization
This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...
- 34.4k
2
votes
0
answers
119
views
Modified quadratic assignment problem
Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that
$$\left\Vert Y^{T}...
- 133
0
votes
1
answer
100
views
Formulating a problem as a mixed-integer conic program
I have the following integer optimisation problem, and I wonder whether it can be reformulated as a conic program that can be solved with, e.g., Mosek. Suppose the $n$-dimensional vectors $a, b$ and $...
- 13
1
vote
1
answer
179
views
Adding valid cuts for integer feasibility problem under Benders decomposition framework?
Traditional infeasibility cut is derived under the assumption that the feasibility problem is LP instead of ILP and relies on the dual form of the LP.
Is there a systematic way of adding valid cuts ...
0
votes
0
answers
40
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 13.2k
1
vote
0
answers
37
views
Sum of all integer binary solutions of a TUM linear system
I have the following problem: $A x = b$ where $A$ is a $m \times n$ total unimodular matrix (TUM) with entries in $\{0,1\}$ and $b$ is a $m$-vector of strictly positive integers. Let $\mathcal X$ be ...
- 11
1
vote
1
answer
495
views
Knapsack like problem with nonnegative weight constraint
I am dealing with a knapsack-like problem with one difference from the conventional problem: the “weights” can be positive or negative and the constraint is $\sum w_i x_i \ge 0$ instead of $\sum w_i ...
- 13
0
votes
1
answer
143
views
Integer programming for bin covering problem
I encounter an integer programming problem like this:
Suppose a student needs to take exams in n courses {math, physics, literature, etc}. To pass the exam in course i, the student needs to spend an ...
1
vote
1
answer
303
views
Is this variant of knapsack problem strongly NP-hard?
Suppose we have a sequence of containers each of which contains multiple items. Each item $I_i$ is associated with an nonnegative weight $w_i$, a nonnegative value $v_i$, and $I_i(C)$ denotes the ID ...
2
votes
0
answers
76
views
Polyhedron coordinate bound
Given a polyhedron
$$Ax\leq b$$
where we assume $A\in\mathbb Q^{m\times n}$ and $b\in\mathbb Q^{m}$ and it takes $L$ bits to represent the inequalities what is a good bound on the quantity $\|y\|_\...
- 13.9k
3
votes
0
answers
50
views
Modular counting of integral points under sparse non-negativity
Given a polyhedron
$$Ax\geq b$$
where every entry of $A,b$ are non-negative and $A\in\{0,1\}^{m\times n}$ and there are $O(1)$ (say $\leq8$) non-negative entries per row of $A$ is it possible to ...
- 13.9k
1
vote
1
answer
254
views
Knapsack problem with capacity constraint
The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
5
votes
0
answers
241
views
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at Theoretical Computer Science SE
A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$....
- 123
1
vote
1
answer
373
views
Knapsack problem with value range constraint
The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...