Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
1,128 questions
4
votes
1
answer
277
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 ...
- 18k
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. ...
- 23.6k
2
votes
1
answer
798
views
Integral Farkas Lemma
The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given.
In the proof of Lemma 3.1.1 in the book "...
CommunityBot
- 1
6
votes
1
answer
1k
views
Solving $Ax = b$ for non-negative $x$ given boolean matrix $A$ and non-negative $b$
I am trying to solve $Ax = b$ with the following properties:
$A$ is a boolean (aka. logical, binary) matrix, i.e., each entry in $A$ is either $0$ or $1$
$A$ is of size $m \times n$ where $m \ll n$
...
CommunityBot
- 1
1
vote
1
answer
836
views
Total unimodularity and partition of the rows
Theorem. A given matrix $A \in \mathbb{Z}^{m \times n}$ is totally unimodular iff for any $I \subset [m]$ there exist a partition of the set $I$, $(I_1, I_2)$, such that $$\sum_{i\in I_1}a_{i} - \sum_{...
CommunityBot
- 1
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 ...
- 5,488
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 ...
- 5,488
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 ...
- 52.5k
2
votes
1
answer
2k
views
Constraints of a linear programming problem
QUESTION
Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
CommunityBot
- 1
8
votes
2
answers
2k
views
Linear constraints to placing $N$ queens on an $N \times N$ chessboard? [closed]
I'm trying to formulate the problem of placing $N$ queens on an $N \times N$ chessboard such that no two queens share any row, column, or diagonal.
I managed to define my decision variable as $x[n][...
CommunityBot
- 1
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 ...
- 23.6k
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\...
- 52.5k
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}$ ...
- 23.6k
3
votes
1
answer
913
views
Approximate algorithms for integer linear programming (for optimal subset selection)
I'm trying to select an optimal subset of some items. I've tried 2 optimal approaches (branch-and-bound and integer programming) but both proved impossible for the size of the problem. I'm wondering ...
CommunityBot
- 1
1
vote
2
answers
346
views
Existence of an inner point in a nonempty polyhedron
I was reading some notes on polyhedral analysis and encountered a proof that confused me. The proof is in the book named "Integer and Combinatorial Optimization" by Wolsey and Nemhauser.
Let ...
- 21