mUBQP: Multiobjective unconstrained binary quadratic programming


| Description | Format | Generator, evaluation functions | Instances | Bibliography |

Description

The four main parameters of the family of mUBQP are:

  • ρ: the objective correlation coefficient
  • M: the number of objective functions
  • N: the length of bit strings
  • d: the matrix density (frequency of non-zero numbers)


The mUBQP is described in:


Format

The syntax of mUBQP instances is inspired by the DIMACS Max-Sat format. The format also follows the ρMNK-landscapes format.

An instance is described by the following three sections that must appear in the order shown:

a) Comment section

  1. The section is optional and should be used to give additional information concerning the instance (the name, the source, a general description, etc.)
  2. Each line of the section starts with the letter "c" (lower case)
  3. The section is made of an arbitrary number of consecutive lines

b) Problem section

  1. The section is used to describe the problem type
  2. The section is made of a single line that starts with the letter "p" (lower case)
  3. The line format is the following:
     p MUBQP <rho> <M> <N> <d>

where <rho> is a real number that gives objective correlation coefficient, <M> is a positive integer that gives the number of objective functions, <N> is a positive integer that gives the length of bit strings, and <d> is a real number between 0 and 1 that gives the frequency of non-zero number in the matrices. These fields are separated by blank or by TAB characters

c) Matrices section

  1. The section is used to describe the matrices of mUBQP problem.
  2. The sections starts with this line: p matrices
  3. The following lines gives the matrix coefficients of each matrix: one matrix for each objective.
  4. The number c_{m,i,j} is the coefficient (i,j) -- line i, column j -- of the matrix of the objective m.
  5. One column for each objective function
  6. The coefficients are ordered from the first column to the last column (from (1,1) to (N,1) and then (1,2) to (N,2) and so on to (N,N)):

c_{1,1,1} ... ... c_{M,1,1}
c_{1,2,1} ... ... c_{M,2,1}
... ...
c_{1,N,1} ... ... c_{M,N,1}
c_{1,1,2} ... ... c_{M,1,2}
... ...
... ...
c_{1,N,2} ... ... c_{M,N,2}
c_{1,1,3} ... ... c_{M,1,3}
... ...
... ...
c_{1,N,N} ... ... c_{M,N,N}

Example

One example for an instance with a negative objective correlation -0.9, two objectives M=2, a bit string of length N=3, and a density d=0.9.

With N=3, there is 3 x 3 = 9 coefficients for each objective matrix. In this example the matrix of the first objective is:

67-80
-92-53-32
0-960

And the matrix of the second objective is:
||border=1 width=40%

30200
-73-3477
070

which gives the following instance file:

c
c Example of instance
c
c
p MUBQP -0.9 2 3 0.8
p matrices
67 30
-92 -73
0 0
-8 20
-53 -34
-96 7
0 0
-32 77
0 0

Source code of generator and evaluation functions

The source code of a instance generator (in R) and the multiobjective fitness functions (in C, C++, java, and under paradiseo framework) are available on the svn of the project:

svn checkout http://svn.code.sf.net/p/mocobench/code/trunk/mubqp/generator mocobench-mubqp

For more details on project svn, see the sourceforge repository.

You can download the generator which is written in R: mubqpGenerator.R
If you need to install R, please visit the official page of R project

You can also browse the svn repository to download one of the multiobjective fitness function written in C, C++, java, or under paradiseo framework: browse generator repository.

The paradiseo source code is plugged (or can be plugged) with classical multiobjective algorithms (NSGAII, Pareto LS, etc.).


Data files of instances

All instance files are available on the svn of the project. See svn to access directly with svn.

If you want to access only to some instances, you can browse the repository: browse instances repository.

File names are normalized: mubqp_<rho>_<M>_<N>_<d>_<seed>.dat
where <rho>, <M>, <N>, and <d> are the main parameters of the instance, and <seed> is the random seed used to produce the instance with mubqpGenerator.R.

If you don't want to download the instances, you can produce them (and others) with the available scripts written in bash, or in python. They both use the generator in R.


Bibliography


Please contact us for any addition.

2014

  • A. Liefooghe, S. Verel, J-K. Hao, A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming. In Journal: Applied Soft Computing, vol. 16, , p. 10-19, 2014.
  • Zhou, Y., Wang, J., & Yin, J. (2013, October). A directional-biased tabu search algorithm for multi-objective unconstrained binary quadratic programming problem. In Advanced Computational Intelligence (ICACI), 2013 Sixth International Conference on (pp. 281-286). IEEE.

2015

  • Liefooghe, A., Verel, S., Paquete, L., & Hao, J. K. (2015, March). Experiments on local search for bi-objective unconstrained binary quadratic programming. In International Conference on Evolutionary Multi-Criterion Optimization (pp. 171-186). Springer International Publishing.
  • de Souza, M. Z., & Pozo, A. T. R. (2015, November). Multiobjective Binary ACO for Unconstrained Binary Quadratic Programming. In 2015 Brazilian Conference on Intelligent Systems (BRACIS) (pp. 86-91). IEEE.

2016

  • Zangari, M., Santana, R., Mendiburu, A., & Pozo, A. (2016, July). On the Design of Hard mUBQP Instances. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference (pp. 421-428). ACM.
  • Xue, L. Y., Zeng, R. Q., Wang, Y., & Shang, M. S. (2016, August). Solving Bi-objective Unconstrained Binary Quadratic Programming Problem with Multi-objective Backbone Guided Search Algorithm. In International Conference on Intelligent Computing (pp. 745-753). Springer International Publishing.
  • Huo, C., Zeng, R., Wang, Y., & Shang, M. (2016, October). A Multi-parent Crossover Based Genetic Algorithm for Bi-Objective Unconstrained Binary Quadratic Programming Problem. In Bio-Inspired Computing-Theories and Applications (pp. 10-19). Springer, Singapore.