Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
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 ...