Optimization Models & Instances - The Quest for Optimality

Design of a more beautiful and usable instance database is scheduled for late 2013; will probably be available early in 2014. Publishing blog content is on a higher level of priority. Thanks for your patience.

Multi-product Multi-period capacitated lot-sizing model

These models are multi-period, multi-product capacitated lot sizing model instances. A short description of the model can be found here.

As these models were generated to test standard MIP solvers and I am not an expert of lot-sizing models, I use a rather direct formulation that does not incorporate any specific craft found in the literature to tackle lot-sizing models (reformulation, strong cutting planes resulting from polyhedral studies, etc.)

Set Name Are used in:
(black: blog
red: paper)
Set Info Downloads
Nb Instances Nb Products (p) Nb Periods (t) Comments Instance Data Model Files Optimal Solutions
P30T21C1 20 30 21 High capacity-to-demand ratio; these instances are really easy to solve. LP Files (zip) SOL Files (zip)
P30T21C2 [1] [2] 20 30 21 Moderately tight capacity-to-demand ratios; more difficult than C1. LP Files (zip) SOL Files (zip)
P30T21C3 20 30 21 Tighter capacity-to-demand ratios than C1 and C2.
P40T14C2 [4] 100 40 14 Moderately tight capacity-to-demand ratios. LP Files (zip) SOL Files (zip)
P50T14C2 100 50 14 Moderately tight capacity-to-demand ratios. LP Files (zip) SOL Files (zip)
P256T64C2 [5] 10 256 64 Larger instances used to test distributed MIP algorithms.   LP Files (zip) SOL Files (zip)

 

Two-Echelon (hierarchical) Capacitated Facility Location with Single Sourcing

These models are single-period, single-product, capacitated facility location models with single sourcing. I use a path-based formulation taken from the following reference:
Klose, A., Drexl, A. (2005). Facility location models for distribution system design, European Journal of Operational Research 162: 4-29.

This problem can be solved quite efficiently using a Lagrangian relaxation and a slightly different formulation:
Tragantalerngsak, S., Holt, J. and Rönnqvist, M. (2000). An exact method for the two-echelon, single-source, capacitated facility location problem. European Journal of Operational Research 123: 473-489.

You can download my localsolver template for solving TESSCFLPfiles. It requires the input of an instance data (.in) file.

Set Name Are used in:
(black: blog
red: paper)
Set Info Downloads
Nb Instances Smallest Instance Largest Instance Comments Instance Data Model Files Optimal Solutions
A Series [3] 25 3 x 5 x 10 25 x 65 x 500 Instances of various sizes. IN Files are to be used with the localsolver lsp file. LP Files (zip)
IN Files (zip)
 
B Series [3] 25 3 x 5 x 10 25 x 65 x 500 Instances of various sizes. IN Files are to be used with the LocalSolver lsp file. LP Files (zip)
IN Files (zip)
 
C Series        

Single-product capacitated facility location model (CFLP)

In this model, one wish to locate facilities to serve a set of customer demands at minimal total cost. The cost is composed of fixed costs related to the opening of the facilities plus a variable transportation cost per unit. The facilities have limited capacity.

Set Name Are used in:
(black: blog
red: paper)
Set Info Downloads
Nb Instances Smallest Instance Largest Instance Comments Instance Data Model Files Optimal Solutions
D Series [6] 50 3 x 10 200 x 1000 Instances of various sizes. LP Files (zip) SOL Files (zip)

Multidimensional Knapsack problem

A classical combinatorial optimization problem. Please note that this is different from the multiple knapsack problem (if you're confused check this). You can find a discussion of the problem in the following paper:
Chu, P.C. and Beasley, J.E. (1998). A Genetic Algorithm for the Multidimensional Knapsack Problem, Journal of Heuristics 4: 63-86.

You can download my localsolver template for solving multidimensional knapsack files. It requires the input of an instance data (.in) file.

Set Name Are used in:
(black: blog
red: paper)
Set Info Downloads
Nb Instances Nb Items Nb Constraints Instance Data Model Files Optimal Solutions
B-1000-5 [3] 10 1000 5 LP Files (zip)
IN Files (zip)
B-2000-10 [3] 10 2000 10 LP Files (zip)
IN Files (zip)
 
B-3000-10 [3] 10 3000 10 LP Files (zip)
IN Files (zip)
B-5000-5 [3] 10 5000 5 LP Files (zip)
IN Files (zip)
B-5000-10 [3] 10 5000 10 LP Files (zip)
IN Files (zip)
B-5000-15 [3] 10 5000 15   LP Files (zip)
IN Files (zip)
 
B-10000-20 [3] 10 10000 20   LP Files (zip)
IN Files (zip)
 
               

Generation parameters for all instances starting with "B":
Item Values: U[1;50]
Item Weights: U[1,90]
Right hand sides: 17 * NbItems