Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2401.03942 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917685796798464 |
|---|---|
| author | Buchheim, Christoph |
| author_facet | Buchheim, Christoph |
| contents | Extended formulations are an important tool in polyhedral combinatorics. Many combinatorial optimization problems require an exponential number of inequalities when modeled as a linear program in the natural space of variables. However, by adding artificial variables, one can often find a small linear formulation, i.e., one containing a polynomial number of variables and constraints, such that the projection to the original space of variables yields a perfect linear formulation. Motivated by binary optimal control problems with switching constraints, we show that a similar approach can be useful also for optimization problems in function space, in order to model the closed convex hull of feasible controls in a compact way. More specifically, we present small extended formulations for switches with bounded variation and for dwell-time constraints. For general linear switching point constraints, we devise an extended model linearizing the problem, but show that a small extended formulation that is compatible with discretization cannot exist unless P=NP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_03942 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Extended Formulations for Binary Optimal Control Problems Buchheim, Christoph Optimization and Control Extended formulations are an important tool in polyhedral combinatorics. Many combinatorial optimization problems require an exponential number of inequalities when modeled as a linear program in the natural space of variables. However, by adding artificial variables, one can often find a small linear formulation, i.e., one containing a polynomial number of variables and constraints, such that the projection to the original space of variables yields a perfect linear formulation. Motivated by binary optimal control problems with switching constraints, we show that a similar approach can be useful also for optimization problems in function space, in order to model the closed convex hull of feasible controls in a compact way. More specifically, we present small extended formulations for switches with bounded variation and for dwell-time constraints. For general linear switching point constraints, we devise an extended model linearizing the problem, but show that a small extended formulation that is compatible with discretization cannot exist unless P=NP. |
| title | Extended Formulations for Binary Optimal Control Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2401.03942 |