Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
1,127 questions
0
votes
1
answer
85
views
How many big and small marbles are not used?
Translating to English from a non-English physics book about measurements:
Anif has $8$ big marbles and $15$ small marbles. The weight of the big and small marbles are $37.5$ and $12.5$ respectively. ...
- 2,491
0
votes
1
answer
95
views
Create a closed tour so that every number is visited maximum once
Create a closed tour visiting the numbers. The tour must start and end at the same cell. During the tour, you can only visit the neighboring cell (up,down,left,right). The tour cannot contain a number ...
- 15
0
votes
0
answers
36
views
Upper bound on the denominators of a rational solution for feasible linear program over integers
Let $d\in \mathbb{N}$ be a fixed constant. Let $V\subseteq \{-1,0,1\}^d$ be some set of vectors and let $w\in \mathbb{Z}^d$. Consider the linear program
find $ x\in \mathbb{R}^V $ such that: $
\sum_{v\...
- 101
1
vote
2
answers
158
views
How to scale matrix rows so the sum of each column has a similar value?
Given a matrix $A \in \mathbb{R}^{m \times n}$, I want to find a vector $\vec{x} \in \mathbb{N}_{+}^{m}$ so $\vec{y} = {A}^{T} \vec{x}$ is nearly a constant vector, i.e., the values of $\vec{y}$ are ...
- 393
3
votes
1
answer
81
views
ILP formulation for finding best route in 18xx-style board game (Maximum value disjoint paths of given length)
I'm working on an ILP formulation that's supposed to find the best scoring set of routes on a given turn in a 18xx-style board game (in this particular case, Shikoku 1889)
Problem description
To ...
- 113
2
votes
2
answers
131
views
LP relaxation leads to exponential Branch & Bound
Consider the following LP program
$$ \min x_{n+1} $$
subject to:
$$ \sum_{i=0}^n 2 x_i + x_{n+1} = n $$
$$ x_i \in \{ 0, 1 \} $$
And $n$ odd.
The claim is that using the standard B&B algorithm ...
- 2,005
0
votes
1
answer
57
views
Gomory fractional cuts and separation problem
I confused myself into a hole here, so just need to see what I am missing. So, in the Gomory fractional cut cutting plane algorithm you use the basis to generate a new cut. How come it does not ...
- 176
-1
votes
1
answer
77
views
How to use combinatorics to prove a minimum number of weeks required for a scheduler.
Given a soccer league with 9 teams, is it possible to calculate the minimum number of weeks needed for each team to play each other twice, with the following restrictions:
Each week, a maximum of 2 ...
0
votes
1
answer
44
views
How to compute minimal points of well-ordered $\mathbb{N}^{d}$-space
Suppose we have
$$
S := \{x\in\mathbb{N}^{d}:Ax=b\}\subseteq\mathbb{N}^{d}
$$
for some $k,d\in\mathbb{N}, b\in\mathbb{N}^{k}, A\in\mathbb{N}^{k\times d}$.
The set $\mathbb{N}^{d}$ is partially ordered ...
- 163
0
votes
1
answer
50
views
How to choose x positive integer such that x*2024^n has uneven number of digits for the longest time?
How to choose $x$ positive integer such that $x*2024^n$ has uneven number of digits for the longest time?
For example, if $x=1$, at $n=1$, I already have an even number of digits.
With $x=7$, I have ...
1
vote
0
answers
51
views
Solving for Hamming Weight Inequality in $\mathbb{F}_2^n$
Given random value vectors $X_i \in \mathbb{F}_2^n$, for $i = 1, 2, \ldots, m$, and a target range $[a, b]$, the objective is to efficiently find all solutions to the inequality $a \leq w_H\left(\sum_{...
- 11
0
votes
1
answer
92
views
Integer Optimization with Constraints
I need to maximize the following expressions: $mn-n^2$ given $0\lt m^2+n^2 < d$, where $d$ is given to me. I am also given that $m$ and $n$ are both integers and that $gcd(m, n) = 1$. I am unsure ...
user1386447
1
vote
2
answers
81
views
Closed Set of Vertices
The question goes as follows:
Given a directed graph $G = (V, A)$ with weights $w_v$ on the vertices
for $v ∈ V$. Describe the problem of finding a closed subset of vertices
with maximum weight as an ...
- 39
0
votes
0
answers
70
views
How to simplify this nonlinear integer programming
The situation is :
There are n bulbs and m power sources. The j-th power source has a failure probability of $P_j$. Each bulb is connected to 3 power sources, and only $\frac{3n}{m}$ bulbs can be ...
- 33
1
vote
1
answer
190
views
Chvatal-Gomory integer rounding method to find facets of $\operatorname{conv}(S)$
The question:
"given a set $S = \{x \in \mathbb{Z}^2 : 4x_1 + x_2 ≤ 28, x_1 + 4x_2 ≤ 27, x_1 − x_2 ≤ 1, x ≥ 0 \}$.
we are tasked with deriving each facet of $\operatorname{conv}(S)$ as a Chvatal-...
- 13
0
votes
1
answer
109
views
A variant of the partition problem or subset sum problem
Given a target list $T = (t_1, t_2, \ldots, t_N)$ and a multiset $S = \{s_1, s_2, \ldots, s_M\}$, both with non-negative integer elements, $t_k\in \mathbb{N}_>$ and $s_k\in \mathbb{N}_>$, ...
- 134
1
vote
1
answer
206
views
What is the computational complexity of generalized Long Live the Queen?
Consider the following model of computation: The computer's memory consists of $n$ registers denoted $r_1, ..., r_n$, each holding an integer.
In the following, an affine combination means an ...
- 173
1
vote
1
answer
53
views
Question about a property of the integer-hull
If I have a convex set $Q\subseteq \mathbb{R}^n$ and a cone $E\subseteq \mathbb{R}^n$. Let $Q_I = conv\{Q \cap \mathbb{Z}^n\}$ and $E_I$ respectively.
Is it in general the case that $Q_I + E_I \...
- 477
1
vote
1
answer
103
views
Is it possible or practical to just solve integer optimization problem by penalizing?
I am an engineer who is currently working in network optimization problem. I have finised my master degree a long time ago. During my studies I have learnt about the penalty technique to turn a ...
1
vote
1
answer
296
views
How to write constraints for an indicator function such that if x = 0 then y = 1, and otherwise y = 0?
Currently working on an optimization problem using pyomo. One constraint I need to make is to limit the number of times a situation occurs - Essentially when my variable x = 0.
So I would like an ...
- 13
3
votes
0
answers
81
views
Reference Request: Vertex Enumeration Algorithms That Finds All Integer Points in a Polytope
For fun, I explored vertex enumeration algorithms for linear programs to find all feasible extreme points in a polytope. Naturally, I asked, "Do there exist algorithms that solve for all integer ...
- 2,157
1
vote
1
answer
63
views
Integer Linear Programming - Dividing n people into m groups of specific sizes
I've recently asked this question about dividing n people into m groups for the specific model I used to solve the assignment problem of dividing the people into groups (boolean variables xij that ...
- 197
2
votes
1
answer
116
views
Integer Linear Programming - Dividing n people into m groups
I have modeled the problem of dividing n people into m groups using a binary $nxn$ matrix that we will call X.
If $x_{ij} = 1$ it means that person i is with person j in the solution's groups. If $x_{...
- 197
3
votes
1
answer
276
views
Largest smallest integer solution
I have the following system of equations, for $i$ in $1,\ldots,n$:
$$
\mathbf{a_i} \cdot \mathbf{x} = y
$$
The variables are $\mathbf{x}$ - a vector of $n$ non-negative integers, and $y$ - a positive ...
- 11.6k
3
votes
1
answer
74
views
Does there exist other integer models that contain an exponential number of branches thats not knapsack for the branch-and-bound method?
During a class assignment, I was presented with the following question:
Provide an integer program that has an exponential number of branches...(expunged excess)
...
- 2,157