Back to Search
Start Over
Non-uniform Grid Refinement for the Combinatorial Integral Approximation
- Publication Year :
- 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.
- Subjects :
- Mathematics - Optimization and Control
49M20, 90C11
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2305.12846
- Document Type :
- Working Paper