Questions tagged [mixed-integer-programming]

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

1,026 questions
Filter by
Sorted by
Tagged with
137 views

Is there any way to use Lazy constraints in Pyomo?

I would like to know if there is any way to implement a Lazy constraint in the Pyomo package. (As far as I know, the only way to implement such a constraint is by ...
• 9,046
75 views

Minimize Expenses For Workers

My goal is to minimize the labor expenses. Say we have 3 types of workers: $x_1$ = Permanent Driver, rate = 693.875/day $x_2$ = Reliever Drivers rate = 435/day $x_3$ = Crews rate = 400/day There are 6 ...
1 vote
88 views

How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
66 views

How to deal with performance bottlenecks in Stochastic Vehicle Routing Problem with Benders' decomposition?

I've been working on solving a stochastic vehicle routing problem using Benders' decomposition with CPLEX in C++. Initially, my implementation struggled with larger instances, but I've made ...
• 327
73 views

Improving the lower bound

Good afternoon. I have a very difficult to a MIP model. I have tried several different strategies to reduce the gap. I am using Gurobi and in this case, I already have an incumbent solution. I've set &...
51 views

multiple shifts per day constraint for a workforce scheduling problem

This is an extention to the workforce scheduling problem discussed in this thread Workforce scheduling problem. Adding a new post to discuss an important new requirement in this model. So the new ...
• 33
59 views

How to linearize this L0 norm of a vector?

I have an QP optimization problem. $\bf x$ is the binary optimizaion variable of size $12\times 1$. One of the constraints is non-linear/non-convex. The constraint is L0 constraint. The constraint I ...
• 2,377
1 vote
68 views

Connections between Bounds in MIPs

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and ...
• 19
120 views

Modelling L-0 norm of a vector

I have a binary variable $\bf x$ of length 4000. Let ${\bf x}=[x_1,x_2,\cdots, x_{4000}]$. Let's say we have ${\bf y}=[y_1,y_2,y_3,y_4]$, where \begin{align} y_1&=x_1+x_5+x_{9}+\cdots+x_{3997} \\ ...
• 2,377
40 views

• 2,377
121 views

Optimizing a Route Selection Problem with Multiple Constraints and Objectives

I'm developing a solution to optimize a vehicle routing problem where each stop has an associated score (priority), specific geo coordinates, and a required stop duration. The goal is to maximize the ...
• 131
55 views

Temporal changing model parameters/constraints/variables in MILPs

In general, I can compute an MILP using a solver of my choice (Gurobi, ...) and stop it at any time, change parameters/constraints add variables. Take the so far best solution computed based on the ...
• 319
1 vote
24 views

(Dis-)Advantages of Design Space Exploration Frameworks generating MILPs (e.g. DeSyDe, ArchEx, ...)

Are there still reasons to create MILPs manually from the ground up, or is it more suitable to rely on certain frameworks translating requirements and elements into proper MILPs using a set of rules, ...
• 319
126 views

Converting a piecewise function to linear equations

I am trying to build a MILP model. In this model, I have a dependent variable (alpha) that its value depends on the value of some other variables (or different combination of some other variables). In ...
• 97
1 vote
101 views

Converting a Linear Program with TU Constraint Matrix to a Nonlinear Convex Model: Solver Performance?

I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total ...
244 views

Can we add a certain binary row to a matrix which preserves total unimodularity?

Suppose I have a matrix $A\in \{-1, 0, 1\}^{m\times n}$ which is Totally Unimodular (TU), and a vector $b^T \in \{-1, 0, 1\}^{1\times n}$ which has exactly one entry which is $1$ and exactly one entry ...
1 vote
41 views

What reasons would cause lazy constraints to degrade the performances when reoptimizing with a different objective?

We are currently solving a hard MILP problem on optimality. Once it has been solved, several times (from 5 to 10 times), we change one coefficient of the objective function and reoptimize. Thus the ...
• 741
153 views

Why would a solver stay on node 0 and still improve the gap?

I understand how exploring the Branch-and-cut tree would help improve the best bound known and the incumbent of a MILP, however, on some instances that I deal with, my solver (Gurobi) seems to keep ...
• 741
133 views

What does a solver do with a MIP warmstart solution?

From what I understand, most solvers use a user provided solution by first detecting if it feasible. If it is feasible, its objective value is used as a first bound for the branch and cut tree, this ...
• 741
127 views

Exploiting identical subproblems in column generation

As suggested, this is a new post. I have the following column generation model. The notation is as follows: $i\in I$ refers to the nurses, $t\in T$ to the days and $s\in S$ for the shifts. With the ...
1 vote
112 views

• 525
125 views

Equivalent constraints in MILP give different answers

I'm getting unexpected results from the HiGHS solver in scipy (scipy.optimize.linprog with integrality constraints). In my mixed integer program one of my constraints is that $x_0 \geq 100$. I get a ...
• 33
186 views

PuLP is ignoring constraints, and setting everything to 0 for minimization problem

I have a multi-objective optimization problem I am trying to solve with competing objectives. I am trying to model a network of industrial businesses which can share wastewater rather than sending it ...
• 13
464 views

How to modify master problem and individual sub problems in column generation?

This is a follow-up post regarding this one. I deleted this new post once before, as I was unhappy with the formulation. I have the following basic nurse scheduling MILP, which tries to cover the ...
1 vote
116 views

How to model the following Constraint

I would like to model the following: $B \le \alpha \implies \sum_i W(i) \ge \beta$, where $B$ a continuous variable, $W(i)$ binary variables, $\alpha$ a real constant number, $\beta$ an integer ...
• 2,252
67 views

Formulation of a stepwise linear approximation

I am currently trying to solve an MILP in Gurobi. Unfortunately, Gurobi does not support non-linear functions and I would like to do the following. I currently have the following constraint. It ...
232 views

Convex equivalent of a constraint

I have a constraint as follows in my MILP model: $$\sum_{e} (a_1(e) - a_2(e))^2 \leq M$$ Where, $a_1(e)$ and $a_2(e)$ are binary variables. Would you please guide me how can I find the equivalent ...
65 views

How to Group IDs Based on the Difference of Each ID’s Min and Max Value?

I have a dataset that contains IDs along with their corresponding minimum and maximum values. Here’s a sample of the data: ...
• 529
30 views

Grouping of a list of elements in fixed order to maximize the total return of all the groups

I'd like to ask about if there's an existing type of problems that fits to my question. (Searching it for a while but cannot get to the point) Basic Problem Description: Given a sequenced list (order ...
• 103
58 views

Better formulation of bilinear terms

I am working on an optimization problem where I need to formulate a constraint that represents the total sales value under specific conditions. The challenge lies in creating an expression that ...
• 23
1 vote
141 views

How do I linearize such a constraint?

I was wondering, how one would linearize such a constraint, to make it applicable to LPs. $a_{i}=(a_{i-1}+b_{i})(1-c_{i})-d_{i}$ $a_i$ gives information of the number of assigned jobs to machine $i$. ...
166 views

Grouping values based on a difference constraint

I am trying to write an MILP to do a grouping (clustering) given one difference condition. Suppose, I have the following elements in a list: 1,2,3,4,6,8,9,10. My goal here is to group them so that the ...
• 529
57 views

Warehouse placement problem in

I’m curious about the warehouse placement problem. Suppose N nodes exist, each with average demand across all products (or a single product for simplicity.) the problem is to position M warehouses ...
• 551
1 vote
97 views

Logical conditions

This is similar to question I asked here: Priotization rules for variable allocation in linear programming. In an optimization problem, the goal is to manage the purchase and sale of items under ...
• 23
75 views

Cost function value of relaxed ILP after rounding is less than or equal to the optimal one

I have a minimization problem for which I am having some misunderstandings and confusions with regard to some results I am getting for an ILP and its LP relaxation. In the ILP I have two decision ...
• 1
1 vote