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
1 vote
0 answers
50 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 ...
user avatar
3 votes
1 answer
62 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 ...
user avatar
0 votes
1 answer
83 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 ...
user avatar
  • 12.8k
0 votes
1 answer
77 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 ...
user avatar
  • 21
4 votes
1 answer
197 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 ...
user avatar
2 votes
0 answers
70 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}...
user avatar
0 votes
1 answer
42 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 $...
user avatar
  • 13
1 vote
1 answer
30 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 ...
user avatar
0 votes
0 answers
27 views

Minimal distance between intersections of a regular grid parameterized by its change-of-basis matrix

Let a 2D grid basis $\mathcal{B}(\theta_1, \theta_2,r_1, r_2)$ whose change-of-basis matrix with respect to $\mathcal{B}_0$ the canonical basis of $\mathbb{R}^2$ writes : $$P_{\mathcal{B}_0}^{\mathcal{...
user avatar
0 votes
0 answers
19 views

MSTs as "connectivity donors" for ILPs of TSPs

Traditionally the constraints that eliminate subtours from the optimal solution of an ILP for a TSP are based on partitions of the vertex set that resemble a $2$-factor of the problem instance. ...
user avatar
0 votes
0 answers
30 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-...
user avatar
0 votes
0 answers
25 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 ...
user avatar
1 vote
1 answer
107 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 ...
user avatar
  • 13
0 votes
0 answers
22 views

Can it be decided in advance if the relaxed (non-integer) solution of a integer program will result in low error when rounded?

Is there any useful characterization of the class of integer programs where rounding of the relaxed (non-integer) solution will provably result in a good approximation of the minimum of the objective ...
user avatar
  • 111
0 votes
0 answers
44 views

Are there references to functional variants of the Unbounded Knapsack Problem?

Looking for a version of the following problem, extended to solutions in $\ell^{\infty}(\mathbb{N})$ Unbounded Knapsack Problem $ \max_{x_1,...,x_n} \sum_{i=1}^n v_ix_i$ $\text{ subject to }$ $\sum_{...
user avatar
  • 175
0 votes
1 answer
74 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 ...
user avatar
1 vote
1 answer
117 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 ...
user avatar
2 votes
0 answers
71 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\|_\...
user avatar
  • 12.8k
3 votes
0 answers
46 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 ...
user avatar
  • 12.8k
1 vote
1 answer
121 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 ...
user avatar
4 votes
0 answers
165 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\}$....
user avatar
1 vote
1 answer
192 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 ...
user avatar
0 votes
1 answer
41 views

What's the meaning of this in equality 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 ...
user avatar
0 votes
1 answer
110 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 ...
user avatar
1 vote
0 answers
59 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. ...
user avatar
  • 12.8k
1 vote
1 answer
96 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 ...
user avatar
  • 141
2 votes
0 answers
95 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 ...
user avatar
  • 23.3k
0 votes
0 answers
67 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 ...
user avatar
  • 101
-1 votes
1 answer
85 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 ...
user avatar
  • 39
1 vote
0 answers
62 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 ...
user avatar
  • 1,708
1 vote
0 answers
37 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 ...
user avatar
  • 3,668
2 votes
1 answer
122 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 ...
user avatar
  • 1,708
2 votes
1 answer
71 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{...
user avatar
2 votes
0 answers
201 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 ...
user avatar
2 votes
0 answers
53 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}\...
user avatar
0 votes
0 answers
80 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 &...
user avatar
1 vote
2 answers
331 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 ...
user avatar
0 votes
0 answers
20 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\}$...
user avatar
  • 43
1 vote
1 answer
150 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 ...
user avatar
0 votes
1 answer
146 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 ...
user avatar
  • 103
0 votes
1 answer
82 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 ...
user avatar
5 votes
1 answer
285 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 ...
user avatar
  • 201
0 votes
1 answer
93 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\...
user avatar
  • 19
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 ...
user avatar
  • 1,708
1 vote
0 answers
82 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 ...
user avatar
  • 1,708
0 votes
1 answer
264 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 ...
user avatar
1 vote
1 answer
86 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} \...
user avatar
  • 85
6 votes
0 answers
263 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 ...
user avatar
  • 3,686
1 vote
0 answers
35 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 \; ...
user avatar
  • 5,600
1 vote
0 answers
92 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}$ ...
user avatar
  • 12.8k