This page provides input files and the respective best known solution files for instances of the Orthogonal Discrete Milling Problem (ODMP) described in [1] and [2] and known to be NP-hard.
How to cite this page
Use the BibTeX entry:
@Misc{odmp-instances-page,
author = {Igor R. de Assis and Cid C. de Souza},
title = {Benchmark {I}nstances for the {Orthogonal Discrete Milling Problem}},
year = {2011},
note = {\sl{www.ic.unicamp.br/$\sim$cid/Problem-instances/Milling}}
}
Or equivalent if you are not using BibTeX.
Problem
Consider an orthogonal polygon with holes P called pocket and a unit square Q called cutter.
A feasible solution for ODPM is a closed curve, not necessarily simple, traversed by Q whose Minkowski cover is equivalent to the pocket. The curve is limited to have axis-parallel edges and, hence, all its turns are either orthogonal or U-turns. Orthogonal turns have cost 1 while U-turns are assigned with cost 2.
File format
Instances
The input files are the subdivision graph of the orthogonal polygon when using a unit square cutter.
name: (string with the name of the instance)
type_of_instance: GRID
number_of_vertices: (integer with the number of vertices)
number_of_edges: (integer with the number of edges)
side: (integer with the size of a square grid that can embed the instance)
(* triples of integers u,r,c separated by space where r is the row and c the column of the vertex u)
(** pairs of integers u,v separated by space meaning there is an edge between u and v)
* There are number_of_vertices lines, each with one triple.
** There are number_of_edges lines, each with one pair.
Solutions
The solution files is a header with metadata from the solution and an ordered list of edges representing the solution.
name: (string with the name of the instance)
instance_file: (string with the path to the input file)
primal_bound: (* double with the best found primal bound)
dual_bound: (* double with the best found dual bound)
number_of_edges: (integer with the number of edges of the solution)
(ordered list of edges of the solution)
* The solution is optimal when primal_bound equals dual_bound.
Instances
You can find below the sets of instances A and B used to generate the results found in [2] and [3] respectively.
Set of instances A:
Set of instances B:
Solutions of Set A
You can find below the respective solutions found by the given algorithms. Detailed descriptions of the algorithms can be found in [2].
Unless otherwise specified, all solutions correspond to executions in a a machine with an Intel Core2 Quad Q9550 @ 2.83GHz processor and 8GB RAM.
Exact
Approximate
Gardener's Heuristic
Solutions of Set B
You can find below the respective solutions found by the given algorithms. Detailed descriptions of the algorithms can be found in [3].
Unless otherwise specified, all solutions correspond to executions in a a machine with an Intel Core2 Quad Q9550 @ 2.83GHz processor and 8GB RAM.
Exact
New Approximate
New Gardener's Heuristic
Matheuristic
References
- [1] Arkin, E.M., Bender, M.A., Demaine, E., Fekete, S.P., Mitchell, J.S.B., Sethia, S.: Optimal covering tours with turn costs. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms. (2001) 138–147^
- [2] de Assis, I.R., de Souza, C.C.: Experimental Evaluation of Algorithms for the Orthogonal Milling Problem with Turn Costs. Accepted for publication in the Proceedings of the 10th International Symposium on Experimental Algorithms (SEA 2011) to be published in the LNCS series edited by Springer. ^
- [3] de Assis, I.R., de Souza, C.C., Crepaldi B.C.: Heuristics for the Orthogonal Milling Problem. (Submitted)^
Contact
Cid C. de Souza
Institute of Computing (IC)
University of Campinas (UNICAMP)
Av. Albert Einstein nº 1251
Cidade Universitária Zeferino Vaz
Barão Geraldo - Campinas - SP
13083-852
phone.: (55) (19) 3521 5877
fax...: (55) (19) 3521 5847
e-mail: 