Linearization of Euclidean norm dependent inequalities applied to multibeam satellites design

Abstract : Euclidean norm computations over continuous variables appear naturally in the constraints or in the objective of many problems in the optimization literature, possibly defining non-convex feasible regions or cost functions. When some other variables have discrete domains, it positions the problem in the challenging Mixed Integer Nonlinear Programming (MINLP) class. For any MINLP where the nonlinearity is only present in the form of inequality constraints involving the Euclidean norm, we propose in this article an efficient methodology for linearizing the optimization problem at the cost of entirely controllable approximations even for non convex constraints. They make it possible to rely fully on Mixed Integer Linear Programming and all its strengths. We first empirically compare this linearization approach with a previously proposed linearization approach of the literature on the continuous k-center problem. This methodology is then successfully applied to a critical problem in the telecommunication satellite industry: the optimization of the beam layouts in multibeam satellite systems. We provide a proof of the NP-hardness of this very problem along with experiments on a realistic reference scenario.
Complete list of metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.laas.fr/hal-02066101
Contributor : Laurent Houssin <>
Submitted on : Tuesday, March 19, 2019 - 2:18:02 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Thursday, June 20, 2019 - 12:34:55 PM

Identifiers

Citation

Jean-Thomas Camino, Christian Artigues, Laurent Houssin, Stéphane Mourgues. Linearization of Euclidean norm dependent inequalities applied to multibeam satellites design. Computational Optimization and Applications, Springer Verlag, 2019, 73 (2), pp.679-705. ⟨10.1007/s10589-019-00083-z⟩. ⟨hal-02066101⟩

Share

Metrics

Record views

84

Files downloads

177