Most Popular
1500 questions
24
votes
4 answers
What instances can be solved today by modern solvers (pure LP)?
I have found a PowerPoint presentation in which the presentor Hall claims instances could be of the size of 108 in variables and constraints to be solved today. I assume that he meant sparse problems. Bixby claims that since CPLEX 5 the problem size…
Gehhilfe
- 453
- 3
- 6
24
votes
2 answers
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 factor of over 1.1M X since the early 1990s.…
Michael Lindahl
- 1,659
- 6
- 22
24
votes
3 answers
Combinatorial problem in my daughter’s class
In Denmark, a rather substantial amount of work and effort has gone into reducing bullying in the Danish public schools. Many initiatives, which purposes are to strengthen the unity and solidarity in the individual classes, have been introduced (and…
Sune
- 6,457
- 2
- 17
- 31
24
votes
5 answers
How can I remember the rules for taking the dual of a linear program (LP)?
When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?
David M.
- 2,077
- 9
- 26
24
votes
2 answers
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 interested in).
Then, the question here asks about…
EhsanK
- 5,864
- 3
- 17
- 54
24
votes
4 answers
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
Modelling approaches for domain problems is well…
fhk
- 1,069
- 6
- 14
24
votes
5 answers
Find feasible point in polynomial time in linear programming
Background
A while ago my team was implementing an interior point LP solver and we came across the following conundrum:
Is there a polynomial-time algorithm to find a feasible starting point
in linear programming? If so, what is the…
Nikos Kazazakis
- 12,121
- 17
- 59
23
votes
1 answer
Polynomially solvable problems with exponential extension complexity
The maximum matching problem is solvable in polynomial time using Edmonds' blossom algorithm. However, unlike for example the spanning tree polytope, it has been proven fairly recently that the matching polytope has exponential extension complexity,…
Rolf van Lieshout
- 2,325
- 11
- 20
23
votes
5 answers
Solving ATSP problem for large-scale problem
I want to solve the Asymmetric TSP for a large-scale problem for an industrial application where the company cannot buy a commercial software license. For their applications, it is very important to find good solutions within a short computation…
Amin
- 2,150
- 7
- 20
23
votes
3 answers
Difference between stochastic optimization and robust optimization
I would like to know whether stochastic optimization and robust optimization are the same and if not, what is the main difference between them. I did an Internet search and I found the following…
PeterBe
- 1,632
- 2
- 15
- 30
23
votes
9 answers
What are Operations Research applications for 'good causes'?
I am looking for applications of OR for good causes, possibly with some literature. I intend a good cause loosely defined in the sense that the scope is that of improving the well-being of others, e.g., fighting poverty, raising charity funds,…
k88074
- 1,661
- 8
- 18
23
votes
9 answers
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 approach. What are some other problems where column…
EhsanK
- 5,864
- 3
- 17
- 54
23
votes
4 answers
How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition
Combinatorial Benders decomposition is a mathematical programming technique consisting into dividing a problem into a master problem and a sub problem.
The master problem is solved to optimality (or alternatively for a MIP, every time a potential…
Renaud M.
- 2,408
- 1
- 11
- 27
22
votes
3 answers
How to (graphically) present computational results?
I am interested in evaluating and demonstrating various aspects of the performance of general solvers for mathematical optimization problems (in particular MILPs). I assume that I have a good testset of instances. What "revealing" experiments…
Marco Lübbecke
- 5,919
- 22
- 64
22
votes
4 answers
What is a solution?
Consider a standard optimization problem: Minimize an objective function with respect to constraints. My question is:
What does the term "solution of the optimization problem" mean?
At first I would think that the answer is obviously:
A solution…
Dirk
- 381
- 3
- 12