Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
169
questions
8
votes
4answers
320 views
Understanding integer programming solvers
I would like to verify if I understand the nature or workings of integer programming solvers.
My understanding is that for integer programming problems like the knapsack problem or the traveling ...
3
votes
2answers
199 views
How to get an extreme ray of an LP from Gurobi
I am working on a problem of form
\begin{equation}
\begin{array}{l @{\quad} l}
\mathrm{max}_{x, u} & p^{\top} u
\\
\text{st.} & A u + a x \leq 0
\\
& x \in \{0, 1\...
0
votes
2answers
208 views
How can I formulate this specific if-then constraint?
IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly)
AND
IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly)
$X$ and $Y$ are binary variables.
What I'm actually trying to do is to charge the ...
4
votes
2answers
208 views
How to solve this convex problem heuristically?
I have the following problem
$$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$
$$\text{subject to}$$
$$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$
$...
3
votes
0answers
52 views
Flexible Job Shop with Preemption
I'm trying to solve a flexible job shop problem variant that has precedence constraints on jobs along with a few other issues. We have a MIP formulation and also a simulated annealing algorithm to ...
1
vote
1answer
108 views
Constraint programming and scheduling issues
I have a constraint problem that I need to resolve, but I did not how know to model the problem:
I have 11 employees, I will name them from $a$ to $k$: $\{a,b,c,d,e,f,g,h,i,j,k\}$.
I have a small ...
2
votes
1answer
326 views
Divisibility constraint in Integer programming
I have a simple question regarding the divisibility in integer programming
suppose the objective function is
$\text{max}\quad x_1 + x_2$
where the constraint is that the sum of $x_1$ and $x_2$ are ...
2
votes
1answer
78 views
confusing results of two models with different complexity
i have two models that address the same problem.
the first one is :
the second one is:
for different instances for the same size (n=30) i found the following results ( the first column on the left ...
4
votes
1answer
217 views
How to determine the size of a model?
I want to know about the number of variables and constraints of this formulation (exp: $o(n)$ variables and constraints or $o(n^2)$ ....).
Is the number of variables $\mathcal O(n^3)$ because we have ...
6
votes
1answer
138 views
Literature on “simcity-like” problems
As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that.
I have a set of "buildings" that I want to place on a small 2d ...
-2
votes
1answer
105 views
Any references to the ROADEF 2020 Challenge?
The problem description of the challenge is given here.
Does anyone has some references to similar problem. I would like to participate but I don't know where to start.
2
votes
0answers
76 views
Indicator function for integer variable with inequality constraint
I have $n$ integer variables $\vec{x}$ with the following integer programming problem.
$$
COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0)
$$
Here, $a_i, b_j \in \mathbb{R}_+$ ...
2
votes
1answer
40 views
Finding bounds on a data sensitivity scenario ILP problem
This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem
As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
3
votes
1answer
176 views
Issue in solving a large scale MIQP problem
I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below.
\begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...
2
votes
0answers
96 views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
0
votes
0answers
36 views
Interger programming using gray encoding
Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
3
votes
2answers
678 views
What are the solvers that give a feasible solution within a given time?
What are the solvers that take the maximal computation time as a parameter and gives the best found feasible solution within this time.
3
votes
2answers
97 views
Modelling a data-sensitivity scenario as an ILP problem
I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve:
When publishing data, it is sometimes important to "suppress" sensitive ...
0
votes
0answers
40 views
Linearizing max constraint Problem [duplicate]
I want to linearize a max constraint as below:
In which x_(i,t),are binary decision variables and T is a constant.
How can I linearize this constraint?
3
votes
0answers
40 views
How to find all covers and minimal covers?
Consider a constraint of type
$$c_1x_1+c_2x_2+\cdots+c_nx_n\leq C$$
with $x_i$ binary.
We call a cover a subset of the $n$ indices such that the sum of the corresponding coefficients is higher than ...
1
vote
2answers
91 views
How this problem can be defined as MultiObjective optimisation
I need to optimize the end-to-end latency of a multi-component application.
Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
5
votes
0answers
140 views
When is there at least an integral point in a polyhedron?
This problem comes from a problem of economics. Let $x\in [0,1]^n$. $\{x_1,x_2,\ldots,x_n\}$ is partitioned into ${S_1, S_2,\ldots,S_k}$ such that $\sum_{x_i\in S_j}x_i\leq 1$ for each $1\leq j\leq k$....
1
vote
2answers
176 views
Switching of decision variables to be larger than or equal to a decision variable according to an indicator variable value
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is greater than or equal to a ...
4
votes
1answer
148 views
Switching of decision variables to be equal to a certain decision variable according to a binary (indicator) variable
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is to be equated to a third ...
7
votes
1answer
162 views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
4
votes
2answers
184 views
Formulating the conditional constraint
I want to develop a model extension of capacitated location problem.
The variables are a binary $x_i$ and a continuous $Q_i$. The following condition must be satisfied:
if $x_i = 0$, $Q_i$ must be ...
3
votes
1answer
82 views
Integer decision variables as index
The following problem has only two integer variables; however, they appear in the index of the parameters. Appreciate it if anyone has any efficient idea to transform it into a canonical integer ...
3
votes
0answers
63 views
Theoretical aspect of using extended formulation
If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...
5
votes
0answers
82 views
Are there any good models for min-max vehicle routing problem?
I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
3
votes
0answers
34 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
5
votes
1answer
55 views
Min-cost flow with per-edge flow conservation
I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint.
Instead of the summed outgoing flow equaling the summed ...
4
votes
3answers
205 views
Faster implementation of “or” constraints in ILP
I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
10
votes
6answers
2k views
Nonlinear integer (0/1) programming solver
I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
6
votes
2answers
192 views
Linear objective function with non-linear constraints
I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type
$$
\underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\
$$
subject to the ...
4
votes
2answers
273 views
Combinatorial Optimization using AMPL
I want to solve the following integer programming problem using AMPL. The problem is the following (It was already asked on mathstackexchange.com, but I need to know how to solve it using AMPL):
Let $...
7
votes
1answer
173 views
CPLEX MIP warm start seems slow down the program?
I have been working on a combinatorial optimization problem which can be modeled as an integer linear programming. I implemented it as a c++ project in visual studio 2017 and CPLEX1271. With the hope ...
3
votes
1answer
180 views
Formulation of Assignment problem as integer programming
We need to maintain as quickly as possible a complex system. In particular, we need to replace six of its components $\{P_1,\ldots,P_6\}$. We have three 3D printers $\{M_1,M_2,M_3\}$ which we can use ...
5
votes
2answers
195 views
What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?
Say that I have a binary IP
$$z=\max_x \{c^\top x: Ax=b, x\in B^n\}$$
where $B^n$ is the set of $n$-dimensional $0-1$ vectors.
Its LP relaxation will be
$$z^{LP}=\max_x \{c^\top x: Ax=b, 0\leq x\leq 1\...
4
votes
1answer
326 views
Indicator function in math programming
Let $x$ be an integer variable that takes the values $1$, $2$ or $3$.
Let $y_1$ and $y_2$ be binary variables.
I want to express the two following logical constraints:
if $x=2$ then $y_1=1$
if $x=3$ ...
2
votes
0answers
151 views
Operation hours optimization for circular schedule
Here is my problem. A store has X = 15 electical devices with the ability to work non-stop, fully charged, up to 8 hours. Their battery charge lasts 2 hours and the operating hours of the store differ ...
4
votes
1answer
83 views
Make Optimization term fit into DCP rules
I want to make a term in an objective function I am working with fit into DCP for CVXPY.
I am working on replicating this research paper for an active learning problem. Specifically equations 5 is ...
5
votes
3answers
194 views
How can I optimize this integer programming constraint problem without running out of memory?
I am trying to run this constraint problem but the memory runs out, $$S_{i}$$ are 1975 Students that need to be assigned to one of 188 teacher assistants classes, each teacher assistant has to chose a ...
2
votes
1answer
153 views
Formulation of assignment problem as Linear Optimization
In the anti-tumor treatment with radiotherapy, it is possible to irradiate the tumoral mass from different positions with different intensities. For each of these possibilities, however, one has to ...
4
votes
1answer
79 views
Formulation of Machine allocation as an optimization problem
A manufacturing company from Eastern Finland will have to decide on the machines to use in order to produce 2800 units of a given item. Each machine has some given characteristics: a setup cost if it ...
3
votes
2answers
584 views
How to add logical OR constraint in OR-Tools?
Let's say nurses normally do 1 shift
for d in all_days:
for s in all_shifts:
model.Add(sum(shifts[(n, d, s)] for n in all_nurses) == 1)
But I want to ...
2
votes
4answers
83 views
Linearity of an optimization problem which comprises the product of variables with constant values from a non-linear function
In a mathematical integer optimization problem, if the objective function is represented as $\sum x_k \cdot M_k$, where $M_k$ is a non-linear function whose value is known and just plugged in to the ...
4
votes
3answers
939 views
Branch and bound algorithm programming code
I want to solve an integer programming problem using the branch and bound method, but I'm having trouble finding the programming code. From what I saw, almost all algorithms use it for traveling ...
3
votes
1answer
105 views
What kind of scheduling problem is this?
I am trying to develop algorithm to solve following basic version of the problem.
1) I would like to know what this problem is called in literature so that I can look it up
2) What are efficient ...
7
votes
1answer
1k views
How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour
I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colours to colour the routes, ...
9
votes
3answers
1k views
Open source MILP solver for quick “good enough” solution
I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
