# Tag Info

21

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 instances in mixed integer programming. Naturally that evens out a bit if looking at a longer time frame and more instances. In the past solver developers typically ...

17

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 coloring. I also have kept track of results for a sports scheduling problem, the Traveling Tournament Problem, at http://mat.tepper.cmu.edu/TOURN A couple things I ...

17

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 structures to impose constraints on the dual space. They reduce the number of pricing iterations without compromising the complexity. Unfortunately, they are ...

16

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 benchmark. For example, MIPLIB2017 was specifically compiled in a way to ensure diversity. The design paper for the CEC2018 benchmarks specifically states: The 15 ...

14

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 one is performance profiles. They were introduced in this article: Elizabeth D. Dolan and Jorge J. Moré, Benchmarking optimization software with performance ...

12

Here is a quick summary about the pros and cons of LocalSolver, a global optimization solver combining exact and heuristic techniques. Please note that this summary is written by the LocalSolver team itself, as asked by Kuifje in the comment above. Pros: You will model your problem using nonlinear and set-based mathematical modeling APIs. Then, your math ...

11

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 validation, which is a common practice in other areas (e.g. machine learning). Second, since one can be never sure to avoid a bias, I think it is helpful to state ...

9

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 benchmarking multi-objective solvers. It covers a variety of Multiobjective linear optimization problems (multiobjective combinatorial problems, multiobjective ...

9

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-44, 2000) that discusses this issue in detail.

9

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 supervised by our Marco Lübbecke) is mentioned on the About webpage for the Generic Column Generation (GCG) software. Compare with SCIP's VRP (tiny) example docs. ...

9

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. References [1] Ray, S., Soeanu, A., Berger, J., Debbabi, M. (2014). The multi-depot split-delivery vehicle routing problem: Model and solution algorithm. ...

8

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 somehow more general problem class. $$\{\mbox{MILP}\}\subset\{\mbox{non-convex QCQP}\}$$ There are some off-the-shelf non-convex QCQP (global) solvers, like ...

7

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 : Minizinc challenge)

7

Here's one: CSPLib: A problem library for constraints

7

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 described in the Claudio's answer). Penalty function approaches we tried have generally better performance than dual price smoothing. However, the former are ...

7

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. Two widely used statistical tests are shown to have high probability of type I error in certain situations and should never be used: a test for the difference ...

7

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) optimization instances. The repository contains instances, results, generators etc. for different MO problems and is continuously updated. The repository can be ...

6

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 sample size is "large enough." Usually "large enough" is taken to mean $n\ge30$. You can use a Two Sample $t$-test for this. You want to show that Algorithm $... 6 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, from different researchers and different vendors. I'd love to help build out an open datawarehouse of benchmarks, using our benchmark toolkit on top of ... 6 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-VRPTW problem. A set of 56 large instances, each with 100 customers and 21 recharging stations, and a set of 36 small instances with 5, 10, and 15 customers per ... 5 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 the final lp can be infeasible or the objective can be different because of an artifact in Cplex (mind-numbing detail: it can return mip solutions obeying the ... 5 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 doesn't scale to the types of problems we typically solve with$10^{40}\$ leaf nodes in a scenario tree.) I have been collecting a number of examples in the SDDP....

5

"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 for example were used for testing purpose in "Dentcheva, Darinka, and Andrzej Ruszczyński. "Portfolio optimization with stochastic dominance constraints." ...

5

You can check the Test Sets section of the Stochastic Programming Resources web site. It contains different types of problems—two-stage or multi-stage, mixed or pure IP, and even LP in the different stages. Hopefully, you should find something close to the problem type you are looking for.

4

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 mention. The time windows, on the other hand, are absolute and do not depend on the starting times of the routes. In a classical VRPTW setting, only time windows ...

4

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 by the research, and at the core of many industrial problems. Here are some examples: traveling salesman, vehicle routing, job scheduling, multidimensional ...

4

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 marginally improve the runtime only up to some point. Such optimal number of threads should be checked on a case by case basis. In CPLEX, for instance, the parallelism ...

3

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.2018.0825 (SDVRP with time windows) and https://doi.org/10.1016/j.ejor.2014.04.026 (standard SDVRP).

3

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 time is shorter, that you win in the majority of benchmark instances (which is not a good measure in general, especially because it is intransitive), that you ...

2

You might be able to adjust my vrp generator code to generate some SDVRP problems. That way you'll immediately have road distances etc. I used it to create the Belgium road-km/road-time/air - 50-2750 visits datasets. Whatever you do, post the datasets on vrp-rep.org - we as a community should try to centralize all vrp datasets. (I am not affiliated with vrp-...

Only top voted, non community-wiki answers of a minimum length are eligible