Non-uniform Grid Refinement for the Combinatorial Integral Approximation
From MaRDI portal
Publication:6437448
arXiv2305.12846MaRDI QIDQ6437448FDOQ6437448
Authors: Felix Bestehorn, Christoph Hansknecht, Christian Kirches, Paul Manns 
Publication date: 22 May 2023
Abstract: The combinatorial integral approximation (CIA) is a solution technique for integer optimal control problems. In order to regularize the solutions produced by CIA, one can minimize switching costs in one of its algorithmic steps. This leads to combinatorial optimization problems, which are called switching cost aware rounding problems (SCARP). They can be solved efficiently on one-dimensional domains but no efficient solution algorithms have been found so far for multi-dimensional domains. The CIA problem formulation depends on a discretization grid. We propose to reduce the number of variables and thus improve the computational tractability of SCARP by means of a non-uniform grid refinement strategy. We prove that the grid refinement preserves the approximation properties of the combinatorial integral approximation. Computational results are offered to show that the proposed approach is able to achieve, within a prescribed time limit, smaller duality gaps that does the uniform approach. For several large instances, a dual bound could only be obtained through adaptivity.
This page was built for publication: Non-uniform Grid Refinement for the Combinatorial Integral Approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437448)
