Analysis Of Instances Of MOCO Problems Library Of Instances

This task will be useful to analyse the performance of algorithms for solving Multi-objective combinatorial optimization (MOCO) problems. The work will be divided into the two following subtasks.

Subtask 1.1: Characterisation of instances
This sub-task aims at understanding why a numerical instance of MOCO problem is hard to be solved, to identify the determining factors of this difficulty, and to predict their influence on the Pareto set. To run this investigation, two main kinds of instances will be considered: instances with a correlation intra-objective, and instances with a correlation inter-objective. This kind of knowledge is a preliminary step to the goal of leading to a powerful algorithm, according to the numerical instance to perform.

Subtask 1.2: Production of instances
In a second step, a library of relevant numerical instances for selected MOCO problems (assignment, knapsack, shortest paths, spanning trees) will be generated and published on a website in order to provide relevant benchmarks for forthcoming developments of algorithms for MOCO problems. Those instances will review the MCDMlib (a collection of MOCO instances maintained by X. Gandibleux and available online since 1998 on the website of the International Society on MultiCriteria Decision-Making).