Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
5
votes
0answers
43 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
25 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
0answers
27 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 ...
3
votes
2answers
79 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 ...
9
votes
6answers
1k 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
130 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
229 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 $...
6
votes
1answer
124 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 ...
5
votes
2answers
124 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
194 views

Indicator function in math programming

I have the following doubt: Being $x$ an integer variable that takes the values $1$, $2$ or $3$. Being $y_1$ a binary variable. Being $y_2$ a binary variable. I want to express the two following ...
2
votes
0answers
129 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 ...
2
votes
1answer
53 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
164 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
127 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
71 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
193 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
76 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
298 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
83 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, ...
8
votes
3answers
833 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 ...
5
votes
1answer
74 views

Linearize a product of an integer variable (not just binary) and a continuous variable?

I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally ...
4
votes
1answer
123 views

How to set these constraints in a linear optimization problem (PuLP)?

I am trying to implement an employee (nurse) scheduling problem and seek some advice on how to implement a specific constraint.The problem is as follows: There is a set of employees and days (both ...
2
votes
1answer
49 views

Inequality Constraint Linearization of a product of an integer and a binary variable

I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable? But the answers to that questions didn't help me find a solution for my ...
5
votes
3answers
76 views

Requiring exactly $n_j$ slots for job $j$ (if scheduled)

Let $x_{j}(t)=1$ iff job $j$ is scheduled at time $t$. I want to say that if the job is scheduled at all, then it is scheduled at $n_j$ slots. I wrote this as: $$x_{j}(t)\sum_{s=1}^{T}x_{j}(s)=n_jx_{...
3
votes
1answer
85 views

Problem solving a linear program using Excel

The exercise is as follows: ACI has decided to put an order for golf shoes twice every year and expects to receive one shipment of $960$ pallets of shoes by the beginning of January and another ...
3
votes
2answers
206 views

Mocking up conditional statements in LP

I would like to know how if condition statements in linear programming can be reformulated using indicator constraints, and hence solved as a mixed integer linear program. Specifically: 1. Is it ...
4
votes
1answer
42 views

Inputting logical constraints into a binary programming model in Gurobi

I am very new to Gurobi and OR in general (I'm in my first class for it now), so apologies if this is a very obvious answer. For a project in that class, I am generating a flight schedule for a ...
16
votes
7answers
2k views

Does there exist an aggregation of videos on optimization?

Is there a website or otherwise maintained list of talks regarding mathematical optimization? This would be a big help for the community it seems. I'm most interested in those relating to integer ...
4
votes
1answer
53 views

Find the number of idle intervals with weights

We have one job $i$ and one machine. Let $\mathbf{x}_i=[x_{i,1},x_{i,2},\ldots,x_{i,T}]$ be a binary vector where $x_{i,t}=1\iff$ job $i$ is scheduled at time $t$. Let $u$ be a positive number. I ...
5
votes
0answers
77 views

How to communicate number of integer combinations to a user

I'm working on a nifty little feature for our next release, i.e., to print the number of possible integer combinations left during branch and bound. This is really handy for the user because they ...
7
votes
1answer
762 views

How to find the idle intervals in integer programming?

I have a scheduling problem with one machine and one job. I defined a binary variable $z_t$ that is 1 iff the job is scheduled at time $t$ (the job can be served in multiple times that are not ...
10
votes
2answers
129 views

Use integer/quadratic programming to maximize consecutive zeros in a binary array

A binary array $t = [t_1, t_2, t_3, t_4, t_5]$ with each element a binary integer variable taking values 0 or 1. You can think this vector as slots with 1 representing the slot being taken and 0 ...
8
votes
2answers
1k views

How to formulate problems in the language of mathematical programming?

The question says it all. I am having difficulties formulating general problems (meaning no numbers just variables). When I read the solution, I understand but I can't figure how to formulate myself ...
4
votes
0answers
61 views

Continue on “Is there a known MILP to schedule routes after routes are made”

I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made). I have derived the sets of the problem, which are: 1) Itineraries of vehicle: $i \in ...
6
votes
1answer
104 views

Gurobi stuck at start - 16GB RAM exhausted

I'm solving a large instance using Gurobi 7.0, 64-bit version on machine with 16GB of RAM. Gurobi is stuck at the start and all the memory is exhausted. Here is the output: ...
7
votes
1answer
162 views

Custom Nurse Rostering Problem

I've asked this question also on Math Stack Exchange. It's a custom nurse rostering problem: $N$ is a set of nurses; $S$ is the set of shift-type (morning, afternoon, night, rest) $n_\mathrm{...
5
votes
2answers
536 views

Integer programming problem

I have the following exercise: Stockco is considering four investments. Investment 1 will yield a net present value (NPV) of \$16,000; investment 2, an NPV of \$22,000; investment 3, an NPV of \$12,...
5
votes
1answer
212 views

How is Big M calculated?

Because of excessive pollution on the Momiss River, the state of Momiss is going to build pollution control stations. Three sites (1, 2, and 3) are under consideration. Momiss is interested in ...
9
votes
1answer
102 views

Equivalence of formulations

I have a simple model such as: \begin{align}\max&\quad z=X_1+X_2+X_3+X_4\\\text{s.t.}&\quad y_1+y_2+y_3+y_4=2\\&\quad X_1 \leq y_1\\&\quad X_2 \leq y_1+y_2\\&\quad X_3 \leq y_2+...
13
votes
2answers
774 views

How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?

When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$. Is ...
12
votes
0answers
140 views

Integrality gap in bilevel binary linear programming problem

I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is $$ \begin{alignat}2 \min\limits_x&\...
7
votes
0answers
77 views

Automatic detection of SOS variables and constraints

We've been working on a new feature for Octeract Engine, namely to automatically extract SOS structure from a model and then exploit it. While the literature is quite rich on what to do with SOS once ...
7
votes
2answers
133 views

Linear constraint formulation (OR-statement)

I have the decision variable $X_{iz}$ And I have two parameters $T_i\in\{0,1\}$ and $IT_z\in\{0,1,2\}$. I can only assign $i$ to $z$ if the following holds: for $T_i=0$, $IT_z$ needs to be $0$ or $2$...
9
votes
0answers
69 views

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
5
votes
1answer
145 views

Integer programming example clarification

There is an explanation in my book for an integer programming example, which goes like this: A company is considering manufacturing three types of autos: compact, midsize, and large. The resources ...
10
votes
1answer
91 views

MIP: If integer variable $>0$ it should be equal to other integer variables $>0$

I have an MIP problem where $n$ different types of cars are delivering packages. Sometimes multiple types of cars are required to go to a single location. For example if car $1$ makes two deliveries ...
6
votes
2answers
116 views

A heuristic approach to solve a MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem? Since I have an additional but ...
10
votes
1answer
360 views

TSP problem: traveller does not visit all nodes - Google OR-tools

Context: I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must ...
7
votes
1answer
187 views

When using docplex.cp is it possible to get all feasible solutions?

I would like to solve an ILP and get all feasible solutions (even the worst one). How could I do that using docplex.cp? I've seen a similar question in: Using CPLEX "solution pool" to count ...