Skip to main content

Questions tagged [mixed-integer-programming]

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

Filter by
Sorted by
Tagged with
51 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.
Mark L. Stone's user avatar
33 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 ...
David M.'s user avatar
  • 2,107
32 votes
3 answers
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 ...
LarrySnyder610's user avatar
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 ...
Rolf van Lieshout's user avatar
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 ...
fbahr's user avatar
  • 1,026
28 votes
5 answers
5k views

Why is open source operations research software so far behind open source statistics and machine learning software?

Like many who participate in this site, I work on projects in both operations research (OR) and statistics/machine learning (ML). The different states of open source software in these fields are often ...
Robert Bassett's user avatar
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 ...
Albert Schrotenboer's user avatar
26 votes
1 answer
615 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 ...
Omicron_Persei_11's user avatar
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 ...
rasul's user avatar
  • 2,150
25 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 ...
EhsanK's user avatar
  • 5,874
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 ...
fhk's user avatar
  • 1,069
24 votes
2 answers
1k views

How much can we expect to increase the speed of mixed integer programming in the next 10 years?

Mixed-integer programming is a super powerful tool for operations researchers to solve many difficult problems. As described by Bixby[1] there has been an overall improvement in the performance of a ...
Michael Lindahl's user avatar
23 votes
9 answers
778 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 ...
EhsanK's user avatar
  • 5,874
22 votes
5 answers
2k views

How can I best handle symmetries in my MIP?

When dealing with mixed-integer-programs with many symmetric solutions it can take very long until the branch-and-bound-tree search is finished because symmetric optimal solutions cannot be pruned. ...
YukiJ's user avatar
  • 2,023
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 ...
Palaniappan Chellappan's user avatar
21 votes
3 answers
4k views

Using Neural Networks For Solving Optimization Problems

Recently, I came across the below paper and found it very interesting. Solving Mixed Integer Programs Using Neural Networks; https://arxiv.org/abs/2012.13349 The idea is to use (train with neural ...
alamaranka's user avatar
21 votes
3 answers
2k views

Are valid inequalities worth the effort given modern solvers?

In Laurence Wolsey's Integer Programming[1], he presents a well-known procedure for deriving valid inequalities (VI) suitable for integer and mixed integer linear problems (see Section 8.3, and also ...
SecretAgentMan's user avatar
21 votes
5 answers
686 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 ...
Mertcan Yetkin's user avatar
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 ...
AndyT's user avatar
  • 193
19 votes
4 answers
5k 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?
Rajasekhar Kadambur's user avatar
19 votes
2 answers
862 views

How do we decide/plan an SLA for an NP-hard optimization process running in production?

How do you decide or plan an SLA (Service Level Agreement) for an application that depends on an optimization process when the problems you deal with are NP-hard? That is, if you are developing an ...
Skander H.'s user avatar
  • 2,139
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 ...
Mark H's user avatar
  • 550
18 votes
4 answers
2k 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 ...
David M.'s user avatar
  • 2,107
18 votes
1 answer
3k views

Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
rasul's user avatar
  • 2,150
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 ...
Oguz Toragay's user avatar
  • 8,667
17 votes
5 answers
763 views

Presolve is cutting down a lot of binary variables. Should I rethink my formulation?

I built my model on Python and am passing it to Gurobi to solve the problem. The presolve phase of Gurobi cuts down ~80% of the integer/binary variables and I am wondering if I should rethink my ...
Abhishiekh Ramesh's user avatar
17 votes
1 answer
5k 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?
LarrySnyder610's user avatar
17 votes
2 answers
3k views

Dual bounds of integer programming problems

I often read in papers when branch-and-X algorithms are used to solve mixed integer programming problems, that the lower bound (in the minimization case) obtained from solving a linear programming ...
Djames's user avatar
  • 1,143
17 votes
1 answer
5k views

The difference between max-min and min-max

I am solving two-stage optimization problems in the form of $$\max_{x \in X}\min_{y \in Y} f(x,y),$$ where $f(x,y)$ is the solution of a mixed integer linear program (MIP). As the constraints of the ...
Albert Schrotenboer's user avatar
16 votes
3 answers
1k views

What is a "hard problem" in the context of Mixed-integer programming?

As a practical (real-world problems) point of view, it's important we could solve optimization problems as quickly as possible (for instance, to release a daily schedule). Maybe a problem with many ...
A.Omidi's user avatar
  • 8,960
16 votes
4 answers
2k views

Best model for precedence constraints within scheduling problem

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to ...
JakobS's user avatar
  • 2,767
16 votes
2 answers
701 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 ...
Albert Schrotenboer's user avatar
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,...
Karen Jin's user avatar
  • 161
16 votes
1 answer
2k views

Warm start CPLEX using google or-tools

I have been trying to use the SetHint python API in google or-tools to warm start MIPs and solve it using CPLEX. It looks like my hints are accepted by the SetHint function but I am not sure whether ...
Palaniappan Chellappan's user avatar
15 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 ...
Mark L. Stone's user avatar
15 votes
2 answers
4k views

Is Apple's M1 suitable for Operations Research?

I am curious about the performance of Apple's M1 chip solving optimizations models, MIP, LP, and in solutions approach as benders or columns generations. I read that is a spectacular cpu to perform ...
orpanter's user avatar
  • 517
15 votes
3 answers
1k views

How does the search space affect the speed of an ILP solver?

Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model ...
ephemeral's user avatar
  • 917
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)....
rasul's user avatar
  • 2,150
15 votes
1 answer
189 views

Symmetric undirected $p$-median instance with fractional LP solution?

The $p$-median problem is NP-hard, so its LP relaxation does not naturally have all-integer solutions. However, it very often does; in fact, it can be hard to find an instance for which the LP ...
LarrySnyder610's user avatar
15 votes
1 answer
272 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) ...
Discrete lizard's user avatar
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 ...
hardmath's user avatar
  • 247
14 votes
3 answers
5k views

When should I use dual Simplex over primal Simplex?

In Gurobi the user can change the method parameter in order to force Gurobi to use a particular method for solving MIPs. The user can, amongst others, choose ...
YukiJ's user avatar
  • 2,023
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....
Mostafa's user avatar
  • 2,104
14 votes
2 answers
793 views

Obtaining optimality gaps when using hybrid exact-heuristic approaches to vehicle routing problems

I'm starting to read about column generation-based approaches to vehicle routing problems (VRP). Let's say that I want to solve very large instances of an intricate VRP, I'm not looking to always ...
vulpith's user avatar
  • 383
14 votes
3 answers
1k views

How to handle an IP sub-problem with an objective function in Benders Decomposition

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) ...
whitepanda's user avatar
14 votes
1 answer
776 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 ...
Oguz Toragay's user avatar
  • 8,667
14 votes
1 answer
262 views

In the context of LASSO regression, how to introduce a constraint for max number of selected betas?

In lasso, we have a regularization term in the loss function: $$\sum \|y-\hat{y}\|_{2} + \lambda \sum\|\beta\|_{1}$$ As the loss function is minimized, some $\beta$'s will become zero. That's what ...
eight3's user avatar
  • 481
14 votes
1 answer
711 views

Tools to implement branch-and-price algorithms

As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms. I ...
vulpith's user avatar
  • 383
13 votes
7 answers
963 views

What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?

I'm specifically looking for real applications of the following form of MIP: $$\max\,Cx$$ subject to: \begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{...
Junior MIP's user avatar
13 votes
6 answers
1k views

Where can I find documentation on good practices for efficient formulations of a problem?

I am sort of new to mathematical optimization and have to build some fairly complicated models for my thesis. I was wondering where I could find literature to help me develop more efficient versions ...
J. Dionisio's user avatar

1
2 3 4 5
21