Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
1,127 questions
0
votes
1
answer
84
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
2
votes
2
answers
102
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 ...
- 805
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
1
answer
107
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
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
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
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}...
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
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
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,375
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
2
votes
0
answers
62
views
Integer linear combination of vectors [closed]
I have a lot of integer vectors $v_1=(a_1,b_1),v_2=(a_2,b_2),\dots,v_n=(a_n,b_n)$ and vector $(a,b)$. I need to find integer linear combination, s.t. $c_1v_1+\dots+c_nv_n=(a,b)$. Is there a smart way ...
- 37
-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 ...
1
vote
1
answer
86
views
Conjecture about a particular type of $N \times N$ binary matrix
Matrix Properties
Considering all $N \times N$ matrices $ M = \{ m_{i,j} \}$ with the following properties:
Elements are 0 or 1. So $ m_{i,j} \in \{0,1\}$
Diagonal elements are always 1. So $m_{i,i} =...
- 43
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
0
answers
23
views
"Extreme ray semigroups" are finitely generated
There is this nice classical theorem that says that, if $C \subseteq \mathbb{R}^d$ is a polyhedral cone, then $C \cap \mathbb{Z}^d$ is a finintely generated semigroup.
I have the intuition that the ...
- 1,892
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 ...
0
votes
0
answers
53
views
Optimizing code to find optimal value of integer polynomial
I'm writing a Python program to calculate the maximum value of a polynomial $p * (1 + (d * (1 + (o * (1 + g))))$, subject to the constraints that $p$, $d$, $o$ and $g$ are all positive integers, and $...
- 1
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
129
views
Writing consecutive ones matrix in reduced row echelon form.
I’m trying to prove that every matrix with the consecutive ones property is totally unimodular.
A matrix has the consecutive ones property if every row is of the form $(0,\ldots ,0,1, \ldots , 1, 0, \...
- 3
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
1
answer
76
views
Multi-objective optimisation methods suitable for LPs and (M)ILPs
Which methods (classic/modern) are utilised to solve multi-objective optimisation problems compatible with linear programming (LP) and mixed-integer linear programming.
Utilised in the context of time ...
- 265
1
vote
2
answers
80
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
2
votes
2
answers
88
views
Solving set of linear integer equations, and we compute the automorphism subgroup of permuting variables (preserving equations)
Suppose we have a set of variables $X_i, i=1..n, n \in \Bbb{N}$ and a set $E$ of linear equations in them:
$$
\sum_{i = 1}^n \lambda^j_i X_i = C_j \in \Bbb{Z} \\
j=1..m
$$
Then define $\textbf{Aut}(E) ...
- 22.7k
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
0
votes
1
answer
99
views
Maximizing $\sum_{i<j} \frac{x_i x_j}{\sum_{k=i}^j x_k}$ over compositions of $m$
I'm interested in the one-parameter family of optimization problems, parametrized by $m \in \mathbf{Z}^+$
$$\max_{n, x_1,x_2,\dots,x_n \in \mathbf{Z}^+ \\ x_1+x_2+\cdots + x_n=m} \sum_{i=1}^{n-1} \...
- 25k
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
0
answers
142
views
Existence of a basis of lattice with successive minima norms
Is there an easy way to show that given a lattice $\Lambda \subset \mathbb{R}^n$ of full rank, exists a basis where each vector has norm $\lambda_i$ i.e the i-th successive minima ($\lambda_i(\Lambda)=...
- 5,324
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
0
votes
1
answer
88
views
Why should Branch&Bound not terminate if the relaxation is an unbounded LP?
In my homework assignment there is a task which wants you to show that for specific integer programs Branch&Bound could run forever.
One could just choose the relaxation of the IP to be some kind ...
- 477
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
3
votes
1
answer
73
views
Can you find a linear system with these integer solutions?
I have this expression $(x \geq 1) \vee(x=0 \,\wedge\, y -z \geq 1)$ which I am solving over the nonnegative integers $x,y,z \in \mathbb{Z}_0^+$.
I suspect it is impossible to find a system of linear ...
- 19.3k
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
0
votes
1
answer
80
views
Correctly understand the implication of approximation ratio for the set cover problem?
I am currently reading this wikipedia article about the set cover problem and it said here that "it cannot be approximated to $\left[ {1 - o\left( 1 \right)} \right]\ln \left( n \right)$ unless $...
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 ...
2
votes
2
answers
48
views
Explanation of multiple constraints from one rule [closed]
I'm trying to understand this case study:
https://github.com/DorisRipley/Art-Exhibition-Optimization-A-BIP-Modeling-Approach/blob/main/Art%20Exhibition%20Optimization.pdf
and I'm having trouble with ...
1
vote
1
answer
293
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
0
votes
3
answers
148
views
Minimizing linear function with constrains on coefficients
Question:
I am faced with minimizing a specific sum:
$$ \sum_{i=1}^{L} a_i x_i $$
$L$, $x_i$ and $K$ are given.
So the question is reduced to choosing proper $a$.
Constrains on $a$:
$a_1$ = 1.
$a_i = ...
- 55
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
0
answers
103
views
Integer programming problem, with complicated cost function
I need to find the vector $\hat{n}=[n_1 \; n_2 \; \cdots \; n_N]$, all integers,such that $1\leq n_i \leq Z$, $\forall i$ (with $Z$ also integer) that minimizes the following function:
$F=\frac{1}{N}\...
- 89
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
1
vote
1
answer
32
views
Searching for an optimal multiple + offset decomposition.
Let us assume I have a sequence of numbers $\{n_1,n_2\cdots, n_k\}$ which I want to approximate / represent like so:
$$\hat n_i = a_i x + b_i :,\\ a_i \in \mathbb Z^+,b_i\in \mathbb Z\\\text{so that}\\...
- 26.7k
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
1
vote
1
answer
117
views
Why this ILP and LP are equivalent?
Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
- 13
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
6
votes
1
answer
231
views
What was the gap in Ariane Papke's proof that the minimum number of sudoku clues is 17?
I was reading McGuire's paper on why the minimum number of clues in a Sudoku puzzle is 17 when I came across a curious comment:
In 2008, a 17-year-old girl submitted a proof of the nonexistence of a ...
- 424
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
0
votes
0
answers
108
views
Gram Schmidt swapping two vectors of the basis
I'm trying to understand how the LLL algorithm works and I've stumbled upon the following question:
Suppose I have $B = (b_1,\cdots,b_n)$ vectors and I perform Gram Schmidt process obtaining $(v_{1},\...
- 5,324