Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
0
votes
0answers
10 views
A mixed integer programming problem
What is the integer programming complexity of this sentence?
$\exists x\in\mathcal P\quad\forall y\in\mathcal P\quad\phi(x)\leq\phi(y)$ where $\mathcal P$ is a bounded convex polytope in $\mathbb Z^{...
0
votes
0answers
19 views
List of graph algorithm problems which can turn to polynomials
I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
0
votes
1answer
35 views
Atom in first order programming
Consider the following statements regarding atom in first order programming
An atom is a predicate applied to a tuple of objects.
Atoms: An atom evaluates to a number.
A scalar, a ...
1
vote
1answer
66 views
How to reformulate with Dantzig-Wolfe decomposition technique
I am dealing with the following Binary ILP:
\begin{equation*}
\label{equation6}
minimize
\sum_{i=1}^{m}\sum_{j=1}^{n}\sum_{t=0}^{T-p_{ij}}e_{ij}x_{ijt}
\end{equation*}
subject to
\begin{...
0
votes
0answers
14 views
Flowshop with parallel machines model
I am working on an integer programming model for a flowshop problem with different number of parallel machines.
I have to schedule $i=1,..,n$ jobs in $j=1,..,m$ activities where each $j$ activity has ...
1
vote
0answers
39 views
Binary Optimization Problems that can be easily solved?
As far as I have researched, even linear programs with binary constraints on the decision variables are in general NP hard.
However, I wounder if there are some (non-trivial) binary optimization ...
1
vote
0answers
20 views
knapsack with multiple constraints and some negative weights
I'm trying to solve an integer linear programming problem of the following form
$max$ $\sum_{i=1}^n v_i \cdot x_i$
$s.t. \sum_{i=1}^n w_{i1} \cdot x_i \leq 0$ and $\sum_{i=1}^n w_{i2} \cdot x_i \...
0
votes
1answer
35 views
Two Mixed Integer Linear Programs (MILP) with different objectives and same constraints
There are two Mixed Integer Linear Programs. They have the same set of linear constraints constraints, but different objectives with variables $\mathbf{z}$ and $\mathbf{x}$.
The first objective is:
$...
2
votes
1answer
25 views
Finding all natural number solution(s) to linear Diophantine equation of three variables
Ok, I've been puzzling over this problem for a while now and I think I'm close, but I'm running into a bit of a dead end.
For those curious, this puzzle comes from the game West of Loathing. It's ...
0
votes
2answers
35 views
Project allocation optimisation Code
I've been formulating an integer optimisation model for allocating students to projects where students give their preferences and rank them 1,2,or 3 with one being their best project preference.
...
0
votes
1answer
50 views
Unconstrained convex quadratic integer programing
Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I have a minimization problem of the form
$$
\min_{n\in N} \sum_i A_i n_i +\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^2
$$
...
0
votes
1answer
41 views
Approximate function by stacking building blocks
I need some help with a 'generalised Lego problem':
Given a function $f(x)\geq 0$ on an interval $[a,b]$, and a 'building block' function $p(x)\geq 0$ with compact support. The maximum of f shall be ...
1
vote
0answers
27 views
When are quadratic integer programs easy to solve? [duplicate]
Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form
$$
f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...
0
votes
1answer
28 views
Representing rounding algebraically [closed]
Is there a standard way to deal with rounding in algebra? For example:
y = x + round(x/2)
Would give 2 when x = [1, 3), 3 when x = [3, 5), etc. This of course ...
-1
votes
1answer
22 views
Find a valid inequality
Find a valid inequality for
$$
\{x\in\{0,1\}^5 \mid 9x_1 + 8x_2 + 6x_3 + 6x_4 + 5x_5 \leq 14\}
$$
that cuts off $(1/4, 1/8, 3/4, 3/4, 0)$.
I tried both Chvàtal cut and cover inequality, both of ...
0
votes
2answers
77 views
Matrix equation & integer programming
I have a series of matrix equations that look like:
$$x^TA_ky=b_k$$
with $k = 1, 2, .. n$
and $A_k, b_k$ known double precision matrices, $x$ and $y$ unknown.
Besides,
$$x, y$$
are vectors ...
1
vote
0answers
21 views
Resource Allocation Problem
Let $I, J, n \in \mathbb N$. Furthermore, let $\mathbf M \in \mathbb N^{I \times J}$. Finally, for $i \in \{1, \dots, I\}$ and $j \in \{1, \dots, J\}$, let $M(i,j)$ denote the element in the $i$th ...
0
votes
0answers
32 views
Location problem — linear programming
I have a location problem I need help with:
Suppose a boat company wants to operate services between 11 ports in a city. The number of return journeys between port i and port j is denoted by a x-...
0
votes
0answers
30 views
Changing domain of solution in Integer Programming
I'm given an inequality $a_1x_1 + a_2x_2 \geq c_1$ where $a, c, x_1, x_2$ are integers and $x_1, x_2 \text{ are either } 1 \text{ or } 0$.
I'd like to construct another inequality $b_1y_1 + b_2y_2 \...
2
votes
0answers
42 views
Computer program for the conjugacy problem of $GL_n(\mathbb{Z})$
In "Solution of the conjugacy problem in certain arithmetic groups" Grunewald provided an algorithm for solving the conjugacy problem of $GL_n(\mathbb{Z})$.
My question is:
Is there some computer ...
0
votes
1answer
23 views
Count the number of unique elements in a vector by linear constraints (ILP)
Let $\mathbf{x}\in \{0,1\}^n$, be the objective variables of an ILP.
Further, let $\mathbf{a} \in \mathbb{N}_{\geq 0}^n$ be a given random vector and $\mathbf{w} = \mathbf{x} \odot \mathbf{a}$ where ...
1
vote
1answer
58 views
If-Then Constraint: If $F(X) > 3$, then $Y = 1$
$F(x) = x_1+x_2+x_3+x_4$
Scenario: Amongst binary variables $X_1$, $X_2$, $X_3$, $X_4$, if more than $3$ are chosen, then another binary variable $Y = 1$. Otherwise, $y = 0$. How can I formulate ...
0
votes
1answer
16 views
What is the minimum distance between vertices on an integer grid with the form $(m(m+2), 0)p + (m, 1)q$?
Suppose, for given $m > 0$, we have a set of points of the form $v = (m(m+2), 0)p + (m, 1)q$, with $p, q, m$ integers. What is the minimum distance between two (distinct ones) of them?
Here is the ...
1
vote
0answers
71 views
Knapsack cover inequalities for a particular covering problem
The Knapsack cover inequalities for a constraint $ A_i x \geq b$ where $x_{j}\in\{0,1\}$ are:
$$\sum_{ j \notin S} \tilde{ a}_j x_j \geq b_i −\sum_{ j \in S } 1 $$
with $\tilde{ a}_j = \min \{...
1
vote
0answers
36 views
Representation of chained XOR operation as a set of linear inequalities
I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met:
$x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$
where $\oplus$ is the binary xor operator.
...
0
votes
0answers
20 views
How do I use an integer programmed mathematical modelling of TSP (travelling salesman problem)?
Okay, so I just finished my mathematical modelling of TSP using integer programming.
Now, how do I use it?
Now, I just want to know to use this model to solve a simple 5 vertices large graph.
You ...
0
votes
0answers
17 views
Property of submodular non-decreasing function
Let $f:\mathcal{P}(N) \longrightarrow \mathbb{R}$
be a set function. $f$ is submodular if
\begin{align}
f(A) + f(B)
&\geq
f(A \cup B) + f(A \cap B)
&\text{for all } A, B \in \mathcal{P}(N),
\...
0
votes
0answers
12 views
Bus fleet requirement for transporting passengers/baggage between airport terminals
I am trying to determine the optimum number of buses required for loading and unloading of passengers/baggage. The buses perform following tasks:
Transport terminating passengers and their carry on ...
0
votes
0answers
33 views
which combination(partiotioning ) has the smallest value?
A positive integer can be partitioned, for example, the number 7 can be partitioned into the following:
$7=7$
$ 7=6+1$ , $ \ \ 7=5+2$,$ \ \ 7=4+3$
$ \ \ 7=4+2+1$,$ \ \ 7=3+3+1$,$ \ \ 7=3+2+2$,
$ \ ...
2
votes
0answers
41 views
Constraint satisfaction problem (CSP) for inequalities of vectors
I have two vectors $Y= (y_1, y_2, \ldots, y_m)^T$ and $S= (s_1, s_2,\ldots, s_m)^T$, where all entries in $Y$ and $S$ being positive integers. $Y$ is defined by $Y = A + B \cdot X$, where $A$ is a ...
1
vote
3answers
102 views
Binary variables in time series: integer linear programming
I'm working on a problem and I can't seem to find an easy solution to it. It's about an optimization problem, concerning a time series.
I have a binary variable $\alpha_t$ for $t \in [0, 24[$. I ...
0
votes
1answer
46 views
Algorithm to find integer combinations satisfying a set of inequalities
I have an engineering problem that is reduced to finding a set of positive integer combinations satisfying several inequalities and some other properties.
Specially, let $\mathcal{S}$ be the set of ...
0
votes
1answer
71 views
Knapsack Problem with Equal Weights
The problem consists in the standard knapsack problem in interger programming with the weights that all have the same values, for example they are all equal to one.
It seems to me that the solution ...
0
votes
1answer
27 views
How do you set up this constraint in integer programming using binary variables?
Mike wants to invest in $X_1$ if and only if he invests into $X_2$ or
$X_3$ or both.
Please help i can't get my head around this
Thanks
0
votes
1answer
70 views
Prove that if the constraints to a linear program are integer, then the optimal solution is rational
I've got the following question that I can't quite figure out.
I have a vague idea of how to do this.
Attempt
Assume, for contradiction, that the optimal solution $x*$ is not rational. This means ...
0
votes
0answers
10 views
Complexity of maximizing sum of fractional functions under cardinality constraint
Considering the following optimization problem:
$max_{x} \ \sum_{i=1}^n \frac{W_i}{D_i - z_i},\quad s.t.\ \sum_{i=1}^n z_i \leq k,z_i\in[0,k]$, where $W_i$ and $D_i$ are postive constants and $z_i$ ...
1
vote
1answer
33 views
Reformulate Absolute values in linear programming
I did not find answer to similar question anywhere so I asking here.
I have a constraint in linear programming model:
$|a-b|=d+g+i~$ where
$~a, b, d, g, i$ are binary.
How should I reformulate this ...
1
vote
0answers
25 views
Matrices whose submatrices have determinant of at must 2
Totally Unimodular matrices, for which every square submatrix has a determinant in $\{0,\pm 1\}$, are well-studied due to their usefulness in integer programming. Has there been any study of matrices ...
0
votes
0answers
93 views
maximizing absolute value in linear programming
I know that this question has been answered several times, and based on the answers, I attempted something. But I simply do not get the right results. The question is as follows. I wish to solve the ...
0
votes
1answer
22 views
Write linear constraints with order in sets
I have $m$ sets $A_1,\ldots,A_m$ and a binary variable $x_{ij}\in\{0,1\}$ for $i\in I$ and $j\in\bigcup_{k=1}^mA_k$. I would like to express these constraints:
If $x_{ij}=1$ for $j\in A_k$, then $x_{...
0
votes
0answers
60 views
Large scale mixed integer (quadratic) programming
Here we have this optimization problem:
Given positive semi-definite matrix $A \in \mathbb{R}^{n \times n }$, and matrix $B \in \mathbb{R}^{n \times m} \text{ and vectors } d \in \mathbb{R}^n,e \in ...
3
votes
1answer
38 views
Transportation problem with the least number of transportations.
I have a non trivial case of transportational problem. Let me get you familiar with it.
We have $n$ suppliers $a_1, ..., a_n$ and $m$ consumers $b_1, ..., b_m$.
The suppliers volume of goods to ...
1
vote
1answer
37 views
Solving an integer (boolean) constraint satisfaction problem
I have a 0-1 integer constraint satisfaction problem of the following form: find binary vectors $x = (x_1,\dots,x_m) \in \{0,1\}^m$ and $y = (y_1, \dots,y_n) \in \{0,1\}^n$ that satisfy the ...
2
votes
2answers
110 views
Given $11x+17y +19z =2561$ , find minimum and maximum of $x+y+z $
Given diophantine equation $11x+17y +19z =2561$ , which $x,y,z \geq 1$
Find minimum and maximum value of $x+y+z$
I'm start with reduces equation to $11x+17y +19z =2514$ , which help us ...
0
votes
1answer
33 views
Why is showing that ILP in NP not trivial
I have a question regarding the topic of showing that ILP is in NP
What is the problem with Guess and Check?
Guess a solution and then check if it is optimal.
Or further:
Calculate a solution via ...
0
votes
1answer
39 views
How to check if point is in elliptical sector without float-point arithmetic?
How can I check whether point lies in elliptical sector without float-point arithmetic if I know a and b from the ellipse ...
1
vote
1answer
47 views
How to formulate a maximum size k-plex problem in integer linear programming?
First, k-plex is a subgraph that each vertex is connected to at least n-k vertices, where n is the size of subgraph.
I found some materials that similar to k-plex : page 5 of
http://citeseerx.ist.psu....
0
votes
0answers
16 views
How to generalize Neumann's minmax theorem to the case where one of the input's domain is discrete?
I know the Nuemann's minimax theorem requires that both of the input's domain to be convex set,but I encounter this problem of the following form
Here A={1,2,...n},V takes continious values,My ...
0
votes
1answer
67 views
How to count occurrences in linear programming
This is an integer linear programming question.
Let $L$, $T$, and $R$ be positive integer values and define the sets $\mathscr{L} = \{1,2,\ldots,L\}$, $\mathscr{T} = \{1,2,\ldots,T\}$ and $\mathscr{R}...
0
votes
0answers
31 views
Integer Optimization with a specific form ($\sum f_{ij} (x_i,x_j)$)
I encountered a series of integer optimization problems that share a similar structure.
The integer variables are $(x_1,x_2,\cdots,x_n)$, where each $x_i$ is non-negative.
The objective function $f$ ...
