GAP instances

GAP (generalized assignment problem) instances


The instances of types A, B, C and D with n <= 200 are exactly the same with
those in OR-Library.
Other instances (i.e., type E instances and instances with n >= 400) are
generated by us. All the instances in this web site were solved as minimization
problems in the papers listed below.

NOTE: Types D and E instances should be solved as minimization problems;
      otherwise they are trivial.

Some of these instances are used in:

  P.C. Chu and J.E. Beasley,
  A genetic algorithm for the generalized assignment problem,
  Computers & Operations Research, 24 (1997) 17-23.

  M. Yagiura, T. Yamaguchi and T. Ibaraki,
  A Variable Depth Search Algorithm for the Generalized Assignment Problem,
  in: Meta-Heuristics: Advances and Trends in Local Search Paradigms for
  Optimization, eds. S. Voss, S. Martello, I.H. Osman and C. Roucairol,
  (Kluwer Academic Publishers, Boston, 1999) pp. 459-471.

  M. Yagiura, T. Yamaguchi and T. Ibaraki,
  A Variable Depth Search Algorithm with Branching Search for the Generalized
  Assignment Problem, Optimization Methods and Software, 10 (1998) 419-441.

  M. Yagiura, T. Ibaraki and F. Glover,
  An Ejection Chain Approach for the Generalized Assignment Problem,
  INFORMS Journal on Computing, 16 (2004) 133-151.

  M. Yagiura, T. Ibaraki and F. Glover,
  A Path Relinking Approach for the Generalized Assignment Problem,
  Proc. International Symposium on Scheduling, Japan,
  June 4-6, 2002, pp. 105-108.

  M. Yagiura, T. Ibaraki and F. Glover,
  A Path Relinking Approach with Ejection Chains for the Generalized Assignment Problem,
  European Journal of Operational Research, 169 (2006) 548-569.
  abstract 


The format is the same with those in OR-Library:

number of agents (m), number of jobs (n)
 for each agent i (i=1,...,m) in turn:
     cost of allocating job j to agent i (j=1,...,n)
 for each agent i (i=1,...,m) in turn:
     resource consumed in allocating job j to agent i (j=1,...,n)
 resource capacity of agent i (i=1,...,m)

Type A instances (tar + gzip)   Type A instances (zip)
Type B instances (tar + gzip)   Type B instances (zip)
Type C instances (tar + gzip)   Type C instances (zip)
Type D instances (tar + gzip)   Type D instances (zip)
Type E instances (tar + gzip)   Type E instances (zip)

Mutsunori YAGIURA