Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
140
questions
3
votes
0answers
32 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
54 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
2answers
148 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
159 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
263 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
150 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
173 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
185 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
251 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
145 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
79 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
186 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
145 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
76 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
430 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
82 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
740 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
96 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
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 ...
5
votes
1answer
112 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
254 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
81 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
85 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
173 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
286 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
71 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
55 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
78 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
773 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
174 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
63 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
129 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
171 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
754 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
299 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
109 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
813 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
162 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&\...
8
votes
0answers
87 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
147 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
73 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
212 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
104 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
183 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
415 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 ...
8
votes
1answer
290 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 ...
