Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...