Stack Exchange Network

Stack Exchange network consists of 175 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.

2
votes
0answers
57 views

(Strong) Duality for the integer programming for $\text{gcd}(c_1, c_2, \ldots, c_n)$

It is known that (quoted from CLRS, 3rd edition) If $a$ and $b$ are any integers, not both zero, then $\text{gcd}(a, b)$ is the smallest positive element of the set $\{ax + by: x, y \in \mathbb{Z}\}...
2
votes
2answers
29 views

Strict inequality logical implication in optimization problems

I have $ x \in \{0,1\}$ and $y \geq 0$ and I want to model that $x=1$ iff $y>0$, is this possible while keeping the constraint linear? Thanks. One part of the implication is easy $ y \leq Mx$. The ...
1
vote
2answers
52 views

If then convex condition in mixed integer linear programming with binary variables

I have a convex polynomial $f(x_1,\dots,x_t)$ where $x_1,\dots,x_t\in\mathbb R$ and constant $a$. If condition $$f(x_1,\dots,x_t)\leq a$$ holds I have to make variables $y_1,\dots,y_n\in\mathbb R$ ($...
0
votes
1answer
41 views

Assign sequence based on simple calculation

I'm developing a model for truck sequencing at a warehouse. I want to sequence the trucks based on a value ($Q$) equal to the multiplication of their priority ($\alpha$), arrival time (continuous ...
0
votes
0answers
21 views

Division with replacement of floating-point arithmetic to integer arithmetic

The issues: Not all the hardware has an FPU => not possible to use floating-point arithmetic. Not all the hardware has an uint64_t => not possible to use ...
0
votes
0answers
28 views

Minimum number of binary integer variables to handle $AND$ and $OR$ implications in Mixed Integer Linear Programming?

Suppose I want to have an integer program for handling the cases $(x_1>1)\wedge(x_2>1)\wedge(x_3>1)\wedge\dots\wedge(x_n>1)\implies\delta=1$ $(x_1>1)\vee(x_2>1)\vee(x_3>1)\vee\...
0
votes
0answers
24 views

Optimization - production in two categories

I ran in to this idea in a homework assignment, but here's the general idea which I'm having trouble formulating. Imagine you have two producers $x_1$ and $x_2$ which can produce in two different ...
1
vote
1answer
21 views

OR equality constraint for binary integer program

I am trying to find a way to implement an OR equality constraint in a Binary Integer Program. For example, say I want to add the following logical condition to the program: $$x_1+x_2+x_3+x_4+x_5 = 1\...
0
votes
1answer
29 views

Is this problem solvable with positive integer linear programming?

I have the unknowns $w,x,y,z$ that are all in $\mathbb{N}$ and $\gt0$. The known parameters $\alpha,\beta,\gamma,\delta$ are all in $\mathbb{N}$ and $\gt0$ too. Given $\alpha,\beta,\gamma,\delta$, I ...
1
vote
1answer
32 views

Modeling $t \in [a,b] \; \Rightarrow y_{[a,b] }=1$, asking for alternatives if any

Suppose you have a variable $t\ge 0 $, I want to model the following statement : $$ t \in [a_i,b_i] \; \Rightarrow y_i =1 $$ I am assuming $t$ belongs to a unique interval among the ones proposed. I ...
1
vote
2answers
68 views

integer programming???

I have a math problem and I would like to solve it, but I'm not sure what area to look under. Basically given $x \in \mathbb{R}^k$ (for my purposes, $x \in \mathbb{Q}^k$ since I am using a computer) ...
1
vote
1answer
42 views

Correctness of integer reformulation in the FICO MIP quick reference

I have stumbled upon an industry quick reference for MIP formulation by FICO: However, after checking their writing on section 2.3 Maximum value. It seem that there are problems with their ...
0
votes
0answers
45 views

Optimize the product of three binary variables: convex relaxation and integer solutions

I am working on a problem related to graphs and I formulated the problem as follows: $$\max_{y,e} \sum_{i=1}^n (c_i^1 y_i^1 + c_i^2 y_i^2) + \sum_{(i,j)\in E}(d^1y_i^1y_j^1e_{ij} +d^2y_i^2y_j^2e_{ij})...
0
votes
0answers
24 views

How to reformulate (or model differently) the sum of fractions in the objective of integer program?

I have the following (integer) program: $ \max \sum_{i\in I} \frac{a_i}{b_i + \sum_{j\in J} c_{ij} x_{ij}} $ s.t. $ x \in X $ $ x_{ij}\in \{0,1\}, \quad\forall i\in I \wedge j\in J $, where $ a_i ...
0
votes
1answer
18 views

Integer programming, elimination of products of variables and transfer it to linear integer program

I have a constraint of the form: $a_1*a_2 = b_{12}$ where $a_1$ and $a_2$ are integer variables with ranges $a_1∈[{0,1,2,...,m}]$, $a_2∈[{0,1,2,...,n}]$, and $b_{12}∈[{0,1,2,...,m*n}]$. I would ...
1
vote
1answer
45 views

Correct terminology for optimization problem

An optimization problem aims to minimize the sum of a variable u over a time-series. It is made of three variables that are in a linear relationship. Two binary variables $$x_1, x_2, \dots x_n$$ and ...
0
votes
1answer
28 views

Total Unimodularity in Integer QP

I have a Quadratic Programming problem with linear constraints. My objective is Quadratic-Convex, the constraint matrix is Totally Unimodular (similar to assignment or network flow problems), and the ...
0
votes
0answers
24 views

Equivalence between convex and integer optimization problems

Under what conditions does a convex optimization problem have the same solution as a corresponding integer problem? (By corresponding, I mean if we force the optimization variables of the convex ...
0
votes
1answer
51 views

Writing integer programming math statements

I am currently in a linear programming class, and we are on the topic of integer programming. I am asked to write certain relationships in "integer mathematical formulation" with binary ($y_i$), ...
0
votes
1answer
35 views

Prove projection of convex hull = convex hull of projection

I'm not sure how to show this: $proj_x(conv(S)) = conv(proj_x(S))$ where S $\in R^{n+p}$
0
votes
0answers
17 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
1answer
11 views

Variable selection in mixed linear integer programming or mixed integer programming with convex constraints and objective

I have a binary variable $b\in\{0,1\}$ and three real variables $x,y,z$. If $b=0$ then I want $x=y$ and if $b=1$ then I want $x=z$. Is this possible with mixed linear integer programming? Is this ...
0
votes
0answers
20 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
39 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
72 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
74 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
38 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
37 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
29 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
47 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
54 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
44 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
32 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
27 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
86 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
30 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
34 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
43 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
26 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
88 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
22 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
79 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
54 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
23 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
19 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
35 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$, $ \ ...