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

170 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
70 views

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. ...
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-...
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 ...
1 vote
107 views

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