Questions tagged [mixed-integer-programming]
For questions about mathematical optimization problems involving both continuous and binary or general integer variables.
913
questions
0
votes
0
answers
42
views
Using docplex with mpmath
In Python 3.10, is it possible to use docplex along with mpmath (https://mpmath.org/), e.g., to compute expressions in constraints and objectives with arbitrary precision?
- 101
0
votes
2
answers
78
views
How to design a constraint to control flow in a non-network optimization model
I'm working on a production scheduling problem with a MIP model somebody left to me.
This is a discrete-time model in which the constraints used to control the production and consumption of product p ...
- 27
1
vote
1
answer
92
views
What is NoRel heuristic in GUROBI?
There is NoRel (or No Relaxation) heuristic in the Gurobi solver which helps to find very good feasible solutions for Mixed Integer Programs. I couldn't find explanation of its idea. Perhaps anybody ...
- 53
3
votes
2
answers
130
views
Will adding this constraint help my model?
I am solving a maximization problem with continuous variables $x,z\in \mathbb{R}^+$ and binary variable $\delta \in \{0,1\}$.
I am maximizing $x$ subject to side constraints and would like to enforce ...
- 33
1
vote
2
answers
115
views
Workforce scheduling problem
I am working on a employee scheduling problems (assigning shifts to temporary workers) by modeling it as a MIP. There is a one shift per day constraint for the employees. There are overnight shifts ...
- 11
4
votes
1
answer
107
views
+50
What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?
Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints.
Sadly, at the moment it is not performing fast ...
- 139
2
votes
1
answer
194
views
Linearize piecewise function without big-M constraints
I have been attempting to solve a maximization problem where there is a piecewise function in the objective. Something like:
$\sum_{n}(1-prob_{n})(1+x_n)$
Where $prob_{n} = $
\begin{cases}
0.25,...
- 67
0
votes
1
answer
72
views
Problems understanding model notation in LPs
today I came across a paper that uses a type of model notation I have never come across before. These are the objective function and constraints I don't quite understand. I am specifically interested ...
- 31
2
votes
1
answer
68
views
Compute time between tasks
I am trying to solve an optimization problem in which there is a set of tasks, $S$, where $s_i$ and $e_i$ are the starting and ending time of task $i \in S$. Each task $i $ must be done within its own ...
0
votes
0
answers
61
views
Travelling Salesman problem and Vehicle routing problems
Can someone explain to me why are we doing the $x_{ij}=1$ and and the constraint $U_j \geq u_i+1-n(1-x_{ij})$
Also do you have any books or sources in mind from where I could learn in more detail from ...
- 39
0
votes
0
answers
41
views
Formulation for data insight
There is an interesting data insight question that I want to solve using mathematical programming. I aim to find the combination of features that has the highest impact on the target indicators.
We ...
- 95
1
vote
1
answer
38
views
Formulation to avoid partial coverage for demand points
I would like to assign items to a box over a time horizon where each box has an associated deadline. I was wondering if my formulation and / or variable definition can be improved. In other words, ...
- 334
1
vote
0
answers
34
views
Is there a way to calcuate the maximum number of cuts in a Benders decomposition?
Since the benders algorithm is finite, there a maximum number of cuts that could theoretically be added. The worst case is that I add cuts for all extreme points and all extreme rays that are part of ...
- 139
4
votes
2
answers
188
views
Column generation: set partitioning vs set covering
I am working with a column generation algorithm and have noticed that convergence is much faster when my master is a set covering problem ($Ax\ge 1$) compared to when it is a set partitioning problem (...
- 41
1
vote
0
answers
78
views
Weird behavior when using Automatic Benders Decomposition in CPLEX
I've encountered some weird behavior when using the Automatic Benders Decomposition in CPLEX.
I initially solved the MIP without BD and then I compared the results against the Full, Workers and User ...
- 111
1
vote
2
answers
106
views
Understanding the L-shaped-method and the different variants of it
I am currently trying to understand the integer L-shaped-method/stochastic version of Benders Decomposition because I have practical problem MIP that is stochastic and thus has very good decomposition ...
- 139
2
votes
2
answers
169
views
Express cardinality of index set satisfying conditions
I have two sets of binary variables $x_{i,j}$ and $y_{i,k}$, where $i, j, k$ ranges over some index set $I,J,K$, which satisfies the constraint $\sum_j x_{i,j} = 1$, $\sum_{k} y_{i, k} = 1$. How do I ...
- 223
2
votes
1
answer
121
views
Non-proprietary (Python friendly) alternatives to Cplex and Gurobi
I have implemented a pure binary integer combinatorial optimization routine within a Python module (importing gurobipy), and experimented with relaxing a few ...
- 123
2
votes
1
answer
91
views
Bin packing problem with multiple dates
Data:
I have the following items I need to ship, with the input data as below. Each item needs to be shipped by shipDate at the latest, but can be shipped as early as availDate. Each truck has a min/...
- 53
1
vote
0
answers
136
views
Non-Linear objective function due to piecewise component (part 2)
This is a follow up to this question: Non-Linear objective function due to piecewise component
Consider a piecewise function but now with three segments but the objective remains the same as:
$\sum_{n}...
- 67
0
votes
0
answers
77
views
Generalised formuals from scratch for Linear and Integer programming
I am making quite some silly mistakes while writing the generalized version of MLIP or IP problem. Any sources that you would recommend that teach how to write generalized formulas from scratch? and ...
- 39
2
votes
0
answers
28
views
The facet-defining inequalities for a single resource scheduling problem
Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions:
$$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
- 8,382
2
votes
1
answer
84
views
logic constraints for IP model
I have been struggling with the formulation of logic constraints. Is there any source you would recommend to understand the topic better or trick of formulation of the constraints?
Thanks
- 39
1
vote
1
answer
75
views
Mixed Integer programming, the big M
In the constraints below, why have they used the big M? What do we look for in order to identify the big M in other questions?
- 39
1
vote
1
answer
67
views
How do I check convergence in stochastic Benders?
So in the deterministic version of Benders, the main process works like this:
I initialize my x-vector (Integer variables from the master problem) and solve the dual subproblem (SP).
I add an ...
- 139
1
vote
1
answer
83
views
How to understand the basis of LP problems given by HiGHS solver?
Here is part of a ".bas" file given by HiGHS using serial dual simplex method to solve an LP problem:
HiGHS v1
Valid
# Columns 57471
3 1 1 3 3 1 1 3 3 1 1 3 1 3 3 1 ...
What does the number &...
- 67
1
vote
0
answers
60
views
Need help with a model to optimize a trail in directed graph
The graph in the image represents the production sequencing on a machine with production capacity C in volume. Each node N represents a different product with a profit L per volume produced. Every ...
- 11
1
vote
1
answer
78
views
Recommendations to understand stochastic version of Benders?
I successfully understood and implemented a Benders algorithm for the deterministic version of the problem I am studying.
However, I have some issues now diving into the stochastic model. I have the ...
- 139
0
votes
1
answer
142
views
Production scheduling
I'm formulating a scheduling problem with the following decision variables:
$$X_t \space \text{is power sold to market in time period t} \\
Y_t \space \text{is power used for production in time period ...
1
vote
1
answer
103
views
Mixed-Integer Programming Model for Scheduling with Dynamic Jobs
I have an optimization problem for deliveries between production lines and a warehouse in a small facility. I need to know how many vehicles and utilities to buy, such that cost and downtime are ...
- 11
3
votes
0
answers
111
views
From Quadratic to MILP?
I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:
(QP) $\min c^T x + x^T Q ...
- 1,198
0
votes
0
answers
46
views
Distributed coloring of nodes of sensor ntwork
I have the same graph coloring problem as in
Coloring of nodes of a sensor network
@RobPratt and @prubin have proposed some very good solutions.
This time I am or interested in distributed coloring ...
- 2,211
2
votes
1
answer
74
views
How to define the sequence depending setup time based on a time index formulation
I am working on a scheduling problem in which I have used two different MIP formulations and also based on the time index variable. My problem is in the class $ P_{j} | \ r_{j}, SDST \ | C_{Max} $.
...
- 8,382
1
vote
2
answers
154
views
Matrix lookup modelling variants
As part of a bigger model I have a matrix of variables $x_{ij} \geq 0$ and a "selector" set of variables $y_j \in \{0,1\}, \sum_j y_j = 1$.
From $x_{ij}$ I'd like to get the variables of ...
- 113
0
votes
2
answers
215
views
How to identify constraints that make problem not solvable in polynomial time?
I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below.
The details of the variable definitions, etc., can be found in the paper, but it's ...
-1
votes
3
answers
89
views
mip - mapping of equality to boolean variable
I want to create mip model which assign workers to entities. In case neighbour entities use same worker, objective should be increased by 1. A goal is to maximize total number of same workers for ...
- 189
1
vote
2
answers
221
views
How to properly tackle a big model using weak constraints
I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is.
One suggestion I got is to use lazy ...
- 11
0
votes
0
answers
81
views
In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?
In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an elementary path, meaning that no vertices are repeated.
However, when an elementary path is ...
0
votes
0
answers
96
views
How should one proceed with column generation when the subproblem generates only columns with positive reduced costs?
I try to solve a MILP with Column generation. The Master Problem is a minimization problem with " $\le$ " constraint which lead to non-positive dual values. The problem is that the ...
- 409
3
votes
1
answer
208
views
Formulation of binary constraint with the least binary variables for linear programming
I am currently working on a formulation for a linear program of a complex problem. At the moment I am facing to formulate the following logical condition:
There are two binary variables. Let's name ...
2
votes
1
answer
103
views
How to change the variable bound from an interval to its lower and upper bound in JuMP?
When I read a model from a ".mps" file using "read_from_file" in JuMP and print it, I find that many bounds are written in the interval format like "x \in [0, 1]". I want ...
- 67
0
votes
1
answer
73
views
Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?
I am in the process of trying to solve a VRP with synchronization constraints with Benders Decomposition. I am programming in C++ and my approach seems to be really slow for the following reason:
My ...
- 139
1
vote
1
answer
39
views
if else condition with multiple criteria in MIP
I have problem like below
Decision variable x1 >= 0
But it depends on selection variable s1 as binary variable
If s1 = 0 then x1= 0 and
if s1 = 1 then x1>0
how I can write this as constraint for ...
- 13
1
vote
1
answer
74
views
How to calculate the duration of a task in each shift?
I am solving a job scheduling problem with three shifts,
the duration of all shifts are assumed to be known (and might be equal):
The tasks can start from any shift
We know the duration of each task ...
- 1,275
2
votes
1
answer
108
views
How to select intermediate nodes in a network?
I have a network where nodes are connected as shown in the Figure .
Nodes 2 and 4 have a connection to the cloud node. I am writing constraints where at least one node with a connection to the cloud ...
- 81
2
votes
1
answer
97
views
Formulation for choosing how many items to manufacture
I am working on a scheduler for a manufacturing plant. I have currently set it up so the decision variables are set up as binary variables:
$x_{m,p,s}$ = 1 if machine m is running part p on shift s
...
- 55
0
votes
1
answer
54
views
For an ILP relaxed to LP is the LP solution objective always less than the ILP solution?
If an Integer Linear Programming (ILP) problem is relaxed to a Linear Programming (LP) problem, is the objective value of the LP always less than the same ILP problem? Why?
- 897
1
vote
1
answer
40
views
Activating a sequence of the binary variables in a multi-dimensional array
Suppose we have an array of binary variables $\{x_{i,t,n}, \ \forall i \in I, t \in T, n \in N \}$. If we want to define a condition as, if any of $x_{i,t,n} = 1$ in an arbitrary index $i$, then the ...
- 8,382
0
votes
0
answers
38
views
MILP: Linearization / approximation of mean and variance
My question- What is the standard practice to linearize / approximate computations of mean and variance using MILP solvers?
Edit: referencing comments, an idea was proposed to set an upper limit and ...
- 501
0
votes
1
answer
104
views
How to minimize number of machines required to serve tasks, and return the schedules for each machine?
The problem I'm trying to solve is the following:
Given $t\in \{1,2,3....T\}$ tasks, integer.
Tasks have release times $r_t$ and deadlines $d_t$, and processing times $p_t$, all continuous, real-...
