Data set

ビットマップ図形詰込み問題

代表的な問題例

data

ビットマップ図形詰込み問題の問題例です．これらの問題例に対する数値実験の結果は下記の論文に掲載されています．

  • S.Umetani and S.Murakami, Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes, arXiv preprints, arXiv:2104.04525, 2021. paper

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

instance #shapes #pieces avg. #lines avg.#arcs avg.#holes degrees

Profiles1 8 32 4.63 0.63 0.00 90 incremental

Profiles2 7 50 7.54 1.50 0.38 90 incremental

Profiles3 6 46 7.93 0.65 0.00 45 incremental

Profiles4 7 54 3.83 0.41 0.00 90 incremental

Profiles5 5 50 7.19 0.00 0.13 15 incremental

Profiles6 9 69 4.60 1.40 0.00 90 incremental

Profiles7 9 9 4.67 0.00 0.00 90 incremental

Profiles8 9 18 4.67 0.00 0.00 90 incremental

Profiles9 16 57 26.61 0.00 0.16 90 incremental

Profiles10 13 91 8.23 0.00 0.00 0

劣モジュラ最大化問題

ランダムに生成した問題例

data results

ランダムに生成した劣モジュラ最大化問題の問題例です．施設配置問題(facility location; FOC)，重み付き被覆問題(weighted coverage; COV)，2部影響度最大化(bipartite influence; INF)に対する問題例を含んでいます．これらの問題例に対する数値実験の結果は下記の論文に掲載されています．

  • 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.

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

集合被覆問題

ランダムな問題例を生成するプログラム

generator data (424MB) results

下記論文と同様の方法で集合被覆問題のランダムな問題例を生成するプログラムです．

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

生成された問題例は以下の性質を満たします．(1) 各変数のコスト係数は1〜100のランダムな整数値を取る．(2) 各列は1つ以上の行を被覆する． (3) 各行は2つ以上の列に被覆される．下表のパラメータ値に従ってクラスI-Nの問題例を新たに生成しました．各クラスは5問の問題例を含みます．本プログラムは他の文献で数値実験に用いられたものと同じ問題例を生成するわけではありません．クラス4-6, A-Hの問題例は他のウェブサイトから問題例を取得して下さい．

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%

これらの問題例に対する数値実験の結果は下記論文に掲載されています．

  • 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)

一般化上界制約付き集合多重被覆問題

ランダムな問題例を生成するプログラム

generator data(1.8GB) results

集合被覆問題の問題例から一般化上界制約付き集合多重被覆問題のランダムな問題例を生成するプログラムです．下表の通り4種類の問題例を生成しました．

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

これらの問題例に対する数値実験の結果は下記論文に掲載されています．

  • 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)

多角形詰込み問題

代表的な問題例

data

多角形詰込み問題に関する多く論文で用いられている代表的な問題例です．これらの問題例に対する数値実験の結果は下記論文に掲載されています．

  • S.Umetani, M.Yagiura, S.Imahori, T.Imamichi, K.Nonobe and T.Ibaraki, Solving the irregular strip packing problem via guided local search for overlap minimization, International Transactions in Operational Research, 16 (2009), 661-683.

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

1次元資材切出し問題

紙菅工業における実例をもとに生成した問題例

data

ある紙管工業における実例を基に作成した問題例です．これらの問題例に対する数値実験の結果は下記論文に掲載されています．

  • 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.

繊維産業における実例をもとに生成した問題例

data

ある化学繊維産業における実例を基に作成した問題例です．これらの問題例に対する数値実験の結果は下記論文に掲載されています．

  • 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.

ランダムに生成した問題例

data

下記の論文にて紹介されている問題例生成プログラムCUTGEN1を用いて生成した問題例です.

  • 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.

これらの問題例に対する数値実験の結果は下記論文に掲載されています．

  • 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.