# 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.

154
questions

**0**

votes

**0**answers

32 views

### Showing that one of the inequalities representing a facet is necessary to describe a polyhedron

As stated in Lecture 3 of "Integer optimization" on Page 2, for each facet $F$ of $P$, at least one of the inequalities representing $F$ is necessary in any description of $P$ where $P =\{x \...

**0**

votes

**0**answers

63 views

### On number of facets in projected polytopes of certain sparseness

$\DeclareMathOperator\Set{Set}$
Let
$Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$
where $A$ has $r=km$ rows and $k=O(1)$.
I am trying to write
$$
Set=\{x\in\...

**1**

vote

**1**answer

80 views

### Allowing an “OR” option between equations in a linear program

I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on.
I will explain what I mean precisely: Lets say I have a set of ...

**0**

votes

**0**answers

14 views

### Is it valuable for MIP solves to make redundant variables?

I'm writing an integer programming model, and coming from constraint programming I'm thought to put as much redundancy in as posible. But I'm not sure how much of that logic is correct for MIP.
...

**2**

votes

**0**answers

82 views

### Complete graph invariant based on integer programming?

Roughly speaking, we are trying to find complete graph invariant
as the lexicographically first matrix from the permutations
of the adjacency matrix.
Let $G$ be graph, possibly directed graph, of ...

**0**

votes

**0**answers

53 views

### Solutions to matrix equations in the non-negative integers

For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers.
I've been doing this with Sage's mixed integer ...

**0**

votes

**0**answers

61 views

### On two dimensional integer programming with Euclid

I frequently hear LLL algorithm is generalization of Euclidean algorithm for GCDs. LLL algorithm is utilized in Lenstra's fixed dimension integer programming.
Is there a way to perform two dimensional ...

**-1**

votes

**1**answer

78 views

### How to solve MILP problem on several linear subspaces

I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...

**1**

vote

**0**answers

55 views

### Does Barvinok's algorithm apply to convex integer program?

Barvinok provided a counting algorithm to count number of integer solutions to integer linear program that runs in polynomial time if the number of integer variables is fixed.
If we have convex ...

**2**

votes

**0**answers

54 views

### Linear functions in Lenstra's algorithm (integer programming)

I'm working on implementing Lenstra's algorthm. At the bottom of p.5 (at ``construct $n+1$ linear functions''), he says to constrain each $g_i:\mathbb{R}^n\to\mathbb{R}$ by its value on each of $n+1$ ...

**0**

votes

**0**answers

21 views

### Binary optimisation to maximise covariance or L2-error, is it even possible? Could it be solved by relaxation?

I have a matrix A and a vector y, given A invertible the solution to find x is simple, however if we restrict x to be a binary vector i.e. $$ x_{i} \in \{0,1\} \quad \forall i $$ then we are not ...

**1**

vote

**0**answers

36 views

### Structural properties of polytopes for mainstream integer or linear programs

Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...

**2**

votes

**1**answer

112 views

### Constructivity of two problems on a standard simplex?

Maximizing a hyperplane $\sum_i a_ix_i$ where $a_i\in\mathbb R$ and each $a_i$ are fixed and non-negative and $x_i$ are variables over a standard simplex $\sum_i x_i\leq 1$ with $0\leq x_i$ always ...

**0**

votes

**0**answers

46 views

### Gröbner basis and integer programming

I was studying about grobner basis and observed one application of it in integer programming which is pretty much amazing but tougher than available methods like branch bound. Then what is the benefit ...

**2**

votes

**1**answer

70 views

### Maximizing the length of a sequence under constraints

Fix $\{w_n\}_n$ a sequence of positive real numbers, fix positive integers $N,K$, and fix $\eta>1$. I'm looking for a sequence of integers $\{k_n\}_n$ optimizing the following problem:
$$
\begin{...

**1**

vote

**0**answers

49 views

### Pros and cons of using integer programming alone or combined integer and global optimization?

First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...

**2**

votes

**0**answers

49 views

### Deciding whether a system of linear integer inequalities has infinitely many solutions

I have a quick question that I am struggling to find a solution to:
Given a system of linear integer inequalities $A\textbf{x} \leq \textbf{b}$, where $A\in \mathbb{Z}^{m\times n}$ and $\textbf{b}\...

**0**

votes

**0**answers

68 views

### Maximize sum of supermodular functions over nested sets

Let $R$ be a function that maps a set and a positive integer to a real positive number. We have that for any positive integer $t$ and $S \subseteq \{1, \ldots, t\}$, $R(S, t)$ satisfies:
For all $t &...

**1**

vote

**2**answers

94 views

### Integer linear programming (ILP) formulation of connectivity of induced subgraph

Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...

**0**

votes

**0**answers

19 views

### How do you refer to the feasible set of solutions to a mixed-integer program?

I frequently want to refer to the feasible set of solutions to a mixed integer programming instance. Is there a name for a subset of $\mathbb{R}^n\times\{0,1\}^m$ of the form $\{(x,a)| Ax + Ba\leq b\}$...

**1**

vote

**1**answer

136 views

### Gröbner basis via integer programming

I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...

**0**

votes

**1**answer

142 views

### What are all the possibilities of $A$ s.t. $\det(A)=k$?

Suppose we have $A \in M_3(\Bbb N\cup\{0\})$ s.t. sum of the elements of each row is $k $ for some fixed $k\in \Bbb N\cup\{0\}$. What are all the possibilities of $A$ s.t. $\det(A)=k$?
We can start ...

**0**

votes

**1**answer

66 views

### How do I solve this integer programming problem with non convex constraints?

I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place.
I have an optimization problem like this
...

**5**

votes

**1**answer

149 views

### Is Binary Integer Linear Programming solvable in polynomial time?

The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...

**0**

votes

**1**answer

80 views

### Integer programming problem

I have an integer optimization problem with a non-linear function ($F(X)$) in the objective and one of the constraints.
$F(X)=x_n^{i,j}\Big[\sum\limits_{\forall s\neq i}\sum\limits_{\forall m\in\...

**1**

vote

**0**answers

32 views

### Modelling exact unions of polytopes in homogeneous case?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed ...

**1**

vote

**0**answers

75 views

### Mixed integer formulation of union of polytopes?

Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...

**0**

votes

**1**answer

169 views

### Convex integer program with totally unimodular constraints

Suppose I have a convex (nonlinear) integer program with totally unimodular linear constraints. What are sufficient conditions one can impose on the convex objective function such that relaxing the ...

**1**

vote

**1**answer

81 views

### Algorithm for (binary) integer programming

I am looking for an algorithm that can solve the following (binary) integer programming problem. The problem description is given below:
\begin{align*}
&\max\sum_{i\in I}\sum_{j\in J}g_{ij}w_{ij} \...

**6**

votes

**0**answers

230 views

### Efficient solutions to general Bézout’s identity $a_1 b_1 + \dots + a_n b_n = 1$

Suppose I have integers $a_1, \dots, a_n$ which are coprime, meaning that
$$a_1 b_1 + \dots + a_n b_n = 1$$
has a solution in integers $b_1, \dots, b_n$.
I would like to get a bound saying ...

**1**

vote

**0**answers

34 views

### Fast certficate of negativity for objective value of mixed-integer linear program

Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...

**1**

vote

**0**answers

89 views

### Smallest integer lattice point by box measure in a polytope?

Given an integer lattice $\mathcal L\subseteq\mathbb Z^n$ represented by basis $\mathcal B$ and an integer linear program $Ax\leq b$ where $x\in\mathbb Z^n$ is unknown with $A\in\mathbb Z^{m\times n}$ ...

**2**

votes

**1**answer

289 views

### Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]

I need to emulate this sequence for a program: http://oeis.org/A025302
Stuff that I've taken into account:
After finding the prime divisors of a number. I take any divisor as p and apply the ...

**1**

vote

**1**answer

255 views

### Minimizing sum of ratio of linear functions (Sum of Linear Ratios Problem)

Given constants $c_i \in \mathbb{R}$ and $d_i \in \mathbb{R}$ and variables $x_i \in \mathbb{R}$, where $c_i > 0, d_i > 0, x_i > 0$ can we easily solve the following optimization problem:
$$...

**1**

vote

**0**answers

87 views

### When are quadratic integer programs “easy to solve”?

Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form
$$
f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...

**1**

vote

**1**answer

139 views

### How good is the LP relaxation?

Consider the optimization problem
\begin{align}
\max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i
\end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...

**5**

votes

**2**answers

467 views

### What are the definable sets in Skolem arithmetic?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities ...

**1**

vote

**0**answers

95 views

### How to solve such integer program problem?

Consider a $3$-tuple $(a,b,s)$ with $a,b\in\mathbb{Z}_+,s\in\mathbb{Q}_+$. Denote $ab-s$ by $\Delta$. Let $A$ be a positive number. What are the values of $A$ such that for any $(a,b,s)$ with $\Delta\...

**1**

vote

**0**answers

58 views

### How to minimize n-polytope's bounding box with linear transformation?

I am working on an exact algorithm for integer linear programming for my master's thesis:
$Ax\leq b, x \in \mathbb{Z}^n$
$cx\rightarrow min$
For my idea to work out, I need a guarantee that n-...

**0**

votes

**1**answer

217 views

### Relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem
$$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject ...

**1**

vote

**1**answer

321 views

### Feasibility Mixed integer Linear programming with quadratic constraints?

Consider the mixed integer program
$$Ax\leq b$$
$$By\leq c$$
$$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...

**-1**

votes

**2**answers

89 views

### On OR condition in Linear Programming with exponentially many constraints [closed]

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...

**2**

votes

**1**answer

63 views

### Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...

**1**

vote

**1**answer

87 views

### Convex integer programming on totally unimodular polytope?

If
$$\min x'Qx + Rx$$
$$Ax\leq b$$
$$x\in\mathbb Z^n$$
is a quadratic program with $x'Qx$ is convex is there a polynomial time algorithm for this if $A$ is totally unimodular?
In particular if we ask ...

**0**

votes

**0**answers

209 views

### Finding a point in the relative interior of the convex hull of a set of integer-valued vectors

Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...

**2**

votes

**0**answers

74 views

### What does Lenstra's MILP do?

Honestly I do not understand why Lenstra's MILP is in $P$ if the number of integer dimensions is fixed.
Here is what Lenstra says in 'http://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf' in ...

**2**

votes

**1**answer

220 views

### Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension.
What exactly is this arithmetic complexity?
...

**2**

votes

**1**answer

149 views

### On software for ILP

In 'Computational Experience with Lenstra's Algorithm' by L Gao, Y Zhang it is claimed that they have an implementation of Lenstra's fixed dimension integer programming algorithm. Is this available ...

**0**

votes

**0**answers

67 views

### Discrete primal-duality in optimization

I would like to inquire about the existence of something perhaps similar to the duality theorem in the convex analysis or convex programming in the discrete setting. Here is a concrete example.
Let $...

**1**

vote

**2**answers

152 views

### Detection of gaps in binary vector through linear methods

Suppose I have a binary vector a = (0,1,1,1,0,0) of length $N$. I want to detect in a linear way whether a has any gaps in ...