Skip to main content

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.

Filter by
Sorted by
Tagged with
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 ...
Rikka's user avatar
  • 1
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$$...
Turbo's user avatar
  • 13.7k
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 ...
graphtheory123's user avatar
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 ...
CWC's user avatar
  • 401
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,\\ &...
Manfred Weis's user avatar
  • 12.7k
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 ...
LyLa's user avatar
  • 3
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 ...
LyLa's user avatar
  • 3
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-...
Kamola's user avatar
  • 31
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}...
Anson's user avatar
  • 21
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} :=...
Display name's user avatar
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}^{*} \\ \...
Titouan Vayer's user avatar
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 ...
Brauer Suzuki's user avatar
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 ...
bang's user avatar
  • 3
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 ...
elsnar's user avatar
  • 127
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 ...
Turbo's user avatar
  • 13.7k
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)$ ...
shahulhameed's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Ali's user avatar
  • 127
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 \{...
Tom Solberg's user avatar
  • 3,929
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}}^*}\...
Manfred Weis's user avatar
  • 12.7k
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\{...
alosc's user avatar
  • 71
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 ...
Turbo's user avatar
  • 13.7k
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 ...
joro's user avatar
  • 24.3k
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$?
A.R.S's user avatar
  • 25
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{...
joro's user avatar
  • 24.3k
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 \...
Sebastien Palcoux's user avatar
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 ...
Samuel Bismuth's user avatar
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 ...
Neil Strickland's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
asdf's user avatar
  • 21
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 ...
Max Alekseyev's user avatar
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}...
Richard Border's user avatar
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 $...
grapher's user avatar
  • 13
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 ...
Michael Fan Zhang's user avatar
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-...
Manfred Weis's user avatar
  • 12.7k
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 ...
Luca Savant's user avatar
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 ...
Jeffrey's user avatar
  • 13
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 ...
Yorknight's user avatar
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 ...
Rise of Kingdom's user avatar
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\|_\...
Turbo's user avatar
  • 13.7k
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Rise of Kingdom's user avatar
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\}$....
Surpass2019's user avatar
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 ...
Rise of Kingdom's user avatar
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 ...
Kingsley's user avatar
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 ...
José María Grau Ribas's user avatar
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. ...
Turbo's user avatar
  • 13.7k
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 ...
Eric_'s user avatar
  • 141
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 ...
joro's user avatar
  • 24.3k
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 ...
JonHales's user avatar
  • 101