Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
1,128 questions
4
votes
1
answer
276
views
Winnability of an urn-ball game with restricted two-urn moves
My question is about a certain combinatorial game. The game works as follows. We have $n$ urns, each of which contains $m$ balls, where $m$ and $n$ are positive and satisfy $m < n$. A move consists ...
- 728
0
votes
1
answer
98
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,501
2
votes
2
answers
110
views
Triangle with Interlacing Rows Inequality [Programming]
Hi I am a math major and I am trying to solve a challenging math problem. The tools needed to solve this are in the field of computer science and coding. I am okay at programming, however I need some ...
- 795
0
votes
1
answer
108
views
Optimal Covering of a $98\times 98$ Grid with a $13\times 13$ Tile with Cut Corners
I am working on a 2D covering problem and would appreciate some insights or references to relevant mathematical concepts.
The Problem
The goal is to completely cover a $98 \times 98$ grid using the ...
0
votes
1
answer
97
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
1
vote
2
answers
160
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
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
0
votes
0
answers
59
views
Definition of minimal system on equations
I am searching for the definition of a minimal system of equations for a polytope. Specifically, I am studying a variant of the graph colouring problem, and in Braga et al.$\color{magenta}{^\star}$ ...
- 43
2
votes
1
answer
171
views
Relationship between Optimal Solutions of a Linear Program and its Integer Counterpart with Binary Constraint Matrix
Consider a matrix $\mathbf{A} \in \{0, 1\}^{K \times N}$ and a vector $\mathbf{b} \in \mathbb{Z}_{>0}^{K \times 1}$ (i.e., elements of $\mathbf{A}$ are either $0$ or $1$, and elements of $\mathbf{b}...
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
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
0
votes
1
answer
55
views
Seeking advice on how to "see" this derivation
I'm struggling to model this constraint for a problem:
$$x_C^4 = 1 \implies (x_A^4 + x_B^4 \geq 1 \land x_A^1 + x_B^1 = 0) \;\lor\; x_A^2x_B^3 = 1 \;\lor\;x_A^3x_B^2=1.$$
where all variables are ...
- 2,129
2
votes
1
answer
87
views
Model a finite lattice with an ILP
Is there a standard optimal way to enforce the finite lattice (order) definition in an Integer Linear Program, for a lattice with a given number of elements $n$?
I have tried a web search but with no ...
- 2,405
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 ...
