Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
157
questions
2
votes
1answer
39 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
170 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 ...
1
vote
0answers
34 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
674 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
96 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
38 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
39 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
89 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
162 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
146 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
157 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
171 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
80 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
62 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
78 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
193 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
168 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
266 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
159 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
177 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
190 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
298 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
150 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
81 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
189 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
150 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
77 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
511 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
840 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
100 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
133 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
297 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
94 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
86 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
184 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
295 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
85 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
776 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
184 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 ...
