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

192
questions

0
votes

0
answers

18
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
vote

2
answers

185
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$$...

0
votes

0
answers

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

3
votes

2
answers

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

0
votes

0
answers

34
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,\\ &...

0
votes

0
answers

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

0
votes

1
answer

131
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
votes

0
answers

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

2
votes

1
answer

174
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}...

3
votes

1
answer

132
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} :=...

0
votes

0
answers

61
views

### An integer optimization problem on the simplex

For $K \geq n$ and some $\sigma_i > 0$, I am looking for a solution to the following optimization problem:
\begin{equation}
\underset{\begin{smallmatrix} t_1, \cdots, t_n \in \mathbb{N}^{*} \\ \...

0
votes

0
answers

38
views

### Basis of monoid of integral vectors

Suppose that $M\in\mathbb{Z}^{n\times k}$ is a matrix of rank $k<n$. How can I obtain a set of vectors $b_1,\ldots,b_k\in\mathbb{Z}^k$ (if exists) such that each row of $M$ is a non-negative ...

0
votes

1
answer

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

1
vote

1
answer

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

2
votes

0
answers

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

1
vote

0
answers

89
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)$ ...

0
votes

0
answers

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

3
votes

0
answers

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

3
votes

0
answers

104
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 \{...

0
votes

1
answer

33
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}}^*}\...

0
votes

1
answer

82
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\{...

4
votes

0
answers

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

1
vote

2
answers

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

0
votes

3
answers

662
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$?

2
votes

1
answer

172
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{...

0
votes

2
answers

401
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

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

3
votes

1
answer

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

0
votes

1
answer

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

0
votes

1
answer

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

5
votes

2
answers

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

2
votes

0
answers

111
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}...

0
votes

1
answer

75
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 $...

1
vote

1
answer

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

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

1
vote

1
answer

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

0
votes

1
answer

118
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

283
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\|_\...

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

1
vote

1
answer

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

4
votes

0
answers

218
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\}$....

1
vote

1
answer

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

2
votes

1
answer

68
views

### What's the meaning of this inequality in the lot-sizing and scheduling problem

I learned about the MILP models proposed by Pochet and Wolsey. Here are the formulations of one of these models(MILP3).
So the decision variables and the primary formulation are as following:
Based ...

0
votes

1
answer

124
views

### What is the computational complexity of the calculation of $ \Psi(x) $?

What is the computational complexity of the calculation of $ \Psi(x) $ described below:
Let $\left\{ f_i : \{0,1,\dots,m\} \to \mathbb{R} \right\}_{i=1}^n$. For each $x \in \{0,1,\dots,m\}$ we ...

1
vote

0
answers

73
views

### $\mathsf{NP}$ complete version of 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

1
answer

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

2
votes

0
answers

106
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

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