Benchmark instances for binary integer programming problems

This page contains instances of the binary integer programming (BIP) problem in mps format. Unless otherwise specified, it is assumed that the objective function is to be maximized.

Board packing problem (BoPP)

Download:	BoardPacking_MPS.zip (1,684 MB)
Description:	In total 145 instances.
Source:	G. Abraham, G. Dósa, L.M. Hvattum, T. Olaj, and Zs. Tuza. The board packing problem. European Journal of Operational Research, 308:1056-1073, 2023.

Double traveling salesman problem with multiple stacks (DTSPMS)

Download:	DTSPMS_MPS.zip (472 MB)
Description:	In total 275 instances. Reformulated as a maximization problem as described in unpublished work.
Sources:	H.L. Petersen and O.B.G. Madsen. The double travelling salesman problem with multiple stacks - Formulation and heuristic solution approaches. European Journal of Operational Research, 198:139-147, 2009.
	H.L. Petersen, C. Archetti, and M. Grazia Speranza. Exact solutions to the double travelling salesman problem with multiple stacks. Networks, 56:229-243, 2010.
	R.M. Lusby, J. Larsen, M. Ehrgott, and D. Ryan. An exact method for the double TSP with multiple stacks. International Transactions in Operational Research, 17:637-652, 2010.
	L.M. Hvattum and Á. Felipe G. Tirado. The double traveling salesman problem with multiple stacks and a choice of container types. Mathematics, 8:979, 2020.

Football team composition problem (FTCP)

Download:	FTCP_MOD_MPS.zip (<1 MB)
	(Original instances: FTCP_MPS.zip)
Description:	A set of 15 instances. Original instances contain non-integer coefficients with large precision.
Source:	G. Pantuso and L.M. Hvattum. Maximizing performance with an eye on the finances: a chance-constrained model for football transfer market decisions. TOP, 29:583-611, 2021.

General instances (BIP)

Download:	MIPLIB_2010_MOD_MPS.zip (217 MB)
Description:	In total 111 instances from MIPLIB 2010, but converted to maximization problems. Some of the original instances had non-integer coefficients and have been modified to obtain integer coefficients only.
Source:	T. Koch, T. Achterberg, E. Andersen, et al. MIPLIB 2010. Mathematical Programming Computation, 3:103, 2011.

Max-cut problem

Download:	MAXCUT_MPS.zip (28 MB)
Description:	In total 88 instances. The BIP formulation used was described by Bentsen, Hoff, and Hvattum (2022).
Sources:	C. Helmberg and F. Rendl. A spectral bundle method for semidefinite programming. SIAM Journal on Optimization, 10:673-696, 2000.
	Festa, P., P. M. Pardalos, M. G. C. Resende, C. C. Ribeiro. Randomized heuristics for the max-cut problem. Optimization Methods and Software 7:1033-1058, 2002.
	R. Martí, A. Duarte, M. Laguna. Advanced Scatter Search for the Max-Cut Problem. INFORMS Journal on Computing 21:26-38, 2009.

Multidemand multidimensional knapsack problem (MDMKP)

Download:	MDMKP_MPS.zip (24 MB)
Description:	In total 836 instances, with between 100 and 500 variables and between 6 to 101 constraints.
Source:	P. Cappanera and M. Trubian. A local search based heuristic for the demand constrained multidimensional knapsack problem. INFORMS Journal on Computing 17:82-98, 2005

Multidimensional knapsack problem (MKP)

Download:	MKP_MPS.zip (6 MB)
Description:	In total 270 instances, with between 100 and 500 variables and between 5 to 30 constraints.
Source:	P.C. Chu and J.E. Beasley. A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics 32:63-86, 1998

Multiple-choice multidimensional knapsack problem (MMKP)

Download:	MMKP_MPS.zip (4 MB)
Description:	In total 50 instances. Some of the original instances have been modified by scaling the objective function coefficients so that they become integers.
Sources:	S. Khan, K.F. Li, E.G. Manning, and M.M. Akbar. Solving the knapsack problem for adaptive multimedia system. Studia Informatica Universalis, 2:157-178, 2002.
	H. Shojaei, T. Basten, M.C.W. Geilen, and A. Davoodi. A fast and scalable multi-dimensional multiple-choice knapsack heuristic. ACM Transactions on Design Automation of Electronic Systems, 18:51, 32 pages, 2013

Optimum satisfiability problem (OptSAT)

Download:	OPTSAT_MPS.zip (50 MB) and OPTSAT2_MPS.zip (3 MB)
Description:	In total 5,515 instances, with up to 3,000 variables and 15,000 constraints.
Sources:	T. Davoine, P.L. Hammer, and B. Vizvári. A heuristic for boolean optimization problems. Journal of Heuristics, 9:229-247, 2003.
	R.F. da Silva, L.M. Hvattum, and F. Glover. Combining solutions of the optimum satisfiability problem using evolutionary tunneling. MENDEL, 26:23-29, 2020.

Download:	OPTSAT_MAXSAT_MPS.zip (13 MB) and OPTSAT_MINCOST_MPS.zip (3 MB)
Description:	Instances converted from weighted partial maximum satisfiability and minimum cost satisfiability.
Source:	Work in progress, 2021.

Set covering problem

Download:	SCP_MPS.zip (39 MB)
Description:	In total 40 randomly generated instances, with either 500 or 1,000 variables and either 1,000 or 2,000 constraints.
Source:	F. Rodrigues, A. Agra, L.M. Hvattum, and C. Requejo. Weighted proximity search. Journal of Heuristics, 27:459-496, 2021.

Set partitioning problem

Download:	SPP_MPS.zip (86 MB)
Description:	In total 60 instances, from two different sources, with up to one million variables.
Sources:	K. Hoffman and M. Padberg. Solving airline crew scheduling problems by branch-and-cut. Management Science, 39:657-682, 1993.
	M.G.C. van Krieken, H. Fleuren, and R. Peeters. A Lagrangean relaxation based algorithm for solving set partitioning problems. CentER Discussion Paper No. 2004-44, 2004.

Uncapacitated p-median problem

Download:	PMP_MPS.zip (868 MB)
Description:	In total 90 randomly generated instances, with up to one million variables and constraints.
Source:	F. Rodrigues, A. Agra, L.M. Hvattum, and C. Requejo. Weighted proximity search. Journal of Heuristics, 27:459-496, 2021.

Last updated: August 2024.