# Questions tagged [mixed-integer-programming]

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

913 questions
Filter by
Sorted by
Tagged with
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?
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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,...
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 ...
68 views

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 ...
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 ...
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 ...
1 vote
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, ...
1 vote
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 ...
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 (...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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/...
1 vote
136 views

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 ...
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}$. ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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?
1 vote
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 ...
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-...