21
votes
Accepted
How much can we expect to increase the speed of mixed integer programming in the next 10 years?
I work at a solver company (SAS Institute Inc.) and can probably weigh in on this a little bit.
The problem with saying anything about performance is that there is a lot of variability between ...
- 3,168
17
votes
The curse of the benchmark instances
Let me add a couple of things based on my experience. I created/collated the DIMACS instances for clique and coloring way back in 1992 and they are still used extensively, primarily for graph ...
- 2,362
17
votes
Accepted
Column generation stabilisation
Stabilization methods are tricky. Dual optimal inequalities are you best chance to obtain significant speed ups. Basically they prevent a bunch of useless dual values by exploiting problem-specific ...
- 1,549
16
votes
The curse of the benchmark instances
There are multiple aspects to this topic.
What can be done by testset compilers to prevent finetuning?
For one, testset creators are usually not including many very similar problems into the ...
- 2,856
14
votes
Statistical tests for benchmark comparison
I know that you explicitly ask for a statistical test, but maybe this is because you don't know about alternatives that are rather established in the community. When comparing algorithms, my number ...
- 5,909
13
votes
Accepted
What are the pros and cons of LocalSolver?
Here is a quick summary of the pros and cons of Hexaly (ex LocalSolver), a global optimization solver combining exact and heuristic techniques. Please note that this summary is written by the Hexaly ...
- 2,936
11
votes
Accepted
The curse of the benchmark instances
To complement Michael's answer, which I think made the main points already:
First, an obvious strategy is to separate the data set used for testing and tuning, from the data set that are used in ...
- 2,705
9
votes
Benchmark problems for combinatorial multi-objective optimisation
vOptLib: Library of numerical instances for MultiObjective Linear Optimization problems
From the site:
vOptLib (short for vector optimization library) is a collection
problem instances for ...
- 5,864
9
votes
Statistical tests for benchmark comparison
I think there are many different factors to consider. There's a very good paper by Coffin and Saltzman (Statistical Analysis of Computational Tests of Algorithms
and Heuristics, INFORMS JOC 12(1): 24-...
- 13.1k
9
votes
Column generation stabilisation
Has anyone performed a benchmark of the various stabilization techniques in column generation? ... implemented in SCIP ...
The thesis "Generic Branch-Cut-and-Price" (.PDF), by Gerald Gamrath (and ...
- 2,098
9
votes
Accepted
Vehicle routing benchmark instances
For a table of benchmark instances on SDVRP you can have a look at Table 4 (Benchmark on known SDVRP problem instances) of Ray et al. (2014)1. More details are provided in reference [30]2 of the paper....
- 5,342
8
votes
Accepted
Bilinear programming vs Mixed integer linear programming performance comparison
Constraining a variable to be binary could be expressed as a quadratic constraint:
$$
x\in\{0,1\} \iff x(1-x)=0
$$
This is often mentioned in non-convex QCQP articles to present non-convex QCQP is a ...
- 1,046
7
votes
Accepted
VRP benchmark instances with charging stations
E-VRP-NL has been used in The electric vehicle routing problem with capacitated
charging stations. Also authors in the paper mentioned by A.Omidi design two new sets of benchmark instances for the E-...
- 8,622
7
votes
Are there some benchmark problems for CSP Solvers?
The Minizinc constraint programming benchmark models are in Minzinc file format : https://github.com/MiniZinc/minizinc-benchmarks. Each year several CP solvers compete on some problems (see here : ...
- 71
7
votes
Are there some benchmark problems for CSP Solvers?
Here's one: CSPLib: A problem library for constraints
- 30.5k
7
votes
Benchmark problems for scenario-based stochastic optimization
You can check the Test Sets section of the Stochastic Programming Resources website. It contains different types of problems — two-stage or multi-stage, mixed or ...
- 161
7
votes
Column generation stabilisation
In our JOC paper (Pessoa et al.) mentioned by Claudio, we have performed comparison (on 9 different problems including VRP) between some penalty function approaches and dual price smoothing (both are ...
- 1,394
7
votes
Statistical tests for benchmark comparison
Options for you: McNemarNP, $t$ test (with variants)P, WilcoxonNP, sign testNP, FriedmanNP
Dietterich (1998)
Five statistical tests are compared primarily on the type I error produced. Emphasis mine.
...
- 5,342
7
votes
Benchmark problems for combinatorial multi-objective optimisation
There is also the MOrepo maintained by Lars Relund Nielsen. MOrepo describe itself as:
This repository is a response to the needs of researchers from the MCDM society to access multi-objective (MO) ...
- 6,352
6
votes
Statistical tests for benchmark comparison
A good thing for you to invoke in your case is the Central Limit Theorem. It states, roughly speaking, that you can assume a normal distribution (a special case of the Gaussian Function) provided your ...
- 161
6
votes
Statistical tests for benchmark comparison
Choosing is loosing.
We should be collecting raw benchmarks results at a grand scale, independent of how we evaluate them. And we should have a free, open, objective website hosting all that data, ...
- 4,673
5
votes
CPLEX output log
By default, Gams/Cplex will try to calculate duals by fixing the integer variables and then resolving as an LP. This is the "final solve". Usually the objectives are the same. In rare cases ...
- 2,586
5
votes
Benchmark problems for scenario-based stochastic optimization
Pantelis,
It is a great detriment that no such collection of examples exists. One problem is that there is no established format for multistage problems like MPS. (There is SMPS [paper], but this ...
- 51
5
votes
Benchmark problems for scenario-based stochastic optimization
"Ruszczynski, Andrzej, and Robert J. Vanderbei. "Frontiers of stochastically nondominated portfolios." Econometrica 71.4 (2003): 1287-1297". This paper provides a large number of test problems which ...
- 8,622
4
votes
Capacitated VRP-TW: Gehring & Homberger instances
You seem to be mixing up two related but different attributes: time windows and route duration. Duration is the time elapsed since the beginning of a route, and depends on the starting time as you ...
- 1,549
4
votes
How much can we expect to increase the speed of mixed integer programming in the next 10 years?
More than speedup improvement factors on a bunch of abstract LP/MPS files, we at LocalSolver think that this is more interesting to look at problems. We look at academic problems, used as benchmarks ...
- 2,936
4
votes
When solving many MILPs how to assign CPU cores to solver instances?
So we know that MILP instances are independent and that the total throughput is to be maximized. In practice, increasing the number of threads used by a solver to solve a MILP instance could ...
- 2,140
3
votes
Vehicle routing benchmark instances
The usual way to check which instances are still open is to check the latest paper(s) on exact solution of the problem. The latest papers seem to be https://pubsonline.informs.org/doi/abs/10.1287/trsc....
- 1,394
3
votes
Statistical tests for benchmark comparison
Actually, I asked myself the same question some time ago. But after some time I figured out that the question is just too imprecise.
"Faster" can mean a lot of things. It can mean that the average ...
- 1,110
3
votes
Runtimes for benchmarking
I agree with the comment by @Kuifje: record the solve time as this is what you are concerned with.
However, if you are comparing to some other method (e.g. a smaller MIP with weaker bound or a ...
- 6,352
Only top scored, non community-wiki answers of a minimum length are eligible