The integer-programming tag has no wiki summary.
0
votes
0answers
53 views
find polynomials of special type
This is a question I asked in MSE, see here, but no answer has appeared. I think it might be suitable for MO.
Let $p_i$, $i=1,2,3$ be polynomials in the ring $\mathbb{Z}[y,z]$ such that
...
1
vote
1answer
99 views
Finding integer points inside of a parallelogram
Suppose $P = \{p_1,\ldots,p_4\} \in \mathbb{R}^2$ defines a quadrilateral (here, specifically, a parallelogram). In the particular case I'm dealing with, I know that there exists at least one point ...
2
votes
0answers
78 views
existence of lattice point in polytope
This question was probably asked before but here goes. I have a convex polytope given by $Ax\leq b$ for a specific integer matrix $A$ and integer vector $b$. I need a simple method/result on how to ...
3
votes
0answers
106 views
Beating Kadane's Algorithm
I am seeking some reference on already existing work for the following problem.
Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
1
vote
2answers
61 views
LP constraint enconding
I have an objective function to be maximized
$obj(x) = \sum_i \gamma_i x_i$ with $x_i \in \mathbb{R}$
With multiple constraints of the form:
$\min_{y \in 0,1} (\sum_{i \in A} \alpha_i x_i + \sum_{i ...
1
vote
1answer
76 views
Separation of Anti-Hole Inequality
Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.
An induced subgraph $H$ of $G$ is called an odd-antihole ...
1
vote
0answers
56 views
What is the solution to \min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}
(I've posted this question at Math.SE but got no answer, so I hope I can get a solution here.)
This problem looks familiar, but I don't remember its solution:
$$ \min_k \ \ \frac{b^k/n}{\lfloor ...
5
votes
2answers
412 views
Area of a lattice polygon in terms of its width
Let $M$ be a lattice polygon on a plane (i.e. its vertices are integer points $(i,j)\in\mathbb Z^2$).
Let us define lattice width in a direction $v=(m,n)\in\mathbb Z^2$ as $w_v(M)=\max\limits_{x,y\in ...
1
vote
0answers
156 views
Reference Request for Integer factorization with LP/ILP
Have there been attempts to factor integers with Linear Programming?
Searching the internet suggests that for Integer Factorization only Number Theoretic algorithms, like sieves, are taken into ...
1
vote
2answers
121 views
Brute force lattice problems
What are the easiest brute force algorithms for solving closest and shortest vector problems?
I want to find an arbitrary, but small ($\lesssim 20$) number of lattice vectors closest to a given ...
0
votes
0answers
141 views
If-then-else on mixed linear integer programming
Hi all.
Let A,B and C be three real variables. I must write the following if-then-else condition with linear inequalities:
if A≤B then C=0 else C=B-A
Is this possible by adding a single binary ...
0
votes
1answer
543 views
If then condition on mixed linear integer programming
Hi all. Let $a$ and $b$ be two real variables such that $0 \le a \le a_{max}$ and $0 \le b \le b_{max}$. I must write the following if-then-else condition with linear inequalities:
if $a < ...
10
votes
2answers
680 views
Efficient computation of integer representation as sum of three squares
Hello,
recently I've been studying the problem of integer representation as sum of three squares. Most of the articles that I've found study the function $r_m(n)$ which counts the number of ...
0
votes
0answers
136 views
LP relaxation for ILP\IP (integer linear programming)
I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
0
votes
0answers
127 views
$\ell_o$ Minimization (Minimizing the support of a vector)
I have been looking into the problem
$\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
2
votes
3answers
406 views
is there a solution to system of linear Diophantine equations?
I have a matrix A \in Z^{n \by m}, where m > n and a vector b \in Z^n. Then, under what conditions does an integer solution exist to the equation
Ax = b.
Is there a way to bound the norm of the ...
2
votes
1answer
338 views
sum of maxima vs the maximum of the sum
Consider the following integer program
$$
\begin{align}
\max &\sum\nolimits_{i}\sum\nolimits_{j} U_i(j)\cdot x_{i,j}\\
\text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant ...
0
votes
0answers
140 views
Maximum subset of set of Integers with minimum distance
Hi, i have a set of integers for example: {0,1,3,100,102} and i am looking for a maximum subset in which all elements have a minimum distance to all elements (or the "next" doesnt matter i guess) for ...
4
votes
0answers
258 views
Matching a binary matrix
Given a MxN 0-1 matrix D, with the property that
both M and N are odd numbers
its row sums and column sums in the $\mathbb{Z}_2$ field are all equal to the same number (0 or 1).
How do we find M ...
0
votes
1answer
209 views
Sherali-Adams relaxation
I am trying to find a book or a paper, which explains, how and why the Sherali-Adams relaxation method works. The original paper (1990) is difficult for me to understand. I need a more basic ...
1
vote
1answer
456 views
Multiple disjoint subset sum problem
Given two sets of nonnegative integer numbers:
$X = {x_1, x_2, ... x_n}$
$Y = {y_1, y_2, ... y_m}$
Need to find partition of $X$ on $m$ disjoint subsets, such as sum of elements in $i$-th subset ...
2
votes
0answers
291 views
0,1 solution to system of linear integer equations.
I have the following problem:
$A x = b$
where $A, b$ - $m \times n$-maxtrix and $m$-vector of nonnegative intgers (respectivelly).
$x \in \{0,1\}^n $ - vector of binary variables, which need to be ...
4
votes
3answers
505 views
Lattice points close to a line
Take a sheet of grid paper and draw a straight line in any direction from the origin. What is the closest non-zero grid point $\boldsymbol{p}\in\mathbb{Z}^2$ within a distance $\epsilon>0$ of the ...
0
votes
0answers
111 views
Question on non-linear parametric mixed integer program
I am trying to solve a mixed integer minimization problem, where there are a number of parameters, and there are products of parameters with variables appearing in the objective function. I assume ...
3
votes
1answer
214 views
Partially optimal solutions in integer linear programming
Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals.
An other interesting ...
5
votes
2answers
433 views
Some weird “system” of inequalities in nonnegative integers.
Suppose I have a bunch of nonnegative integers $(a_{ijkl})_{1 \leq i \leq j \leq k \leq l \leq 17}$ such that for all 17-tuples nonnegative integers $w_t$ (for $1 \leq t \leq 17$) we have that ...
4
votes
1answer
548 views
Minimum distance between adjacent concentric circles that cross integer lattice points
This problem looks simple, but I searched around and couldn't find any similar problems or related resources. Hope someone could provide a clue or at least a hint of what class of prolbems it belongs ...
1
vote
1answer
203 views
Representing integer points inside a polytope using a unit hypercube
Let $D\subset\mathbb{Z}\times\mathbb{Z}$ such that $D$ is formed by the points bounded by a convex polytope. Let $f:D\to\mathbb{R}$ defined by $f(x,y)=ax+by+c$, where $a,b,c\in\mathbb{R}$ and ...
1
vote
1answer
191 views
Spectral analysis of sparse symmetric integer matrices
Hi all,
A project I'm currently working on requires me to compute the eigenvectors / eigenvalues of sparse symmetric integer matrices. This is needed in the context of Principal Component Analysis. I ...
0
votes
0answers
135 views
Knapsack Constraint
I'm trying to implement a recursive algorithm that I came up with that first solves the knapsack for a given objective and then cuts off the solution and then finds the next best solution.
However, I ...
4
votes
0answers
198 views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...
1
vote
1answer
223 views
The number of hyperplanes determining the integer points of a polyhedron
This question is inspired by this one.
Let $P \subset \mathbb R_{+}^n$ be a convex polyhedron whose complement in $\mathbb R_{+}^n$ has finite volume. Let $Int(P) = P \cap \mathbb N^n$. (For ...
0
votes
1answer
333 views
How to solve this integer programming problem?
I have a sequence of matrices $\lbrace A_i \rbrace_{i=1}^N$ and I want to select a column from each of these matrices so that the following sum is minimized:
$\sum_{i=1}^N || A_{i} \vec{x_{i}}- ...
2
votes
3answers
343 views
On special type polynomial inequalities over integers
A special monomial is a monomial of the form $C\cdot x_{i_1} \cdot \ldots \cdot x_{i_n}$, where C is an integer and no variable is repeated more than once in the monomial. For instance, $x\cdot y\cdot ...
4
votes
1answer
212 views
Symmetry of the integer gap
Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function ...
1
vote
3answers
1k views
How to solve Linear Programming problem with tighter Integer Programming constraints
I want to learn a bit about Linear Programming.
After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...
4
votes
1answer
2k views
Proving that a binary matrix is totally unimodular
I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
1
vote
1answer
401 views
When is a triangular matrix totally unimodular?
I have an {0,1}, invertible, triangular matrix, that I would like to show to be totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
1
vote
3answers
373 views
non-linear mixed integer programming question
I tried this question over in the algorithms section of stackoverflow and never really got a handle on the problem. I know it concerns non-linear mixed integer programming.
[In the following, 1...n ...
9
votes
1answer
419 views
Condition for existence of certain lattice points on polytopes
Let $a_1,\cdots, a_n$ be integers such that $a_i\geq 2$ for all $i$ and $k>0$ another integer.
I am interested in whether there exist integers $x_1,\cdots, x_n$ with $0<x_i<a_i$ satisfying:
...
0
votes
1answer
153 views
linear program with zeros
Hi, I want to be able to solve a linear program that has constraints that are either zero or a range. An example below in LP_Solve-like syntax shows what I want to do. This doesnt work. In general all ...
4
votes
1answer
480 views
Hermite normal form in families
How does Hermite normal form (over $Z$) vary in families? I.e. if I have an $n\times m$ matrix $M$ whose entries are integral polynomials in some integral variable $x$, how does the Hermite normal ...
