Questions tagged [mixed-integer-programming]
For questions about mathematical optimization problems involving both continuous and binary or general integer variables.
137
questions
32
votes
3
answers
18k
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 ...
12
votes
2
answers
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$ (...
10
votes
1
answer
3k
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.
24
votes
2
answers
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 ...
19
votes
6
answers
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 ...
14
votes
4
answers
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 ...
50
votes
8
answers
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.
7
votes
2
answers
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} ...
7
votes
1
answer
438
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 &&\...
22
votes
2
answers
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 ...
15
votes
2
answers
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)....
14
votes
4
answers
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....
7
votes
1
answer
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 ...
32
votes
8
answers
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 ...
31
votes
3
answers
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 ...
23
votes
9
answers
751
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 ...
18
votes
1
answer
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 ...
7
votes
3
answers
325
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 ...
7
votes
1
answer
640
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 ...
25
votes
6
answers
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 ...
24
votes
4
answers
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
...
19
votes
4
answers
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?
18
votes
3
answers
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 ...
14
votes
3
answers
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 ...
14
votes
1
answer
752
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 ...
13
votes
4
answers
687
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 ...
13
votes
3
answers
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 ...
12
votes
4
answers
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 ...
10
votes
1
answer
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 ...
10
votes
2
answers
990
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 ...
10
votes
3
answers
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,...
8
votes
5
answers
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 ...
6
votes
1
answer
222
views
TSP subtour elimination by assigning distance traveled
Given a set $S$ which we need to travel following TSP rules.
I was wondering if this sub tour elimination method is good enough or not?
Let $b_{i,j}$ denote edge from $i$ to $j$ is taken or not and $...
5
votes
1
answer
239
views
Does exchanging integer variables by binary variables strengthen a MIP?
Suppose that I have an MIP with a whole lot of continuous variables and some integer variables. In my case, this takes a very long to solve (in fact I wasn't able at all to solve it to optimality). So ...
5
votes
2
answers
772
views
How to linearize specific range constraints?
I would like to know about the linearization of the $(If, Then)$ constraints as follows:
$$\begin{array}{l}
\text { If: } \\
15 \leqslant x \leqslant 25 \\
\text { then: } \quad y=\color{blue}{a} x+\...
4
votes
0
answers
115
views
Conditional constraint formulation [duplicate]
How can I create constraints to make sure $x=1$ if $k\geq 0$ and $x=0$ if $k<0$, where $x\in \{0,1\}$ and $k\in \mathbb{R}$?
Here is my attempt:
\begin{equation}\label{cons:1}
\begin{aligned}
...
2
votes
1
answer
192
views
Google OR Tools: Iterative Assignment Problem
This question is a Google OR-Tools specific implementation of recommendation from a previous question.
In short, the movie theater problem encompasses assigning viewers to seats such that the distance ...
2
votes
1
answer
131
views
Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP
I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
2
votes
2
answers
167
views
Mixed Integer Programming: Iterative assignment problem
I have a real world problem, which is analogous to the below toy problem, which I call 'The Movie Theater Problem' (TMTP.)
In TMTP, movie viewers are assigned seats which principally balances two ...
1
vote
2
answers
422
views
How to create A, b and c matrices from very large .lp file?
I am working on Scaling MIP. I use Gurobi within Clion. I need to extract the coefficient of Xs (A matrix), right-hand side (B matrix), and an objective function(c matrix) from the .lp file and ...
-2
votes
1
answer
75
views
Mixed Integer programming - Problem modelling coincidence restriction in scheduling match problem
I am trying to model and solve a problem for maximize audience of matches that must be scheduled in different slots (I am using python PulP library). Below I explain the problem and the model process ...
31
votes
4
answers
3k
views
"Best practices" for formulating MIPs
Often there are many alternatives ways for formulating a MIP. For example:
The model contains inequality constraints that must hold with equality in an optimal solution.
The model contains ...
26
votes
4
answers
1k
views
Stochastic programming MIP solvers
I am aware that Benders Decomposition is readily available in CPLEX and in SCIP; but are there any (free) solvers that provide off the shelf stochastic programming MIP algorithms or a nice to work ...
26
votes
1
answer
601
views
The rationale to improve MTZ?
Currently I need to solve a quite specific problem involving symmetric TSP as a sub-problem (i.e., a Hamiltonian cycle is a necessary condition for optimizing some problem-specific variables that ...
21
votes
5
answers
669
views
Tightness of an LP relaxation without using objective function
How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...
18
votes
4
answers
1k
views
Relationship between Benders decomposition and Dantzig-Wolfe decomposition
It’s often said that “Benders decomposition is Dantzig-Wolfe applied to the dual”. How can this statement be made precise? I know that in Dantzig-Wolfe, cuts are added in one-to-one correspondence ...
17
votes
1
answer
4k
views
What is the "big-M" method? And are there two of them?
I’ve seen the "big-$M$ method" referred to in different ways. What is the "big-$M$ method" and why does it seem to mean two different things?
16
votes
2
answers
2k
views
Why do we need to measure the difficulty of mixed-integer programming problems?
I'm doing a project about the estimation of the difficulty of mixed-integer programming problems. The MIP instances are from MIPLIB 2017. And there are three categories of MIPs provided by MIPLIB 2017,...
16
votes
2
answers
671
views
Branching rules in commercial MIP solvers
I am working on a branch-and-cut algorithm, and I have spent quite some effort into improving the branching decisions that are made by commercial solvers, such as CPLEX and Gurobi. However, it was ...
15
votes
1
answer
268
views
Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?
It turns out that extending MILP with any of the constraints $y=\lfloor x\rfloor$, $y=\lceil x\rceil$, $0 < x$, or $x\notin \mathbb{Z}$ is 'equally hard'.
(see my answer here, and below)
...