Questions tagged [integer-programming]
Questions on optimization constrained to integer variables.
0
votes
1answer
13 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 ...
0
votes
0answers
8 views
Knapsack cover inequalities for a particular covering problem
Now sure where to find the answer to this, anyways the Knapsack cover inequalities for a constraint $ A_i x \geq b$ are $\sum_{ j \notin S} \tilde{ a}_
j x_j \geq b_i −
\sum_{ j \in S } 1 $ $...
1
vote
0answers
21 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
15 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
13 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
10 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
31 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
38 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 ...
0
votes
3answers
76 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
43 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
29 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
25 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
40 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
8 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
28 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
56 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
21 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
33 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
36 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
35 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
106 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
29 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
38 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
43 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
15 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
42 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
29 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$ ...
0
votes
2answers
55 views
How to basically solve Integer programming problems?
I learnt to solve the task below Linear Programmming is employed. I have tried studying texts to better understand what methods to employ out of the following:
$(A) Gomory's-cut$
$(B) Mixed-Gomory's-...
1
vote
0answers
29 views
Under what condition, the optimal solution of assignment problem is unique?
Is there any conditions that can make the optimal solution of a assignment problem unique?
I know if there is no conditions on the cost matrix, it is not guaranteed to have a unique solution. (e.g. ...
-1
votes
1answer
36 views
Reducing data sparsity in linear integer programming
I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix ...
0
votes
1answer
105 views
Integer Linear Programming: Sum of Products of Binary Variables
Given four sets of binary variables $x_{1..N}$, $y_{1..N}$, $v_{1..N}$, and $w_{1..N}$ such that $\Sigma_{i=1}^{N} x_i = \Sigma_{i=1}^{N} y_i = \Sigma_{i=1}^{N} v_i = \Sigma_{i=1}^{N} w_i = 1$, I need ...
0
votes
0answers
29 views
Integer Programming in cubic time?
A paper I found while researching graver bases appears to claim that IP would be solvable in cubic time ($O(L\cdot n^3)$). However, even after the third attempt to understand what's going on I still ...
0
votes
1answer
70 views
How to linearize (or convexify) a function that takes the maximum of binary variables?
I have the following optimization problem in binary variables $x_{ij}$ and $y_i$.
$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i} y_i \max_j \big( c_{ij} x_{ij} \big)\\ \text{subject ...
0
votes
1answer
70 views
Is there any algorithm available for this kind of optimization problem
My optimization problem is to design a $n*m$ matrix consisting of only $0$ and $1$ as elements, such that the sum of each column is not less than a number given as the constraints. The constraints is ...
4
votes
0answers
77 views
When does an equation of the form ${1 \over p}{(2^{p-1}-1)} = 2pxy+x+y$ have no integer solutions?
Specific equations of the form below (for different given values of p, a prime number) will either have positive integer solutions for $x$ & $y$, or will not have any integer solutions.
$${2^{p-1}...
0
votes
1answer
26 views
How to calculate maximal square size when fitting N squares in a given container?
Given a container which width is W and height is H, I'd like to fit N squares of maximal ...
0
votes
0answers
35 views
Convert the following model to quadratic integer programming
Really having a hard time with this.....Convert the following model to a quadratic integer program:
Maximize $Ay$ subject to $Bx \leq d$ and $y\in$ argmax $x^TMy.$
Does anyone have any idea? Or ...
0
votes
1answer
41 views
Convert fractional to quadratic integer programming
Maximize $\frac{\sum_i\sum_ja_{ij}x_iy_j}{(\sum_ix_i)(\sum_jy_j)}+ \frac{\sum_i\sum_jb_{ij}x_iz_j}{(\sum_ix_i)(\sum_jz_j)}$, subject to $Ax+By+Cz \leq d, \quad x,y,z\in \{0,1\}$.
Can we convert the ...
0
votes
0answers
71 views
Iterating over a set of elements in CPLEX OPL
I am trying to model the following constrain in OPL. Here πG is string set.
$$ r >= \sum_{k=1}^{Np-1} y(k,k+1) \quad \quad \quad \quad
∀p∈ πG $$
Here is how I tried it in CPLEX OPL,
<...
0
votes
0answers
29 views
A nonlinear integer programming problem?
I have an optimization problem which is formulated as shown below where (1a) gives the objective function and (1d)~(1f) give the constraints with $x_{ij}$ and $y_i$($i,j=1,2,...,n, i\neq j$) being the ...
0
votes
0answers
31 views
Discovering primary factors using matrix decomposition
I'm attempting to formulate the following problem as a standard matrix decomposition. So far, I've managed to express it formally but not convert it into a standard kind of decomposition. Any help ...
-1
votes
1answer
21 views
Satisfiability of inequality array with binary and arithmetic operators
I have a problem as follows. Really appreciate if anyone can give me some suggestions.
I have $4000$ binary variables $\{x_0, x_1,...x_{3999}\}$ and $4000$ inequalities which have both binary ...
0
votes
0answers
52 views
Linearizing If-Then condition
Somewhere in the internet, I have read that,
suppose, $x, y \in \mathbb{R}, ~and, ~~~ z \in \lbrace 0,1 \rbrace$
$\text{if}~ x>y, ~\text{then,}~ z = 0 \implies \text{if}~ z = 1, ~ \text{then,}~ x ...
1
vote
1answer
41 views
Is the LP-relaxation value on a subset of variables a bound for that subsets value in the MIP solution?
Say we're given the following integer problem:
$\min c^Tx$
s.t
$Ax \leq b$
$x \in \{0,1\}^n$
and its corresponding LP-relaxation:
$\min c^Tx$
s.t
$Ax \leq b$
$x \in [0,1]^n$
Then we can ...
0
votes
1answer
102 views
Consecutive One's and Identities, resulting on Totally Unimodular Matrix…
I'm trying to prove that a linear problem has integer extreme points. Looking at the matrix structures, I guess the easiest way to prove this is by showing that this matrix is totally unimodular. My ...
3
votes
1answer
150 views
how can use method for more than two constraint?
I have a problem with inequality constraint. And I'm going to merge the constraints.I know that we can add surplus and slack variables in order to achieve equality constraints. And then use below ...
0
votes
0answers
54 views
Groebner base optimal solution with inequalities
I have to solve the following optimization problem using Groebner bases. The objective function is
$$x_1+x_2+x_3+x_4$$
with constraints
$$x_1+x_2 \ge 1, \qquad x_1+x_2+x_3 \ge 1, \qquad x_2+x_3+x_4 ...
4
votes
1answer
97 views
Algorithm to solve a system of linear inequalities over the natural numbers
I am looking for an algorithm to solve a system of linear inequalities of the form
$$A\,\vec n + \vec c \;\geq\; 0$$
for $\vec n$ where $A$ is a matrix of integers, $\vec c$ consists of integers and ...
0
votes
1answer
12 views
Solving Disjoint verteces paths problem using column generation
I am faced with the following integer optimization problem which I am trying to solve using column generation:
Given is a digraph $G(V,A)$ with a source and sink node ($s, t$). Each path has a ...
