As of May 31, 2023, we have updated our Code of Conduct.

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

181 questions
Filter by
Sorted by
Tagged with
1 vote
62 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 ...
• 117
29 views

### Partitioning vectors from Z^k into bundles preserving their additive properties

Let $B_1, B_2, \dots, B_m$ be disjoint subsets of $\mathbb{Z}^k$ and $B$ denote their union. Also suppose that $k$ upper bounds the $\ell^\infty$-norm of every vector in $B$. A set $V \subseteq B$ of ...
• 33
182 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 ...
• 13.2k
1 vote
63 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)$ ...
111 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 ...
• 13.2k
104 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 ...
• 117
86 views

• 12k
59 views

54 views

• 13
97 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
227 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 ...
74 views