Orientational variable-length strip covering problem: A branch-and-price-based algorithm
Xiaoxuan Hu,
Waiming Zhu,
Huawei Ma,
Bo An,
Yanling Zhi and
Yi Wu
European Journal of Operational Research, 2021, vol. 289, issue 1, 254-269
Abstract:
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.
Keywords: Covering problem; Strip covering problem; EOS scheduling; Dominance rule; Nested grids (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)
Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720306147
Full text for ScienceDirect subscribers only
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:289:y:2021:i:1:p:254-269
DOI: 10.1016/j.ejor.2020.07.003
Access Statistics for this article
European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati
More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().