Questions tagged [integer-programming]

For questions about mathematical optimization problems involving binary or general integer variables.

Filter by
Sorted by
Tagged with
4 votes
1 answer
637 views

Can sensitivity analysis and limits report be done on an BILP problem?

I am not that experienced with Operations Research yet. I have become familiar with what Sensitivity Analysis and Limits Reports are in general and through the use of Excel. I know that they can only ...
Tita's user avatar
  • 205
1 vote
2 answers
238 views

Capacitated Maximum Coverage Location Problem, Python and Gurobi

I am trying to solve a capacitated MCLP problem with two additional constraints. Non-overlapping circles Minimum and Maximum value for the capacity for a circle. for 2nd constraint, I am able to add ...
Nandy's user avatar
  • 13
1 vote
1 answer
178 views

How to write this logical expression with Gurobi + Java, or express it as a big-m formulation

I am trying to write the following expression in Gurobi+Java or Gurobi+python, if it is more practical It could be expressed as a big-M formulation. \begin{equation} \label{const4} \text{D}_{uv} = ...
Hernan19's user avatar
2 votes
4 answers
451 views

How to approach this shifts problem with Excel Solver?

I am trying to find a way to solve the following problem of mine by using Solver but I get stuck right at the end of it. I have a table of 14 companies each of which want to work on a project. I will ...
Tita's user avatar
  • 205
5 votes
1 answer
668 views

How many variables and constraints can modern mixed integer programming solvers handle?

I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there: "I know ...
graphtheory123's user avatar
1 vote
0 answers
56 views

How to avoid complementarity constraints in continuous nonlinear program?

In my two-stage continuous NLP problem, I have a constraint in second stage: $X_{g,k}$ = $X_{g,0} + a_{g} d_{g} $, if $X_{g,k} \in [X_g^u,X_g^l]$ $X_{g,k} = X_g^u$, if $X_{g,k} \geq X_g^u$ $X_{g,k} ...
Ghulam Mohy-ud-din's user avatar
1 vote
2 answers
176 views

How to express this constraint efficiently?

Let, $\mathcal{C}=\{1,2,\cdots,C\}$, $\mathcal{U}=\{1,2,\cdots,U\}$ $\mathcal{S}_u$ is a subset of $\mathcal{C}$ with $u\in \mathcal{U}$ $d_{u,c}$ is a binary variable with $u=1,2,\cdots,U$ and $c=1,2,...
KGM's user avatar
  • 2,211
3 votes
2 answers
228 views

Modifying and re-optimizing a model using CPLEX Python API

I came across the following functionality that is offered by CPLEX for modifying and re-optimizing a model based on previous computations: https://perso.ensta-paris.fr/~diam/ro/online/cplex/cplex1271/...
Pia MiA's user avatar
  • 392
1 vote
1 answer
106 views

How to model and solve such a 0-1 programming problem

My problem is described in this picture(It's like a Pyramid structure): The objective function is below: $$\min\sum_{k=1}^\ell\sum_{i=0}^{2^k-1}\sum_{j=0}^{2^k-1}\left(A_{i,j}^k-A_{i,j+1}^k\cdot\frac{...
happy's user avatar
  • 63
2 votes
1 answer
127 views

Conditional constraint for binary

Could you please check where I might be wrong? Task is: If $z=1$, then either $x=1$ or $y=1$ My approach: If $z=1$, then $x+y=1$ $\implies x+y\le1$ $\implies x+y\ge1$ If $z=0$, then $x+y\ge0 - M\cdot(...
Bohdana Nevierova's user avatar
6 votes
2 answers
217 views

Breaking symmetry of permutations in LIP

Setup I have a $N \times M$ matrix with integer values and I need to group it into $K$ groups (subject to constraints). Internally I work with a flattened 1D list as I don't see any benefits of using ...
armset's user avatar
  • 73
2 votes
1 answer
85 views

Expressing inner product of binary variables in MIP

I have a $m$ by $n$ matrix $X$ of binary variables in my MIP which represents a list of $m$ items each belonging to one of $n$ categories. $m$ is usually around $1,000$ while $n$ is much lower at ...
Anish Shanbhag's user avatar
2 votes
3 answers
538 views

How to find the index of the item, the first time appears?

How to formulate this problem as MIP: For example, we have the following vector of binary variables: $$ x= [0, 0, 0, 1, 0, 1, 1] $$ How to find out when the first "1" is recorded? For ...
Hussein Sharadga's user avatar
4 votes
3 answers
433 views

How to transform a logical constraint with integer variables?

Consider the binary variables $x_1, x_2 \in \{0,1\}$ and the integer variable $y \in \mathbb{Z}$ with $0 \leq y \leq 3$. I'd like to formulate the following logical constraint: $$ x_1 = 1 \wedge y \...
Ronaldinho's user avatar
1 vote
1 answer
109 views

ILP program to find a centrosymmetric Hadamard matrix

A question in mathoverflow asks if there exists a centrosymmetric Hadamard matrix of order 36. An $n \times n$ matrix $A = (a_{i,j})$ is centrosymmetric if: $$a_{i,j} = a_{n-i+1, n-j+1}, \space i=1,\...
Fabius Wiesner's user avatar
1 vote
1 answer
243 views

Create constraint when variable is within a given range MILP

What is the best way to specify whether a given variable is within a given range in Pyomo? Here I have a binary decision variable assign[t, e] which I want to ...
Pia MiA's user avatar
  • 392
2 votes
1 answer
49 views

How to get the fractional solution of a node in a MIP model using JuMP package?

I'm coding in Julia and use the JuMP package. My IP solver stops by a fixed node limitation. I noticed that I can only get the feasible primal and dual solution if has any, however I would like to get ...
Brown's user avatar
  • 173
3 votes
1 answer
73 views

Can we turn a Binary IP model into a problem solvable using Local search?

I am new to the fields of operations research. I have a Binary IP model for solving a scheduling problem and I am seeking to find information whether I can somehow transform it to a problem that can ...
Pia MiA's user avatar
  • 392
2 votes
2 answers
73 views

How to model this?

$i$ is a set $1$ to $n$. $j$ is a set $1$ to $m$. $j$ and $k$ are from the same set such that $j\neq k$. $c_{ij}$ is a parameter. $x_{ij}$ and $y_{j}$ are binary variables. How to model: If $$c_{ij}\...
user avatar
4 votes
1 answer
75 views

Another difficult constraint for an ILP

How can I add to this ILP with all binary variables (again related to this question): $$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} \ge \lfloor (n-1)/2\rfloor \qquad \...
Fabius Wiesner's user avatar
5 votes
3 answers
679 views

Constraint for two binary vectors to be different

If I have a matrix $A$ of binary variables $a_{i,j}$, $1 \le i \le n$, $1 \le j \le m$, how can I enforce in an Integer Linear Program with binary variables, the condition that every two columns must ...
Fabius Wiesner's user avatar
4 votes
1 answer
187 views

Difficult linearization of a constraint

My previous question was about this ILP with all binary variables: $$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$ $$...
Fabius Wiesner's user avatar
3 votes
2 answers
100 views

How to model if-then?

$i$ is a set $1$ to $n$. $j$ is a set $1$ to $m$. $j$ and $k$ are from the same set such that $j\neq k$. $c_{ij}$ is a parameter. $x_{ij}$ is a binary variable. How to model: If $$c_{ij}\cdot x_{ij} \...
user avatar
4 votes
2 answers
479 views

Expected ILP solving time and how to improve speed

I am trying to solve this ILP with all binary variables: $$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$ $$a_{k,i} + ...
Fabius Wiesner's user avatar
3 votes
2 answers
236 views

Simple Integer Optimization Problem: docplex CP model works but equivalent PuLP+CBC model is infeasible?

I have an integer optimization problem with one constraint per decision variable and no objective function. It can be coded and solved using docplex, however I am ...
SlowLoris's user avatar
  • 145
3 votes
0 answers
87 views

Minimize total cost to buy unique products over timespan

I am looking for some guidance on how to better state my problem formally and practically (e.g., relevant Python libraries). Let's assume I have a set of $X$ unique products to buy. I have $Y$ days in ...
M2FKXY's user avatar
  • 31
3 votes
1 answer
182 views

Assignment problem with mutually exclusive constraints has an integral polyhedron?

I have the following problem $\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij} $ $s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$ $\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I $ $\...
sgk's user avatar
  • 33
1 vote
1 answer
96 views

convert x=min(x, N) function into a constraint, integer programming python

In this case, the shop want to maximise the profit that is there $n$ products the shop can procure, but the shop only has $w$ budget. The cost of each product $x_i$ is $c_i$. I used prediction model ...
mmmm's user avatar
  • 21
5 votes
2 answers
103 views

Is there an efficient/polynomial way to detect/determine whether a polyhedon contains at least an integer point?

How to determine whether a convex polyhedron described by a set of linear inequalities contains at least a or no integer point in polynomial time, which is to say detecting the IP feasibility ? ...
Brown's user avatar
  • 173
2 votes
2 answers
101 views

Is there a name for this type of integer programming?

Let $x_i$ be a decision variable, and let $c_i$ be the coefficient for the decision variable $x_i$. An integer programming problem is where the goal is to: $\text{maximize} \quad \sum_i c_ix_i$ $\text{...
LambdaPsi's user avatar
  • 133
1 vote
0 answers
40 views

Is there a name for this type of integer programming? [duplicate]

Let $x_i$ be a decision variable, and let $c_i$ be the coefficient for the decision variable $x_i$. An integer programming problem is where the goal is to: $\text{maximize} \quad \sum_i c_ix_i$ $\text{...
LambdaPsi's user avatar
  • 133
-2 votes
1 answer
86 views

constraints for a zero-one integer programming problem

We want to arrange 8 tables in 2 rooms. How to write the following constraints? Either table 3 or table 6 must be in room 1 (or both). Exactly one of tables 7 and 8 must be in room 2.
ebrahimi's user avatar
  • 115
5 votes
1 answer
108 views

Identifying the variant of such a knapsack-like problem

I am not too familiar with variants of knapsack problems (or variants of possibly other classical OR problems), but I would like to identify the following Integer Programming problem: $$\min_{x_i,y_{i,...
Vergil's user avatar
  • 51
3 votes
2 answers
304 views

How to model logic constraint: $y=1$ if $a\le x\le b$ and $y=0$ otherwise?

I am trying to formulate indicator-type of constraints. $y$ is binary $0$ or $1$ and $x$ is a continuous variable. $$ y = \begin{cases} 1, & \text{ if } a \leq x \leq b \\ 0, & \...
GuanghuiLiu's user avatar
2 votes
1 answer
87 views

Could non-supported efficient solutions in multi-objective optimization problem be an optimal solution of a parameterized single-objective problem?

Since all supported efficient solutions in a multi-objective optimization problem are actually the optimal solutions for some weighted sum scalarization single-objective optimization problem with the ...
Brown's user avatar
  • 173
2 votes
1 answer
118 views

Linearize a product of binary variables with 2 indexes

I have the following inequality that I would want to linearize. Consider that $r_{ij}, x_{ij}, y_{ij}$ are binary variables defined for every pair of nodes $(i,j) \in A$. Also, I have a set of nodes $...
Nicolas Zerega Oyarzun's user avatar
4 votes
1 answer
469 views

Is this a non-linear integer model?

Let's say if I have two decision variables, $f$ and $g$ respectively, where $f$ is continuous, and $g$ is binary. If I have a constraint like this, $$ f\cdot g \le C$$ Does this make my model ...
overboxed's user avatar
  • 593
2 votes
1 answer
207 views

How to write constraint with sum of absolutes in Integer Programming?

I found a solution for just one term here How can we formulate constraints of the form $$ \sum_{i=1}^n |x_i -a_i| \ge K $$ in Mixed Integer Linear Programming ?
Vinay's user avatar
  • 203
1 vote
1 answer
98 views

What is the meaning of this multi commodity formulation VRP in LINGO

Can someone tell me what is the meaning of this multi commodity flow formulation that I got in LINGO ? I have the brief explanation about the model but don't quite understand the logic behind, here is ...
overboxed's user avatar
  • 593
7 votes
2 answers
866 views

Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value

So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$ I was interested in posing a constraint so that in the collection $...
Vogtster's user avatar
  • 205
3 votes
1 answer
102 views

How to pose the constraint for binary variable to indicate if quantity is zero or greater than zero

So if I have some quantity bounded i.e $ 1-N \leq (p^i-p^{i+1}) \leq N-1,$ for $N\ge1 $. The quantity $p^i-p^{i+1}$ will be an integer as well. I was trying to figure out how to pose the constraint so ...
Vogtster's user avatar
  • 205
4 votes
1 answer
220 views

Accelerating an integer programming model

I am working on a scheduling problem, where I am solving it through column generation. The pricing problem of this algorithm is an integer programming model as follows: \begin{equation} F_1 \Big\{V^...
mdslt's user avatar
  • 573
2 votes
0 answers
68 views

Multi Commodity VRP Time Windows Paper

I have been wondering is there any paper that who discuss multi commodity with four index/indices like this formulation below: $$ \begin{gathered} \sum_{k} \sum_{c} F_{j, j, c, k}=1 \quad \forall j \\ ...
overboxed's user avatar
  • 593
3 votes
1 answer
120 views

Modeling a special case of conservation of flow

At a particular mode, there are 2 inflow arcs, a and b, and two or more outflow arcs, which is kept to 3 for this example, i.e., c, d and e The first requirement is that only one of the two inflow ...
Mike's user avatar
  • 707
3 votes
1 answer
195 views

Integer programming books

I would like to know which books are best to study integer programming. I can see similar questions on this website, such as this one: Books for integer and mixed integer programming Integer and ...
Jonn's user avatar
  • 333
0 votes
1 answer
59 views

What is the meaning of this math formulation?

I have been wondering what is the meaning of this sigma with delta negative or plus in there (if my read is correct). $$ \sum_{i \in \Delta^{-}(j)} x_{i j k}-\sum_{i \in \Delta^{+}(j)} x_{j i k}=0 \...
overboxed's user avatar
  • 593
4 votes
3 answers
203 views

Is this ILP formulation for Group Closeness Centrality a column generation approach?

I want to solve the Group Closeness Centrality problem where the input is a graph $G=(V,E)$ and integer $k$ and we want to find a vertex set $S$ of size $k$ minimizing the total distance of the ...
Christian Komusiewicz's user avatar
1 vote
2 answers
154 views

Include dataframe linear optimization in r

For a linear optimization problem I want to include a dataframe (d_ij) which has binary variables, 1 if customer i is located within the assignable distance of facility j, 0 otherwise. So unless d_ij =...
user9867's user avatar
9 votes
2 answers
1k views

Gurobi finishes with 'infeasible' although optimal solution exists

I am using Gurobi (in Python through gurobipy) to solve an IP on tournament graphs. I am searching for a non-zero minimal integer weighting such that for every vertex the sum of weights put on the ...
Legsleg's user avatar
  • 153
3 votes
1 answer
199 views

Multiprocessor Scheduling Problem: How to modify some constraints after variable changing?

I am thinking about classic problems concerning partitions as the Multiprocessor Scheduling Problem (or Bin Packing or Number Partitioning): Given $n$ tasks, with times $\{t_i\}_{i\in I_n}$, and $m$ ...
Alexandre Frias's user avatar

1
2
3 4 5
7