Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.03942 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.