# Questions tagged [mixed-integer-programming]

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

137 questions
Filter by
Sorted by
Tagged with
19k views

### In an integer program, how I can force a binary variable to equal 1 if some condition holds?

Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like If $x \gtreqless b$, then $y = 1$. How can we write this ...
• 13.1k
3k views

### In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?

Suppose we have the constraint $$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$ where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
• 13.1k
4k views

### What are good reference books for introduction to operations research?

The reference books should cover the wide range of problem-solving techniques and methods.
6k views

### Why is it important to choose big-M carefully and what are the consequences of doing it badly?

The question here discusses the two different use of "big-M method", where one of them is the big-M in logical constraints and linearization in (mixed-)integer programming problems (that's what I'm ...
• 5,864
8k views

### When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model ...
• 193
2k views

### Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do ...
• 13.4k
3k views

### Optimization Problem Libraries

Can someone please make a list of optimization problem libraries so that the community can add to and refine it? I know a few off the top of my head.
• 13.4k
446 views

### How can I strengthen a family of constraints in the presence of a clique constraint?

Suppose $x_i$ are binary variables, $y_j$ are arbitrary variables, $a_j$ and $b$ are constants, and I have the following linear constraints: \begin{align} x_i + \sum_j a_j y_j &\le b &&\...
• 32.3k
2k views

### Mixed-integer optimization with bilinear constraint

So I have an optimization problem of the following form: \begin{aligned} \max_{x,y} \quad & \sum_i x_i \\ \text{s.t.} \quad & \sum_i x_iy_i \leq a \\ \quad & x_{\min} \leq x \leq x_{\max} ...
• 293
7k views

### How does a warm start work in LP/MIP?

Can someone explain how warm starts/ MIP starts work? How do solvers like CPLEX/GUROBI use warm start with the Simplex algorithm? I am interested in understanding how the entire warm start pipeline ...
2k views

### State-of-the-art algorithms for solving linear programs

Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
• 2,150
2k views

### How to model a mixed-integer linear programming formulation in Python using Gurobi?

I can remember that I spent some time in understanding how to formulate my first model. So I aimed at presenting a complete model here, wishing to save some time for students or researchers needing it....
• 2,104
9k views

### How to linearize min function as a constraint?

I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed ...
• 87
2k views

### Modeling floor function exactly

Suppose we want to enforce a constraint $$y=\lfloor{x}\rfloor$$ where $x$ is some continuous variable. One option is to use $$x-1\leq{y}\leq{x},\quad y\in\mathbb{Z},$$ which fails on the edge case ...
• 2,097
2k views

### Feeding known lower bounds to solvers

Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all feasible solutions, and your solver of choice: For what theoretical and/or practical ...
• 1,026
764 views

### Reference for column generation applications

When talking about column generation algorithms, the main example is the cutting stock problem. I'm aware that variations of vehicle routing problem (VRP) can be solved using a column generation ...
• 5,864
3k views

### Working with absolute values in constraint in a LP or MILP

Having all the approaches explained in the blog called "OR in an OB World" (this address) in my mind, I would like to ask the following question: What is the best practice to make a constraint linear ...
• 8,652
664 views

### How to construct my mixed integer programming problem with constraint of minimum consecutive ones

My target is to formulate a binary sequence with fixed size $N$ = 10, such as $[1, 0, 0, 0 ,1, 1, 0, 1, 0, 0]$. However, I want to constrain this sequence so that when 1 appears, it has to appear at ...
• 121
329 views

### Modelling precedence relations

I have two tasks $i$ and $k$ with durations $d_i$ and $d_k$, where $d_i$ and $d_k$ are nonnegative variables. I would like to model that $i$ may precede $k$ or $k$ may precede $i$ and that they may ...
• 2,252
432 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 ...
2k views

### How to compare two different formulations of a problem?

I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
• 2,150
1k views

### What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

Exact methods, e.g., models that utilize an MIP approach with a specified objective and constraints, have advantages like the following: Using off the shelf solvers Optimality gap provability ...
• 1,069
4k views

### How to evaluate the performance of open source solver?

I am looking for a reliable open source solver to solve LP and MILP (with a few thousand variables). How can I evaluate the performance of a given solver for a particular use case?
1k views

### Application of complex numbers in Linear Programming?

The theory surrounding Linear Programming is based on variables, bounds and coefficients that take on values in $\mathbb R$, the set of real numbers. I have long wondered whether there might be ...
• 550
1k views

### Using CPLEX "solution pool" to count feasible points

Some problems call for a count of the number of integer "lattice" points contained in a feasible region (rather than for locating the minimum or maximum objective function value in that region). See ...
• 247
769 views

### Estimation of the size of Branch-and-Bound trees using ML

A short background: A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution ...
• 8,652
726 views

### The effect of choosing big M properly

I have a set of linearized constraints that are modelled using big-Ms. Now, it is, of course, common knowledge to make the value of M and small as possible in order to provide tighter LP relaxations ...
• 1,859
1k views

### How could we simplify solving the large scale MIPs without using any advanced methods like decompositions?

Many practical optimization models (specially MIPs) are NP-Hard and solving them need much time even with the modern solvers like CPLEX or GUROBI. One of the best way (but not easy) is using ...
• 8,950
4k views

### What do solvers like Gurobi and CPLEX do when they run into hard instances of MIP?

MIP is NP-Hard, so it is possible that an instance is very difficult and has multiple local minima that the search can get stuck in. With a Metaheuristic Algorithm, the stochastic and approximate ...
• 2,139
1k views

### How to use warm start to solve MIPs efficiently?

I'm working on the scheduling model which takes a long time to solve to optimality (even for a small instance), therefore I would like to use a warm start (MIP start) to solve the problem. I'm using ...
• 8,950
1k views

### Is there a heuristic approach to the MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. \begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
• 2,297
2k views

### How to remove or replace sub tour elimination constraints in the VRP variant models?

In many of vehicle routing problems variant (VRP), which can be formulated using MIPs, to avoid creating sub tour, we need to use sub tour elimination constraints (SEC). One of the known SEC is (I ...
• 8,950
3k views

### Algorithms vs LP or MIP

Is there a way of writing an algorithm with if-, while-statements to find an optimal solution without using linear-programming (LP)/MIP? If so, what would the benefits be against the LP/MIP? Is it ...
• 1,193
222 views

• 13.1k