×

Orientational variable-length strip covering problem: a branch-and-price-based algorithm. (English) Zbl 1487.90555

Summary: In this article, we study a challenging optimization problem, namely the orientational variable-length strip covering problem. Given a large rectangular region and multiple orientational strips with variable lengths, the strips should be positioned and their lengths be determined such that their union can cover the large region with the minimal total area. This problem is motivated by the real-world problem in which multiple Earth observation satellites are used to image a large region in a cooperative pattern. It is a challenging nonlinear combinatorial optimization problem in continuous space. We propose a set-covering-problem-like integer programming formulation for the problem based on grid discretization and prove that the optimal solutions can be achieved when the strips take discrete values. As there is a large number of columns, we use a column generation method to solve the linear relaxation problem and an enumeration algorithm to solve the subproblem. To accelerate the solution, we propose a provable dominance rule to greatly reduce the solution space of the subproblem, enabling the application of an implicit enumeration (IE) algorithm. Then, we propose a cell-gathered approximate pricing method based on the definition of nested father-child grids. As a result, an efficient branch-and-price-based algorithm (BPBA) is developed. The numerical tests on random instances show that the dominance rule can reduce the subproblem’s solutions by almost 74% and the BPBA can run five times faster than Gurobi (commercial solving software) to find comparable solutions on average.

MSC:

90C27 Combinatorial optimization
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming

Software:

Gurobi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aardal, K.; Den Berg, P. V.; Gijswijt, D.; Li, S., Approximation algorithms for hard capacitated k-facility location problems, European Journal of Operational Research, 242, 2, 358-368 (2015) · Zbl 1341.90080
[2] Abbott, H. L.; Katchalski, M., Covering squares with squares, Discrete and Computational Geometry, 24, 2, 151-170 (2000) · Zbl 0960.52007
[3] Addis, B.; Locatelli, M.; Schoen, F., Disk packing in a square: A new global optimization approach, Informs Journal on Computing, 20, 4, 516-524 (2008) · Zbl 1243.90084
[4] Amaldi, E.; Bosio, S.; Malucelli, F.; Yuan, D., Solving nonlinear covering problems arising in Wlan design, Operations Research, 59, 1, 173-187 (2011) · Zbl 1218.90117
[5] Andrea, C.; Marco, L., A heuristic approach for packing identical rectangles in convex regions, Computers & Operations Research, 38, 9, 1342-1350 (2011) · Zbl 1208.90141
[6] Baker, E. K., Efficient heuristic algorithms for the weighted set covering problem, Computers & Operations Research, 8, 4, 303-310 (1981)
[7] Banhelyi, B.; Palatinus, E.; Levai, B. L., Optimal circle covering problems and their applications, Central European Journal of Operations Research, 23, 4, 815-832 (2015) · Zbl 1339.52013
[8] Bansal, M.; Kianfar, K., Planar maximum coverage location problem with partial coverage and rectangular demand and service zones, Informs Journal on Computing, 29, 1, 152-169 (2017) · Zbl 1364.90285
[9] Bazaraa, M. S.; Goode, J. J., A cutting-plane algorithm for the quadratic set-covering problem, Operations Research, 23, 1, 150-158 (1975) · Zbl 0331.90043
[10] Bennell, J. A.; Cabo, M.; Martinezsykora, A., A beam search approach to solve the convex irregular bin packing problem with guillotine cuts, European Journal of Operational Research, 270, 1, 89-102 (2018) · Zbl 1403.90562
[11] Beraldi, P.; Ruszczynski, A., The probabilistic set-covering problem, Operations Research, 50, 6, 956-967 (2002) · Zbl 1163.90655
[12] Berman, O.; Krass, D., The generalized maximal covering location problem, Computers & Operations Research, 29, 6, 563-581 (2002) · Zbl 0995.90056
[13] Berman, O.; Krass, D.; Drezner, Z., The gradual covering decay location problem on a network, European Journal of Operational Research, 151, 3, 474-480 (2003) · Zbl 1053.90076
[14] Berthold, T. (2006). Primal heuristics for mixed integer programs.
[15] Beyaz, M.; Dokeroglu, T.; Cosar, A., Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2d bin packing problems, Applied Soft Computing, 36, 236-245 (2015)
[16] Cherri, L. H.; Mundim, L. R.; Andretta, M.; De Toledo, F. M.B.; Oliveira, J. F.; Carravilla, M. A., Robust mixed-integer linear programming models for the irregular strip packing problem, European Journal of Operational Research, 253, 3, 570-583 (2016) · Zbl 1346.90626
[17] Christ, T., Beyond triangulation: covering polygons with triangles, Algorithms and data structures, 231-242 (2011), Springer: Springer Heidelberg, Berlin, Germany · Zbl 1342.68331
[18] Church, R.; ReVelle, C., The maximal covering location problem, Papers of the Regional Science Association, 32, 1, 101-118 (1974)
[19] Côte, J.; Gendreau, M.; Potvin, J., An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints, Operations Research, 62, 5, 1126-1141 (2014) · Zbl 1327.90254
[20] Current, J. R.; Storbeck, J. E., Capacitated covering models, Environment and Planning B-planning & Design, 15, 2, 153-163 (1988)
[21] Curtin, K. M.; Hayslettmccall, K.; Qiu, F., Determining optimal police patrol areas with maximal covering and backup covering location models, Networks and Spatial Economics, 10, 1, 125-145 (2010) · Zbl 1183.90288
[22] Desrosiers, J.; Lübbecke, M. E., Column generation, 1-32) (2005), Springer · Zbl 1246.90093
[23] Erdos, P.; Graham, R. L., On packing squares with equal squares, Journal of Combinatorial Theory, Series A, 19, 1, 119-123 (1975) · Zbl 0324.05018
[24] Fallah, H.; Sadigh, A. N.; Aslanzadeh, M., Facility location, Contributions to Management Science, 145-176) (2009), Springer
[25] Friedman, E., Packing unit squares in squares: A survey and new results, Electronic Journal of Combinatorics (2009)
[26] Gurobi (2018). Gurobi optimizer reference manual. Gurobi Optimization, LLC.
[27] Haghani, A. E., Capacitated maximum covering location models: Formulations and solution procedures, Journal of Advanced Transportation, 30, 3, 101-136 (1996)
[28] Hu, X.; Zhu, W.; An, B.; Jin, P.; Xia, W., A branch and price algorithm for eos constellation imaging and downloading integrated scheduling problem, Computers & Operations Research, 104, 74-89 (2019) · Zbl 1458.90308
[29] Kallrath, J.; Rebennack, S.; Kallrath, J.; Kusche, R., Solving real-world cutting stock-problems in the paper industry: Mathematical approaches, experience and challenges, European Journal of Operational Research, 238, 1, 374-389 (2014) · Zbl 1338.90233
[30] Kennedy, T. G., Compact packings of the plane with two sizes of discs, Discrete and Computational Geometry, 35, 2, 255-267 (2006) · Zbl 1092.52010
[31] Kerkkamp, R. B.O.; Aardal, K., A constructive proof of swap local search worst-case instances for the maximum coverage problem, Operations Research Letters, 44, 3, 329-335 (2016) · Zbl 1408.90163
[32] Kumar, V. S.A.; Ramesh, H., Covering rectilinear polygons with axis-parallel rectangles, SIAM Journal on Computing, 32, 6, 1509-1541 (2003) · Zbl 1041.68131
[33] Lanzagutierrez, J. M.; Crawford, B.; Soto, R.; Berrios, N.; Gomezpulido, J. A.; Paredes, F., Analyzing the effects of binarization techniques when solving the set covering problem through swarm optimization, Expert Systems With Applications, 70, 67-82 (2017)
[34] Lawler, E. L.; Wood, D. E., Branch-and-bound methods: A survey, Operations Research, 14, 4, 699-719 (1966) · Zbl 0143.42501
[35] Martinezsykora, A.; Alvarezvaldes, R.; Bennell, J. A.; Ruiz, R.; Tamarit, J. M., Matheuristics for the irregular bin packing problem with free rotations, European Journal of Operational Research, 258, 2, 440-455 (2017) · Zbl 1394.90488
[36] Maximo, V. R.; Nascimento, M. C.V.; De Carvalho, A. C.P. L.F., Intelligent-guided adaptive search for the maximum covering location problem, Computers & Operations Research, 78, 129-137 (2017) · Zbl 1391.90387
[37] Murray, A. T.; Tong, D., Coverage optimization in continuous space facility siting, International Journal of Geographical Information Science, 21, 7, 757-776 (2007)
[38] Pirkul, H.; Schilling, D. A., The capacitated maximal covering location problem with backup service, Annals of Operations Research, 18, 1, 141-154 (1990) · Zbl 0707.90066
[39] Porumbel, D.; Goncalves, G.; Allaoui, H.; Hsu, T., Iterated local search and column generation to solve arc-routing as a permutation set-covering problem, European Journal of Operational Research, 256, 2, 349-367 (2017) · Zbl 1394.90577
[40] Revelle, C.; Hogan, K., The maximum availability location problem, Transportation Science, 23, 3, 192-200 (1989) · Zbl 0681.90036
[41] Revelle, C.; Toregas, C.; Falkson, L., Applications of the location set-covering problem, Geographical Analysis, 8, 1, 65-76 (2010)
[42] Rodrigues, M. O.; Toledo, F. M.B., A clique covering mip model for the irregular strip packing problem, Computers & Operations Research, 87, 221-234 (2017) · Zbl 1391.90391
[43] Sato, A. K.; Martins, T. D.C.; Gomes, A. M.; Tsuzuki, M. D.S. G., Raster penetration map applied to the irregular packing problem, European Journal of Operational Research, 279, 2, 657-671 (2019) · Zbl 1430.90498
[44] Soifer, A., Covering a square of side n + ε with unit squares, Journal of Combinatorial Theory, Series A, 113, 2, 380-383 (2006) · Zbl 1086.52005
[45] Song, D.; Goldberg, K., Exact algorithms for single frame selection on multi-axis satellites, IEEE Transactions on Automation Science and Engineering, 3, 16-28 (2006)
[46] Stoyan, Y. G.; Patsuk, V. N., A method of optimal lattice packing of congruent oriented polygons in the plane, European Journal of Operational Research, 124, 1, 204-216 (2000) · Zbl 0990.90103
[47] Weerasena, L.; Wiecek, M. M., A tolerance function for the multiobjective set covering problem, Optimization Letters, 13, 1, 3-21 (2019) · Zbl 1417.90131
[48] Weerasena, L.; Wiecek, M. M.; Soylu, B., An algorithm for approximating the pareto set of the multiobjective set covering problem, Annals of Operations Research, 248, 1, 493-514 (2017) · Zbl 1357.90126
[49] Xu, Y.; Peng, J.; Wang, W.; Zhu, B., The connected disk covering problem, Journal of Combinatorial Optimization, 35, 2, 538-554 (2018) · Zbl 1393.90105
[50] Zeng, Z.; Yu, X.; He, K.; Huang, W.; Fu, Z., Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container, European Journal of Operational Research, 250, 2, 615-627 (2016) · Zbl 1346.90526
[51] Zhang, Y.; Wang, G., A kind of triangle covering and packing problem, Computational geometry, graphs and applications, 206-213 (2011), Springer: Springer Heidelberg, Berlin, Germany · Zbl 1349.52006
[52] Zhu, W.; Hu, X.; Xia, W.; Sun, H., A three-phase solution method for the scheduling problem of using earth observation satellites to observe polygon requests, Computers & Industrial Engineering, 130, 97-107 (2019)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.