Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
30 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
61 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
133 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
132 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
93 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 ...
6
votes
1answer
137 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 ...
3
votes
2answers
114 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
73 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
59 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
67 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
29 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
33 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
106 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
132 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
238 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
127 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
130 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
203 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
131 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
75 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
169 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
133 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
72 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
246 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
77 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
339 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
85 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
907 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
77 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
145 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
56 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
90 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
218 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
44 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
763 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
136 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
108 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
163 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
553 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
224 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
104 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
791 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 ...