Linearization of Euclidean norm dependent inequalities applied to multibeam satellites design

Jean-Thomas Camino, Christian Artigues, Laurent Houssin () and Stéphane Mourgues
Additional contact information
Jean-Thomas Camino: Université de Toulouse, CNRS, UPS
Christian Artigues: Université de Toulouse, CNRS, UPS
Laurent Houssin: Université de Toulouse, CNRS, UPS
Stéphane Mourgues: Airbus Defence and Space, Space Systems, Telecommunication Systems Department

Computational Optimization and Applications, 2019, vol. 73, issue 2, No 11, 679-705

Abstract: 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.

Keywords: Mixed Integer Linear Programming; Mixed Integer Nonlinear Programming; Euclidean norm linearization; k-center problem; Multibeam satellites (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00083-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:73:y:2019:i:2:d:10.1007_s10589-019-00083-z

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00083-z

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().