Instances for testing

[odow]

Issue #105 has demonstrated that we need better testing of the algorithms.

One approach is to hand-craft tests. But that's pretty slow and limiting.

It'd be better if we could have a set of instances in a file format with a corresponding set of efficient solutions that we could check against.

Here's a library of instances: https://github.com/vOptSolver/vOptLib

It doesn't use a standardized file format, and it doesn't have solutions. But we could translate everything into JuMP and then into .mof.json (https://jump.dev/MathOptFormat), and then compare the various algorithms against each other.

The output would be: a standardized set of instances and a set of solutions 😄 which seems like a useful thing for the community.

I'm very open to discussions for ideas on this...

[xgandibleux]

We have many 2-objective and several 3-objective instances on our archives. All of them have been used for numerical experiments in our papers and projects since the last 30 years.

Several instances are indeed already online on https://github.com/vOptSolver/vOptLib (or have been on MCDMlib, MOCOLib and GuepardLib, all maintained also by us in the past).

And for some instances,

• $Y_N$ , the set of non-dominated points
• $X_{E}$, a corresponding set of efficient solutions (or $X_{Em}$, a set of minimal efficient solutions)

are available, e.g.:

• knapsack problems: https://github.com/vOptSolver/vOptLib/blob/master/UKP/uncorrelated.md
• partitioning problems: https://github.com/vOptSolver/vOptLib/tree/master/SPA
• packing problems: https://github.com/vOptSolver/vOptLib/blob/master/SPP/readme.md
• Truck-to-dock Door Assignment Problem: https://github.com/xgandibleux/TDAP/tree/main/res

For

• 2-objective problems: codes for computing $Y_N$ and $X_{E}$ / $X_{Em}$ are available into vOptSpecific.jl for knapsack (jl & C), assignment(jl & C), and facility location problems (jl & C++). ps: this package is not evolving since a long time and it was developed when we were "beginners" in the interface jl & C/C++ (techniques we used for interfacing languages and embed C/C++ binary into julia are probably outdated now); we have in mind the question of moving one day these specific algorithms to MOA as a kind of "global constraint" (one other topic to discuss with interested persons).

• 3-objective problems: we have in our archives all the original codes for computing $Y_N$ and $X_{Em}$ for instances of 3-objective linear assignment problems.

Almost all instances are extensions of single objective instances available on the OR-Library. It is the reason why the format is not standardized and mainly follow the original description provided in the OR-Library. Also the MCDM community who is the main user of these instances was not in favor of using others format/descriptors(as json). Reasons were (1) having files readable without any specific software and (2) having files size smaller as possible. I was a long time from now (I initated it in 1998...), adopting "modern" formats would be more acceptable by users in 2025 (I have a talk in next October on MOP software at the RAMOO meeting, I will probe the audience).

Today, when I come back on these instances, I provide online the parser in julia e.g. for 2-partitioning instances.

I am very interested to follow this discussion; and if they can help the MO-JuMP community, I am ready to dedicate time and to unarchive our ton of files and codes.

[odow]

I started looking into this in #115

One thing I came across is that there might be multiple points in X space for the same Y:

https://github.com/vOptSolver/vOptLib/blob/16ecd822af03c3590db44026a4e4160c31d2a996/UKP/X/2KP100-50.max#L24-L25

[xgandibleux]

Great!

Indeed, for each non-dominated point $y' \in Y_N$ we are talking about the set of efficient solutions in term of

• the maximum complete set $X_{E_M}$: contains all solutions $x \in X$ corresponding to $y'$ (all equivalent solutions)
• a complete set $X_E$: contains at least one solution $x \in X$ corresponding to $y'$ (some equivalent solutions)
• a minimum complete set $X_{E_m}$: contains only one solution $x \in X$ corresponding to $y'$ (without equivalent solution)

ps: This distinction is important for characterising properly a given algorithm (maintaining solutions is costly for several reasons). Unfortunately papers are not rigourous on this, making a comparison of algorithms not straightforward.

[kofgokhan]

So far there are only objective space algorithms and I do not know how likely it is to add multi-objective branch and bound etc.

The algorithms update the search whenever a new nondominated point is found and I believe in all implementations we have something like y = compute_point(f, x) so I think for every nondominated point there will be an efficient solution. It should suffice to check for the equivelance of Y_N in my opinion.