Data set

Submodular function maximization

Randomly generated test instances and detailed computational results

data results

This is a set of randomly generated test instances for submodular function maximization problem. We have generated three types of well-known benchmark instances called facility location (FOC), weighted coverage (COV) and bipartite influence (INF) according to the following papers.

• Y.Kawahara, K.Nagano, K.Tsuda and J.A.Bilmes, Submodularity cuts and applications, In Proceedings of the 22nd International Conference on Neural Information Processing Systems (NIPS2009), 916-924.

• S.Sakaue and M.Ishihata, Accelerated best-first search with upper-bound computation for submodular function maximization. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI-18), 1413-1421.

We have demonstrated the computational results for the test instances in the following paper.

• N.Uematsu, S.Umetani and Y.Kawahara, An efficient branch-and-cut algorithm for submodular function maximization, Journal of the Operations Research Society of Japan, 63 (2020), 41-59. DOI: 10.15807/jorsj.63.41 (open access)

Set covering problem (SCP)

Random test instance generator and data

generator data (424MB) results

This is a random test instance generator for SCP using the scheme of the following paper, namely the column cost c[j] are integer randomly generated from [1,100]; every column covers at least one row; and every row is covered by at least two columns.

• E.Balas and A.Ho, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study, Mathematical Programming, 12 (1980), 37-60.

We have newly generated Classes I-N with the following parameter values, where each class has five instances. We note that our program does not generate the same instances as those in the literature. You should take instances of Class 4-6 and A-H from other web sites.

instance #rows #columns density(%)

I.1-I.5 1000 50,000 1.0%

J.1-J.5 1000 100,000 1.0%

K.1-K.5 2000 100,000 0.5%

L.1-L.5 2000 200,000 0.5%

M.1-M.5 5000 500,000 0.25%

N.1-N.5 5000 1,000,000 0.25%

We have demonstrated the computational results for the test instances in the following paper.

• S.Umetani, Exploiting variable associations to configure efficient local search algorithms in large-scale binary integer programs, European Journal of Operational Research, 263 (2017), 72-81. DOI: 10.1016/j.ejor.2017.05.025 (open access)

Set multicover problem with generalized upper bounds (SMCP-GUB)

Random test instance generator and data

generator data(1.8GB) results

This is a random test instance generator for SMCP-GUB based on SCP instances. We have generated four types of instances.

instance type (GUB / Group size)

instance #rows #columns density(%) type1 type2 type3 type4

G.1-G.5 1000 10,000 2.0% 1/10 10/100 5/10 50/100

H.1-H.5 1000 10,000 5.0% 1/10 10/100 5/10 50/100

I.1-I.5 1000 50,000 1.0% 1/50 10/500 5/50 50/500

J.1-J.5 1000 100,000 1.0% 1/50 10/500 5/50 50/500

K.1-K.5 2000 100,000 0.5% 1/50 10/500 5/50 50/500

L.1-L.5 2000 200,000 0.5% 1/50 10/500 5/50 50/500

M.1-M.5 5000 500,000 0.25% 1/50 10/500 5/50 50/500

N.1-N.5 5000 1,000,000 0.25% 1/100 10/1000 5/100 50/1000

We have demonstrated the computational results for the test instances in the following paper.

• S. Umetani, M.Arakawa and M.Yagiura, Relaxation heuristics for the set multicover problem with generalized upper bound constraints, Computers and Operations Research, 93 (2018), 90-100. DOI: 10.1016/j.cor.2018.01.007 (open access)

instance #shapes #pieces avg. #vertices degrees

Albano 8 24 7.25 0,180

Dagli 10 30 6.30 0,180

Dighe1 16 16 3.87 0

Dighe2 10 10 4.70 0

Fu 12 12 3.58 0,90,180,270

Jakobs1 25 25 5.60 0,90,180,270

Jakobs2 25 25 5.36 0,90,180,270

Mao 9 20 9.22 0,90,180,270

Marques 8 24 7.37 0,90,180,270

Shapes0 4 43 8.75 0

Shapes1 4 43 8.75 0,180

Shapes2 7 28 6.29 0,180

Shirts 8 99 6.63 0,180

Swim 10 48 21.90 0,180

Trousers 17 64 5.06 0,180

One-dimensional cutting stock problem (1DCSP)

Test instances in a paper tube industry
data

This file includes two sets of instances. The first set includes 48 random instances generated by a modification of CUTGEN (Gau and Wascher, 1995). The second set includes 6 instances taken from a real applications in a paper tube industry in Japan. We have demonstrated the computational results for the test instances in the following paper.

• K.Matsumoto, S.Umetani and H.Nagamochi, On the one-dimensional stock cutting problem in the paper tube industry, Journal of Scheduling, 14 (2011), 281-290.

Test instances in a chemical fiber company

data
These instances are taken from a real applications in a chemical fiber company in Japan. There are 40 instances with the number of product types ranging from 6 to 29, the length of stock rolls 9080, 5180, the number of demands for each product type ranging from 2 to 264, the length of each product type ranging from 500 to 2000. We have demonstrated the computational results for the test instances in the following paper.

• S.Umetani, M.Yagiura and T.Ibaraki, One dimensional cutting stock problem to minimize the number of different patterns, European Journal of Operational Research, 146 (2003), 388-402.

Randomly generated test instances

data
These instances are generated by CUTGEN, which is coded by T.Gau and G. Wascher. The Detail of this problem generator is presented in the following paper.

• T.Gau and G.Wascher, CUTGEN1: A Problem Generator for the Standard One-dimensional Cutting Stock Problem, European Journal of Operational Research, 84 (1995), 572-579.

There are 1800 instances of 18 classes. We have demonstrated the computational results for the test instances in the following paper.

• S.Umetani, M.Yagiura and T.Ibaraki, One-dimensional cutting stock problem with a given number of setups: A hybrid approach of metaheuristics and linear programming, Journal of Mathematical Modelling and Algorithms, 5 (2006), 43-64.