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