Wafae, Stéphane Mikael Aurélien

Catherine Chaima

Stanislas, Mamdouh Yu Bruno

Les Stagiaires

Nila Hugo

Anatole Lara

Yue, Haozhe, Henrique Charles

Alexandre, Paul Les Théodore

Post-Doctorants Manon

Les Shabbir

Apprentis Viet-Ha

Khouloud, Maxime, Audrey Marie D Jean

Au cours de ces trois années, j'ai eu la chance d'être accompagné et soutenu par de nombreuses personnes, à qui je souhaite adresser ces quelques lignes. En tout premier lieu, je souhaite remercier Matthieu Chardy pour m'avoir fait confiance deux fois : d'abord pour un stage de fin d'étude et ensuite pour la thèse. Je n'oublierai jamais trois années et demi d'échanges et conseils professionnels et extra professionnels (en ce qui concerne ces derniers, descendre les vallons de la Meije à la Grave est prévu mais supporter une autre équipe que le PSG n'est pas à l'ordre du jour) ponctuées de conférences ensemble dans des villes magnifiques : Bologne avec ses pizzas et ses spritz en terrasse, Avignon et la superbe excursion à Gordes et Sénanque, et Montpellier. Je remercie Adam Ouorou pour ses nombreux conseils et pour sa bonne humeur et sérénité en toute circonstance. Je remercie mon directeur de thèse Michael Poss pour sa disponibilité et pour m'avoir fait découvrir l'optimisation robuste. Avoir pu appliquer ces outils au problème que j'avais à traiter constitue un des accomplissements majeurs de cette thèse. Je remercie ma co-encadrante académique Rosa Figueiredo pour ses conseils tout au long de la thèse et ses relectures exhaustives. Sur un plan personnel, je souhaite également remercier Michael et Rosa pour leur accueil chaleureux à Avignon et leurs invitations à dîner dans leur maison de Montfavet. Je suis très reconnaissant envers Bernard Fortz et Sonia Cafieri d'avoir accepté d'être rapporteurs et les remercie chaleureusement pour leurs relectures attentives et le grand intérêt qu'ils ont porté à mes travaux. Je remercie Sourour Elloumi pour avoir accepté de présider mon jury de thèse, et pour avoir fortement contribué à ma formation en tant que professeur à l'ENSTA Paris et au CNAM. Merci aux autres professeurs de l'ENSTA et du MPRO que j'ai eu plaisir à recroiser en conférence, et en particulier Marie-Christine Costa qui m'a fait découvrir la recherche opérationnelle.

Je remercie Ivana Ljubic pour avoir accepté de faire partie du jury en tant qu'examinatrice.

Résumé Long Introduction

De nouveaux services consommateurs en ressources (notamment le streaming de vidéos) sont apparus dans le marché du mobile au cours des dernières années, provoquant une forte hausse de la consommation moyenne par utilisateur. Ce phénomène, conjugué à une hausse du nombre d'utilisateurs, induit une croissance naturelle du trafic de données mobiles dans le monde. D'après le "Visual Network Index" de la compagnie informatique CISCO [1], celui-ci atteindra 49 exaoctets en 2020 avec un taux de croissance de Lorsque cela est possible, les entreprises de télécommunication doivent satisfaire les demandes de leurs abonnés en vitesse et en volume pour rester compétitives, ce qui demande des investissements réseaux (Orange a ainsi dépensé 5 milliards d'euros pour améliorer dans le monde entier ses réseaux en 2019, voir [START_REF] Orange | Mobile network worlwide activity (orange group webpage)[END_REF]). Faisant face au double besoin d'offrir un service de qualité et de limiter leurs investissements réseaux, les entreprises de télécommunication cherchent ainsi à ne pas sous-/sur-dimensionner leurs réseaux.

Dans de nombreux pays, les entreprises de télécommunication sont à la fois opérateurs de l'infrastructure réseau et fournisseurs de service. En tant qu'opérateurs, elles sont responsables de l'expansion du réseau. En tant que fournisseurs de service, elles conçoivent les offres proposées aux utilisateurs et ont une influence sur l'intensité des usages et donc sur le trafic. Par conséquent, afin d'optimiser la planification de leurs investissements réseau, les entreprises de télécommunication souhaitent comprendre l'appétence des abonnés à migrer vers de nouvelles offres. La planification des investissements réseau peut ainsi bénéficier de décisions d'investissements marketing (incitations financières, telle qu'une réduction sur un téléphone nouvelle génération).

Le progrès rapide des technologies du réseau mobile rend d'autant plus important l'optimisation conjointe des décisions d'investissements réseau et marketing de ces différentes technologies. Cela est illustré par le tableau 2 qui montre l'historique des différentes générations et les débits associés. D'après l'édition 2020 du rapport annuel de la GSM1 (voir [4]), la 4G est devenue en 2019 la technologie dominante en nombre de connexions (plus de 3 milliards par an soit 52 % des connexions). Dans ce rapport, la GSM prédit que la 4G atteindra son pic en 2023, représentant alors 60% des connexions, tandis que la 5G, déjà lancée dans 24 pays, représentera 20 % des connexions en 2025. Cette évolution rapide des générations de réseaux mobiles mène ainsi à une dépendance cyclique entre les dynamiques réseau et marketing, puisque les investissements réseau provoquent plus de changements d'offres d'une génération vers l'autre qui à leur tour conduisent à de nouveaux investissements. 2: Historique des différentes générations de réseau mobile et débits associés (d'après [5]).

En outre, un enjeu important du renouvellement des générations d'un opérateur mobile est la gestion du spectre de fréquences. Le spectre est en effet un actif clef pour l'opérateur, dont les options pour augmenter la quantité de spectre allouée pour une technologie (et donc la capacité du réseau associée) sont limitées: l'opérateur peut acquérir davantage de ressources en fréquences si disponibles ou gérer ses actifs existants en réallouant des fréquences utilisées pour d'anciennes technologies au profit des nouvelles. Ce procédé est nommé "refarming". Établir la pertinence de stratégies de refarming constitue ainsi un levier décisionnel important pour l'opérateur. Ce levier est en lien direct avec la dynamique des abonnés puisqu'un refarming nécessite que le trafic ait diminué sur les anciennes technologies et n'aura d'intérêt que s'il a augmenté sur la nouvelle, et que les investissements marketing peuvent contribuer à ce basculement.

Dans l'optimisation des investissements d'une entreprise de télécommunication, les décisions d'investissements réseau et marketing, et de gestion du spectre, sont ainsi liées et doivent être planifiées conjointement et simultanément. Cette planification est réalisée sur un horizon temporel discret (typiquement un horizon de 5 ans divisé en 5 périodes d'un an). La stratégie des entreprises de télécommunication est alors de prendre les décisions qui minimisent les coûts réseau et marketing tout en respectant le dimensionnement du réseau à chaque période ainsi que des directives stratégiques, qui peuvent être des ambitions fixées par l'entreprise de télécommunication elle-même, dans le but d'assurer sa compétitivité, ou des engagements demandés par une autorité régulatrice. Ces contraintes peuvent être spécifiques à chaque filiale de l'opérateur, chacune ayant une régulation et un contexte marketing propre au pays concerné.

Dans cette thèse, nous considérons des problèmes de stratégies d'investissements dans le domaine du mobile intégrant les décisions d'investissements marketing et réseau et les choix de refarming. C'est la première fois que de tels problèmes intégrant tout cet ensemble de décisions sont traités. Actuellement, les problèmes d'investissements réseau et les stratégies de refarming sont en effet traités uniquement par des scénarios définis et paramétrés à la main dans des tableurs sans prendre en compte les décisions marketing. Pour modéliser et résoudre la problématique complète, nous nous appuyons sur l'optimisation combinatoire dont les méthodes vont permettre de trouver efficacement les meilleures décisions. En outre, grâce à la flexibilité de la programmation linéaire, les modèles s'adaptent facilement à la situation de chaque filiale d'une entreprise de télécommunication telle qu'Orange en ajoutant des contraintes ou en fixant des décisions imposées par des facteurs extérieurs (tel qu'un refarming décidé par le régulateur).

Plus précisément, nous étudions en premier lieu un problème d'investissements marketing et réseau, dans un cas réduit à deux générations. Ce problème de référence est ensuite étendu au contexte au cas de trois générations ou plus et à l'intégration des décisions de refarming. Pour chaque problème résultant, nous élaborons des méthodes de résolution basées sur des programmes linéaires en nombres entiers (PLNE), renforcées par des inégalités valides, ainsi que des algorithmes de résolution approchés (heuristiques) pour résoudre les grandes instances. Afin de prendre en considération l'aspect incertain de l'effet des décisions marketing, nous proposons et résolvons une version robuste du problème à deux périodes et deux générations. En mettant en oeuvre les différentes méthodes de résolution développées, nous conduisons des études de cas sur des instances réelles répondant à des questions stratégiques pour Orange. Enfin, un outil d'aide à la décision, ayant pour but de visualiser les décisions prises et l'état du réseau correspondant, a été réalisé.

Nous présentons, dans ce qui suit, un résumé du contenu de chaque chapitre.

Mobile investments strategies context

Dans ce chapitre, nous présentons d'abord l'évolution des technologies réseau de la 2G jusqu'à l'arrivée actuelle de la 5G, puis nous détaillons les différentes problématiques que se pose un opérateur de télécommunication lorsqu'il planifie ses réseaux mobiles à long terme. En particulier, nous présentons dans ce chapitre trois dynamiques que l'opérateur doit gérer: la dynamique des investissements réseaux, la dynamique des investissements marketing et la gestion du spectre des fréquences, ainsi que trois aspects moteurs dans la planification de ces dynamiques: la minimisation des coûts, les directives stratégiques et le dimensionnement du réseau.

The Mobile Investments Strategies problem

Ce chapitre traite du problème de la planification optimale des stratégies d'investissements mobile avec deux générations de réseau. Dans ce problème l'opérateur doit minimiser les investissements réseau et marketing tout en respectant des contraintes de capacité chaque année et des ambitions stratégiques de couverture et de qualité d'expérience à la fin de l'horizon temporel. Les leviers décisionnels pour l'opérateur sont les investissements réseau (installation de la nouvelle génération sur les sites existants et augmentation de la capacité pour les deux générations) et marketing (incitation financière pour migrer vers les offres correspondant à la nouvelle génération de réseau). En premier lieu, le problème est formalisé mathématiquement et modélisé sous forme de programme en nombres entiers. La fonction de migration des utilisateurs est ensuite modélisée et la formulation est linéarisée afin d'obtenir un programme linéaire en nombres entiers (PLNE). Cette modélisation est ensuite renforcée par des inégalités valides spécifiques au problème de planification optimale des réseaux mobiles. Enfin, le modèle ainsi que les inégalités valides sont évalués numériquement sur des instances réelles 3G/4G correspondant à un territoire français composé des régions Bretagne et Pays-de-Loire. Les tests algorithmiques montrent l'importance des inégalités valides pour la résolution du problème. Les tests métiers permettent d'évaluer l'impact de différents paramètres (fonction de migration, couverture initiale de la nouvelle technologie...) ainsi que de contraintes additionnelles telles que l'équilibre des coûts.

Practical variants for the Mobile Investments Strategies problem

Le problème traité au chapitre précédent permet de répondre au contexte de déploiement d'une nouvelle technologie sur des sites existants. Dans ce chapitre, nous étendons les hypothèses afin de pouvoir répondre à différentes questions clefs que l'opérateur peut se poser. Les différentes variantes traitées sont l'extension du problème à trois générations de réseau ou plus, la prise en compte des recouvrements de couverture et de l'installation de nouveaux sites et l'intégration des stratégies de refarming. Une modélisation sous forme de PLNE est proposée pour chacun de ces problèmes. Ces différents modèles sont évalués numériquement à travers trois études de cas.

Heuristics algorithms for mobile investments strategies problem

Les chapitres précédents montrent la difficulté des formulations PLNE pour résoudre nos problèmes sur les instances les plus grandes (de la taille d'un pays). Nous proposons donc dans ce chapitre des méthodes approchées (méta heuristiques). Ces méthodes sont basées sur une décomposition du problème selon la réaction des utilisateurs. Le principe de l'algorithme est le suivant: sélectionner une réaction des utilisateurs à tester puis résoudre le problème à réaction des utilisateurs fixée. Afin de sélectionner les réactions des utilisateurs à tester, nous proposons deux méthodes : une heuristique basée sur un algorithme de recherche à voisinage variable, et une énumération partielle.

Nous proposons des PLNE pour résoudre le problème à réaction fixée. Pour le problème à deux générations (Chapitre 3), dans le cas où il n'y a pas d'équilibre des coûts et où les installations réseau sont effectuées à la première période, une transformation du problème en un problème du sac à dos a été proposée et le problème peut ainsi être résolu par programmation dynamique.

Pour le problème avec équilibre des coûts, ainsi que pour les variantes du chapitre précédent, nous proposons, pour les grandes instances, une heuristique de décomposition par sites. Nous évaluons ensuite ces différentes heuristiques sur des instances de grande taille : instances réelles de l'ordre de 1000 sites et simulées de l'ordre de 12000 sites.

Robust framework

Ce chapitre traite du "Mobile Investments Strategies problem" (introduit au chapitre 3) en contexte incertain, sur un cas réduit à deux périodes. L'incertitude considérée porte sur la réaction des utilisateurs aux incitations financières. Premièrement, un modèle n'utilisant que des variables entières et binaires est proposé pour traiter ce cas en contexte déterministe. Deux modèles d'optimisation robuste ont ensuite été élaborés: le premier est statique et le second permet d'ajuster la décision de seconde étape aux différentes décisions prises. Ces modèles sont ensuite utilisés pour tester l'impact de l'incertitude. Deux types de coûts sont alors considérés: les coûts classiques et "les coûts de premier niveau". Ces derniers sont obtenus en prenant la solution de premier niveau fournie par les différents modèles, puis en testant un modèle statique dans lequel cette décision de premier niveau est fixée et la réaction incertaine est échantillonnée.

Conclusion

Nous avons introduit dans cette thèse plusieurs problèmes d'optimisation auxquels est confrontée une entreprise de télécommunication qui veut optimiser la planification de ses investissements.

Des méthodes exactes et approchées ont été proposées pour la résolution de chaque problème.

Ces méthodes permettent de répondre à des questions clefs pour Orange, comme illustré par les différentes études de cas présentées. Un prototype d'aide à la décision a été conçu lors de cette thèse; il permet aux décideurs de lancer une optimisation, de récupérer les résultats et d'analyser ceux-ci grâce à des visualisations graphiques. Nous identifions deux perspectives pour ce travail. La première concerne le traitement de la concurrence entre les opérateurs par des méthodes de théorie des jeux. La deuxième concerne le déploiement opérationel des algorithmes développées.

Chapter 1

Introduction

Over the last few years, new bandwidth-consuming services such as video streaming have appeared (see Table 3), strongly increasing the average monthly consumption by user, known as Average Usage per User. This phenomenon, correlated with an increase in the number of users, induces a natural traffic growth in mobile networks. According to the Visual Networking Index of the IT and network company CISCO [1], the traffic will globally reach 49 Exabytes per month in 2020 with a compound annual growth rate of 47%, this growth being particularly important in Africa (65%). Network expansion is necessary to support such traffic growth. Whenever possible, telecommunication companies must hence satisfy the request of subscribers in speed and volume to remain competitive, which requires network investments (for instance, Orange has spent five billion e to improve its networks worldwide in 2019, see [START_REF] Orange | Mobile network worlwide activity (orange group webpage)[END_REF]). Facing both needs of offering a satisfying service and of limiting their network investments, telecommunication companies do not want to under-/over-dimension their mobile networks.

In many countries, telecommunication companies are both infrastructure operators and service providers. As infrastructure operators, they are responsible for planning their network expansion. As service providers, they design the subscriptions proposed to the users and have an influence on network traffic. Thus, telecommunication companies wish to understand the willingness of subscribers to shift to a new technology in order to optimally plan the investments in new mobile generations. Network investments planning could hence benefit from marketing investments (financial subsidies, such as cost reduction on a phone having access to the newest generation).

Considering jointly the network and marketing investments decisions for all generations together is even more important due to the fast progress of mobile technology. This is illustrated in Table 4 that shows the speed increase through mobile generations. According to the 2020 annual report of the GSM 1 Association (see [4] for the detailed report), 4G has become in 2019 the leading mobile network technology worldwide by number of connections (more than 3 billion and 52% of the total number of connections). In this report, the GSM Association forecasts that 4G technology will peak at 60% of connections in 2023, while 5G, already launched in 24 countries, will account for 20% of connections in 2025. This fast evolution of mobile generations leads to a 1 GSM Association is an originally-European trade body that represents the interests of mobile network operators worldwide.

cyclic dependency between the subscriber and the network dynamics as investments in the network promote a shift in subscriptions which in turn leads to new investments. 4: Evolution of speed through mobile generations (from [5]).

Besides, key stakes in mobile network evolution also lie in the management of the spectrum of frequencies. Spectrum is indeed a key asset for telecommunication companies, which have limited options to increase the quantity of spectrum allocated to a mobile network technology (and thus the associated network capacity): they can either obtain new spectrum when it is available or manage their current spectrum holding by reallocating frequencies used for older mobile technologies to newest ones. Such process is called refarming. Assessing the relevance of refarming strategies is hence an important decisional lever for the telecommunication companies. This lever is directly linked with the subscriber dynamic, since reallocating bands used for older technology to the newest one requires that the traffic has been reduced on older technologies and will be performed only if it increased on the newest one, a shift that marketing subsidies can help to achieve.

In the optimization of the mobile investments of a telecommunication company, the decisions on network investments, marketing investments and refarming strategies are hence intertwined and should be planned jointly. This planning is performed on a discrete time horizon (typically, five years divided in five periods of one year).

Over this time horizon, the telecommunication companies' strategy should take the decisions which minimize the network and marketing investments costs while respecting network dimensioning at each period and strategic guidelines, which can be ambitions fixed by the telecommunication companies themselves in order to ensure their competitiveness, or external requirements from regulator entities. Such constraints can be specific to each affiliate, each facing the regulation and the marketing context of its own country.

In this thesis, we study mobile investments strategies problems, jointly optimizing network, marketing and spectrum decisions. This is the first time such problems encompassing all decisions taken by a telecommunication company are considered. Currently, network investments and refarming strategies are indeed only treated with handly customized scenarios in spreadsheets, which do not consider the marketing decisions. For modeling and solving the mobile investments strategies problems, we rely on combinatorial optimization, whose methods enable us to find efficiently the best decisions for the whole problem. Besides, thanks to the flexibility of mixed integer programming, the designed models easily adapt to the situation of each affiliate of a telecommunication company such as Orange by adding constraints or fixing decisions which are driven by external factors (for instance, a refarming imposed by the regulator).

More precisely, this thesis considers first a Mobile Investments Strategies (MIS) problem for marketing and network investments decisions, in a two-generation case. This reference framework is then extended to the more-than-two generation context and to the integration of the refarming decisions. For each of the resulting problems, we design exact solving methods based on mixed integer linear formulations, reinforced by valid inequalities, as well as approximate solving methods (heuristic algorithms) for large instances. In order to take into account the uncertain aspect of the marketing decision's effect, we propose and solve a robust framework for the two-period mobile investments strategies problem. Using these different methods, we conduct several experimental case-studies on real-life instances to answer strategic questions for Orange Labs. Finally, we design a decision-aid tool aiming to visualize the investments decisions and the resulting network throughout the planning time horizon.

The remainder of this dissertation is organized as follows: Chapter 2 provides some insights on telecommunication companies' strategies and constraints when planning their investments in mo-bile networks. This chapter also includes a state-of-the-art on mathematical models for optimizing mobile investments and a list of the problems tackled throughout the thesis. The MIS problem is introduced, modeled, reinforced with valid inequalities and solved in Chapter 3. In Chapter 4, we introduce and model the mobile investments strategies problem with more than two generations, as well as the problem with refarming strategies. The solving of the aforementioned problems on large instances, through heuristic methods, is tackled in Chapter 5. A study on the uncertainty of the subscriber dynamic is performed through the lens of robust optimization on a two-period framework, in Chapter 6. Finally, in Chapter 7, we synthesize our contributions, describe briefly the decision-aid tool and derive some perspectives.

Chapter 2

Mobile investments strategies context

This chapter provides some insights into the problem faced by an operator trying to plan its investments in mobile networks. Throughout the manuscript, we consider a telecommunication company in countries where it provides telecommunication services to subscribers served by its own networks. We hence exclude Mobile Network Virtual Operator for considering only Mobile Network Operators (MNO). In particular, we study the following six levers in the strategy of a MNO:

• three dynamics:

network dynamic investments, subscribers dynamic: investments for shifting technologies, spectrum management: reallocation of frequencies from oldest technologies to more recent ones,

• three driving aspects for these dynamics:

costs (network and marketing investments) to minimize, strategic guidelines to satisfy, capacity dimensioning to satisfy.

The remainder of the chapter is organized as follows. Section 2.1 sums up the evolution (past and forecast) of mobile technologies. Details on the different network investments that can be decided by the telecommunication company are tackled in Section 2.2. Section 2.3 presents ways for the company to manage its subscriber pool. Section 2.4 presents different hypotheses and policies for the way subscribers are served by the network. In Section 2.5, we describe the stakes involved in the spectrum market and the operator levers on this market. Section 2.6 refers to strategic network guidelines. In Section 2.7, we give some insights into the types of costs used. Finally, we review some mathematical models answering partially to these different problems in Section 2.8 and list the problems tackled throughout the thesis in Section 2.9.

Past and recent evolutions/breakthrough in mobile networks

The sector of telecommunications is in perpetual evolution. A brief history of mobile technologies is provided in Section 2. For details on the technological enhancements, which have allowed such performances, the reader can refer to the releases of the 3GPP ( [START_REF]3G specifications[END_REF]). 3GPP is a standard organization created for preparing 3G, which has accompanied the arrivals of 3G and 4G technologies, and whose last releases are now dedicated to 5G. In what concerns 4G arrival, the reader can also refer to the following book [START_REF] Holma | LTE Advanced: 3GPP Solution for IMT-Advanced[END_REF] which illustrates the technological innovations defined in such releases.

5G: a change of paradigm

The growth of traffic and the move towards an ever more connected world led, soon after the commercial launch of LTE technologies (4G), to an identification of what future networks (5G) should bring (see, among others, [START_REF] Andrews | What will 5G be?[END_REF] and [START_REF] Osseiran | Scenarios for 5G mobile and wireless communications: the vision of the METIS project[END_REF]).

Three services (see [10]) were hence identified. First, the mMTC (massive Machine-Type Communications) has for aim to connect a huge number of devices in what is called the IoT, Internet of Things, sometimes becoming IoE (Internet of Everything) -see [11]. These massive data exchanges between devices have many applications in health, transport, agriculture (see [12]). In some of these applications, low latency communications are critical (see [13]). One of the typical examples of use-case requiring low latency is the example of intelligent transportation systems, in particular a smart city where autonomous cars are adapted accordingly to traffic lights and congestion. Latency is hence the objective of the second service ( [10]): Ultra-Reliable Low Latency Communications (URLLC). The current performances of mobile networks are around 50 ms. The latency requirements for URLLC are 1 ms ( [14]). Finally, eMBB (Enhanced Mobile Broadband) stands for the improvement of current mobile performances (faster connections, higher throughput, and more capacity) as was 4G for 3G networks. Commercial labels for 5G nowadays correspond to the providing of eMBB services. Technological achievements of the requirements for URLLC and mMTC are not forecast before 2025. Providing these services requires indeed an important change of paradigm ( [15]). Details on technological evolutions can be found on 3GPP releases or in [16].

Change of view of old generations : decommissioning

These four generations will coexist in many operators' networks and have led to thinkings about the future of 2G and 3G generations.

Important disparities of the situations between regions are underlined in the last report from GSMA (see [4]). Data from this report for the three regions (stored under Column "Region") in which Orange company is mainly implemented -Europa, Middle East and Africa -, as well as for North America and worldwide in comparison, are provided in Table 5. Data is available for two years, values observed in the last year (2019), and forecast values for year 2025.

For each region, we provide the division (in percentage) of the connections between the different technologies (stored under "% of the total connections") as well the percentage of unique mobile subscribers among the total population (stored under column " penetration rate"). Table 5: Current and forecast % of the total connections according to the different technology and mobile market penetration rate -data from [4] We observe that in North America, the number of connections has already dropped to 18%, while such connections represent still 42% of the connections in Europe, 71 % in Middle East North Africa and 90% in Sub Saharan Africa. In 2025, Europa should join North America in this decrease, with 2G/3G accounting for 7/8%. It will still account for 46% of the connections in Middle East North Africa, and 70% in Sub Saharan Africa. In conclusion, the different regions do not face the same situation in front of market, which leads to different strategies.

The main reason for decommissioning (removing) the oldest network technologies is to liberate frequency spectrum resources in order to have more spectrum for the newest ones, see Section 2.5. Old technologies could also be less efficient energetically and they rely on obsolescent pieces of equipment. Decommissioning such technologies hence brings to the telecommunication company important savings on the OPEX -operational expenditures -(rationalization of means, no more intervention on oldest networks required).

However, removing previous mobile generations is not easy and has to be planned carefully. These networks are still used indeed for some usages, especially machine to machine communications, requiring very few data transfers and cheap links. In some countries, 2G networks are also used for police communications. In most of the world, the plan is to decommission 2G technology first. The pioneers in the 2G shutdown are the Asian and American operators (see [17]). For instance, A T & T shut down its 2G network at the beginning of 2017 (see [START_REF]2G sunset (from A T & T)[END_REF]) and plans to shut 3G networks down around 2022 (see [START_REF]A T & T gives 3G service three years to live[END_REF]). Other American operators plan the shutdown of 2G and 3G technologies nearly simultaneously (around 2020). In Europa and Africa, the use of 2G for M2M leads operators to think of decommissioning 3G before 2G. The full shutdown of 2G and 3G technologies is not envisaged by Orange in its different affiliates before 2025. In its "Legacy-mobile-network-rationalisation on Asia markets" report [17], the GSMA details what are the decisions on the matter taken in different Asian countries. This report enlightens the multiplicity of situations. Sometimes, the shutdown is regulator driven and the operator has to follow what has been decided. In other cases, each operator has each own refarming policy, which becomes hence a new decision lever.

Network investments

To handle the traffic demand, telecommunication companies have to invest in the networks. We consider in this thesis three types of network investments:

• increasing the capacity of an already installed technology,

• installing a new technology on an existing site,

• installing a new site.

We detail successively these three types of investments in Sections 2.2.1, 2.2.2 and 2.2.3.

Increasing capacity on sites

For each technology installed on a site, capacity can be increased. 2G capacity can be increased by the addition of a transceiver (TRX), while 3G, 4G (and 5G) capacity are increased by the increase of the spectrum bandwidth used (multiple of 5 MHz). The way capacity is increased hence depends on the technology but this increase of capacity is always modular. Throughout the manuscript, a module will denote the smallest capacity that can be installed. An associated capacity value, in Mbps, is provided for each generation, corresponding to the capacity obtained with one module, as well as an associated cost. The increase of capacity through bandwidth is hence assumed to be linear (cost and capacity both proportional to the number of modules installed). This smallest unit is 5 MHz for 2G and 3G. For 4G, 5 or 10 MHz are used depending on the considered countries. This increase is limited on each site by the maximal spectrum that can be allocated. In models without spectrum dynamic, a maximal value for the number of modules installed is introduced for representing such limitations.

Installing a new technology on existing sites

Installing a new technology is another lever to reduce congestion in the network, as the subscribers which have compatible devices will be served by the newest technology instead of the saturated older ones.

When planning the installation of a new technology, the operator often decides to plan it on existing sites as mentioned in [20]. Using existing sites avoids civil engineering costs of pylons implementation, backhaul (connection of the site to the reminder of the network ) and electricity links. Still, adding a new technology on an existing site involves important operations and notably the replacement of the technical equipment of the base station, which is called NodeB for UMTS/3G, eNodeB for LTE/4G, and gNodeB for 5G.

Installing a new site

Densification refers to the installation of sites in already covered areas for increasing the capacity in this area. Due to the costs associated with a new site, this solution is used only when investments in existing sites are not sufficient to handle the traffic.

Besides, two other contexts arise when considering new sites. First, sites are installed for extending coverage. This enables the telecommunication company to provide access to telecommunication services to people who were beyond the coverage range. Second, 5G arrival comes with the development of millimiter waves use and the migration from a macro-cell network to a multi-scaled cell network (see Figure 1). Some of the frequencies used for 5G are indeed of very low range (see Table 6 as well as [21] for more details) and thus push to use microcell networks, where small relay antennas are used in addition to a bigger antenna. The microcell networks sites will be cheaper but will be far more numerous in order to cover the whole territory. These considerations drive us to add the possibility of building new sites.

Subscribers levers

In parallel to the investments on networks, telecommunication companies have also leverage on the subscribers' offers. In this section, we consider the evolution of the number of subscribers. macro cells of existing current generation sites micro cells of future new generation sites Figure 1: Illustration of a multi-scaled network.

Section 2.3.1 considers competitiveness and incoming subscribers. In Section 2.3.2, we detail the different types of financial incentives that can be performed by the telecommunication company. Section 2.3.3 presents the diffusion of innovation models used.

Competitiveness and incoming subscribers

The number of new subscribers is difficult to forecast with precision. It is linked with competitiveness and depends on the other operators deployments.

In this thesis, we handle two cases:

• the case where we focus on the management of current subscribers pool, with a total number of subscribers fixed

• the case where the increase of the number of subscribers for each generation is known.

Subsidy incentive for driving subscribers to shift to the newest technology

For having access to the newest technology, a subscriber has to change of device since his/her older device will suffer from technical incompatibilities. To increase the number of subscribers who shift, the operator can hence perform incentives for the subscribers to shift. It is important to notice that what is modeled by subsidies here is the amount of money spent in marketing incentive pro user who shifts. The easiest example to illustrate what is behind this amount is saving coupons on new devices such as "100 euros for buying the next iPhone". However, other marketing expenses can occur behind this amount. Examples can be found in the case studies presented by the GSMA in the report [17], such as:

• savings on the new subscriptions: for instance, exemption from 3G subscription fees for the first three months followed by discounted rates for two years for KT operator in South Korea,

• refund when returning an old device: for instance, payment of KRW33,000 (USD27) for a returned 2G device for KT operator in South Korea,

• loyalty points and air miles (also in KT example),

• lessons for the elderly to increase the use of smartphones (see example from Singapore).

Adopting a new technology: diffusion of innovation models

To model the effect of these subsidy proposals, we rely on the well-known Bass model from the marketing literature.

First studies on diffusion of innovation and new products appeared in the 60's, in a period of high economic growth and important innovations (television, for instance). Everett Rogers published the diffusion of innovation theory in 1962 (see [22]), based on the adoption curve of Figure 2. This curve presents the percentage of subscribers who adopt a new product during the time horizon. The curve assumes that the timing of a consumer's initial purchase is related to the number of previous buyers (imitation part) and enlightens different types of subscribers. The innovators are the easiest to convince and the laggards are those who adopt the last. External factors (marketing and attractiveness) due to decisions taken in the time horizon are not taken into account, as well as the generation effect (new generation replacing an older one).

No subsidies 10% savings on the price each year 20% savings on the price each year time Upgrading Customer (in %)

Figure 2: Curve of the diffusion of innovation and influence of subsidies In 1969, Bass formalized Rogers' model by using differential equations and later developed it to tackle some of the issues with external variables (see [23]) and generations (see [24]). This work considers marketing aspects by showing a left shift on the shape of adoption curves when regular savings (equivalent to constant subsidies) on the price of a product are made, as illustrated in Figure 2. These models help the understanding of how subscribers react in a telecommunication market: see Section 5 in [25] for a discussion on 2G/3G upgrade; [26] for Bass model applied to the forecasting of the 5G upgrade; and [START_REF] Michalakelis | Diffusion models of mobile telephony in Greece[END_REF] for an application to the Greek mobile market.

To adapt this formalism to the current telecommunication context, we consider two important factors for modeling the adoption of a new technology, described hereafter by function f . First, the percentage of subscribers shifting from older technologies is very sensitive to the price gap between the new technology and their current one, which will be referred to as σ. The second factor is the influence of network deployment (denoted c). Indeed, subscribers upgrade more easily when they are sure to benefit from the new service, i.e. if the newest technology is deployed. In multi-generation frameworks, we will also test shifting function with a dependency on a third parameter: the current offers of the subscribers. This assumption enables indeed to model contexts in which subscribers to specific offers have to be targeted (for example 2G subscribers in case of 2G shutdown).

2.4 Link between network and subscribers: how are the subscribers served ?

We have just seen that the reaction of subscribers can depend on the level of deployment of the network. Inversely, the operator wants to avoid over-dimensioning of the network. Several questions about the way subscribers are served are explored in this section. In particular, Section 2.4.1 tackles network dimensioning while Section 2.4.2 discusses on subscribers mobility. Section 2.4.3 presents the benefit of taking into account overlappings, while Section 2.4.4 tackles the different strategies for deciding which generations are served by which sites.

Network dimensioning in long term planning

The dimensioning on each site is performed through the 95th percentile method, assuming that 5% of daily traffic happens during the twenty-two peak hours of the month. These demands are hence forecast Average Usage per User, converted in traffic demand by usual dimensioning rules (see [START_REF] Holma | LTE Advanced: 3GPP Solution for IMT-Advanced[END_REF]). The subscribers considered are equivalent subscribers, which all have the average demand.

Question of mobility in networks planning

The subsidies considered in this section are not geographically targeted. As mentioned, subscribers considered are used for dimensioning. Let us treat the following example. A subscriber has an offer of X GO by month, corresponding to the average demand and consumes the integrality of this offer. Let us assume that this subscriber is served by three sites: 80% of the traffic on site A, 10% of the traffic on site B, and 10% of the traffic on site C.

We will see in our modeling based on equivalent subscribers, this subscriber as 0.8 subscriber on site A, 0.1 subscriber on site B and 0.1 subscriber on site C. Its contribution to the dimensioning trafic is hence assessed, while this subscriber will be taken into account correctly as 1 subscriber in the subscribers dynamic. This reasoning works if the subscribers have demands close to the average demand. This issue can be tackled by considering several offers for a given technology differentiating by the demand (low consumption, high consumption, etc.), but this requires availability of marketing data, to distinguish which part of the traffic is due to which category of subscribers, in order to subside accordingly. This explains why the number of subscribers will be considered continuous and how mobility is naturally taken into account. In first approximation, each telecommunication site is associated with its own pool of subscribers, which assumes that there is no overlapping between sites coverage. This assumption leads to over-dimensioning since overlapping exists in real networks and hence a technology installed on a neighbor site could have been sufficient to serve the subscribers, see Figure 3.

Taking into account overlappings

Load balancing policies

For each offer, the operator has to decide which network technologies should serve the corresponding subscribers. This choice has to be made among compatible technologies. The motivation for such policies is often quality of experience, to serve subscribers by the more recent technologies and hence provide them with the best possible performances. However, such decisions can also saturate some technologies by driving all the traffic to them.

Spectrum and refarming plan strategies

As mentioned, communications in mobile networks require spectrum bandwidth. The way of managing its spectrum resources is hence a key stake for telecommunication companies. Section 2.5.1 defines the spectrum holding. Section 2.5.2 presents the possibilities of using new bands for deploying telecommunication services. Two key mechanisms arise for the operator when considering spectrum:

• acquiring more spectrum through auctions,

• managing its current spectrum holding.

The process for valorizing and acquiring spectrum is tackled in Section 2.5.3 while the management of the current spectrum holding is treated in Section 2.5.4.

Spectrum holdings

Spectrum resources are considered in most countries as exclusive properties of the state and using such resources is hence regulated. The spectrum available for telecommunication services is divided into frequency bands. Each operator has bandwidth holding on some or all these frequency bands. We provide in Table 7 current values of this holding for the four French operators on the 6 available frequency bands which are 700, 800, 900, 1800, 2100 and 2600 MHz. Increasing the network capacity with a module for a given network technology (see Section 2.2) is directly linked to a discrete increase of the bandwidth of the frequency band used, and is hence limited by the sprectrum allocated to this technology, itself limited by the total spectrum holding of the operator.

New bands possibilities

With the arrival of new technologies, the possibility also appears for the telecommunication companies to use frequency bands that were previously used for other services. This is the case for 4G with bands 700, 800 and 2600 MHz. In Europa, the decision of using the 700 MHz band has been taken at the European level (see [START_REF]European decision on using 700 MhZ band for telecommunications[END_REF]). Similarly, 5G arrival is associated with new uses on frequencies bands. For the moment in Europe, the focus is on band 3400 MHz. In France, the auctions for such bands have started in 2020.

The fact that 4G (and now 5G) have new bands on both sides on the spectrum (smaller and greater frequencies than before) is explained by the physical properties of the spectrum, these bands being used for different usages. Low frequency bands have very good coverage and penetration, while high frequency bands (millimeter waves) have low penetration in building and weak coverage, but are used for eMBB service, as it provides high debit performances.

Auction process for new bands attribution or more spectrum on existing frequency bands

The way these new bands are attributed to mobile operators depends on the countries. Since 1990, a consensus [START_REF] Mcmillan | Why auction the spectrum?[END_REF] raised by both economical theory and experiences has led to the use of auctions for allocation mechanism (see [START_REF] Kuroda | The effects of spectrum allocation mechanisms on market outcomes: Auctions vs beauty contests[END_REF] and [START_REF]Spectrum allocations best practices[END_REF]). New mechanisms are also in development such as the Licence Shared Access (LSA) mechanism, which will enable the operator to use, during predefined time slots, spectrum resources that are owned and unused during the timeslot by another incumbent (for instance, the army). Auctions are also designed for such mechanisms (see [START_REF] Chouayakh | PAM: A fair and truthful mechanism for 5G dynamic spectrum allocation[END_REF]).

To participate in the auctions for demanding more bandwidth, telecommunications have to assess correctly their spectrum valuation. A correct valuation enables indeed to bid efficiently. Several valuation methods have been proposed in the literature (see among others [START_REF] Bazelon | Spectrum value[END_REF] and [START_REF]Methodologies for valuation of spectrum[END_REF] ). In this thesis, we do not model this acquiring of new spectrum resources as a decisional lever and consider hence the spectrum situation as an input. Testing two different inputs (one with a new band, and the other without) enables the telecommunication company to valuate spectrum and hence helps it to take such strategic decisions.

How to manage its current spectrum holding

When a telecommunication company requires more spectrum, and no auctions are available, another possibility for the company is to modify the way its spectrum holding is allocated to its different mobile generations. Spectrum no longer used for a given technology can hence be reused by the operator for the newest technology. Part of refarming strategies are sometimes already fixed by the regulator or by strategies explained by factors not considered here (regulator decisions, operational expenditures).

Due to the importance of IoT communications, neither 2G nor 3G shutdowns have been planned for the moment in Orange's market, and it has been decided to keep 5 MHz for both technologies on bands called "legacy bands".

For these reasons, we will look in this thesis at two cases, enabling to answer different strategic questions:

• The operator has to elaborate a refarming plan (deciding which bands or parts of bands are allocated to which technologies).

• The operator wants to assess and compare pre-determined refarming strategies.

The different questions that can be answered by comparing scenarios for refarming strategies are:

• on which bands to deploy the new technology and when,

• from which technology to withdraw resources and when,

• which bands to keep as legacy bands and how many spectrum blocks on these bands,

• whether to proceed refarming on an intermediate technology and then the new technology (e.g. 2G → 3G → 4G) or to reallocate frequencies directly to the new technology (e.g. 2G → 4G).

Key strategic guidelines and regulator requirements

There are several types of guidelines that are driving networks evolution. We illustrate them on the example of the French network. In the French telecommunication context, the regulator is the quango ARCEP. The ARCEP publishes yearly ranking of the operator performances and is also responsible for the spectrum evolution (3.4 GHz band attribution procedure in France).

Yearly rankings

In yearly rankings, such as [START_REF] Arcep | ARCEP rankings[END_REF], operators are ranked according to their performances. These performances are assessed in different types of areas (urban, suburban, rural) and with different criteria focused on user experience (debit, latency). Such rankings have pushed the operators to fix themselves strategic guidelines in terms of debit and coverage to be competitive.

Attribution procedure for 5G 3,4 GHz band

The ARCEP organizes the auctions of the [3,4 -3,8] GHz band (see [START_REF]Procedure and conditions for the allocation of core 5G (3.4 -3.8 GHz band) frequencies[END_REF] for details on the auction procedure). To participate in these auctions, which take place in September 2020, French telecommunication operators are asked to take several commitments:

• deploying their network in "white zones" (areas which are currently not covered);

• installing the new band on sites;

• guaranteeing a debit.

Conclusion

The strategic guidelines we consider throughout can hence be either strategic guidelines fixed by the operator to be competitive in rankings or direct commitments from the operator taken in order to obtain spectrum resources from the regulator.

Costs assessments and forecasts

The costs in our study do not vary over the time horizon. This is because the costs are real costs from equipment sellers. The prices are contracted with these suppliers for a period equivalent to the planning time horizon that we consider (5 years).

Mathematical models for optimizing mobile investments

In this work, we are interested in optimizing, over a time horizon, investment decisions related to network expansion and subscriber dynamics assuming the arrival of new technology. Such problems have been treated in the literature but with a focus on network investments. Capacity expansion problems in telecommunication networks have been studied for a long time in the integer programming community, see [START_REF] Knippel | The multi-layered network design problem[END_REF][START_REF] Gollowitzer | Enhanced formulations and branch-and-cut for the two level network design problem with transition facilities[END_REF] among many others, including the case of multiperiod planning [START_REF] Garcia | Iterative improvement methods for a multiperiod network design problem[END_REF][START_REF] Gendreau | Multi-period capacity expansion for a local access telecommunications network[END_REF][START_REF] Kubat | A multi-period network design problem for cellular telecommunication systems[END_REF]. The authors in [START_REF] Duan | Economic analysis of 4G network upgrade[END_REF] use game theory to look for network upgrade decisions with an objective of revenue maximization in a competitive environment. In [START_REF] Oughton | The cost, coverage and rollout implications of 5G infrastructure in Britain[END_REF], the authors evaluate the cost of different strategies for 5G deployment in Great Britain.

Closer to the context of mobile capacity expansion, the authors of [START_REF] Chardy | 3G/4G load-balancing optimization for mobile network planning[END_REF] present an exact mixedinteger formulation and a heuristic method to compute mobile investments strategies in a restrictive framework. These models integrate the upgrade of subscribers thanks to subsidies. However, a limitation of the models studied in [START_REF] Chardy | 3G/4G load-balancing optimization for mobile network planning[END_REF] is that the amount of subsidy offered to users is fixed and the number of users which upgrade is set as a variable, constrained only to be positive and upper bounded by the total number of users. The possibility of offering subsidies to increase user upgrades is hence not taken into account. In [26], the authors consider the transition of a generation to another, but from a subscriber migration point of view only, applied for a South Korean network.

Problems tackled

The context of mobile investments strategies and the different decisional levers for the operator presented throughout this chapter lead us in the following to tackle:

• The problem MIS, introduced in Chapter 3. This problem deals with a two generation framework and focuses on the arrival of a new generation on existing sites. It integrates three investments decision :

increasing the capacity of an already installed technology (described in Section 2.2.1),

installing a new technology on an existing site, (described in Section 2.2.2),

making the subscriber shift to the current technology to the newest one thanks to subsidies, with a shifting function designed as discussed in Section 2.3.

• The problem MG-MIS, introduced in Chapter 4. This problem extends the MIS problem to the more-than-two generation context.

• The problem GEO-MIS, introduced in Chapter 4. It enables to take into account sites coverage overlapping (see Section 2.4.3) and new sites installation (see Section 2.2.3)

• The problem R-MG-MIS, introduced in Chapter 4. This problem integrates the refarming strategies that we have described in Section 2.5.

The uncertain and empiric aspect of the shifting function (see Section 2.3) drives us to consider robust versions of the MIS problem, which will be tackled in Chapter 6.

Chapter 3

The Mobile Investments Strategies problem

Introduction

The problem tackled in this chapter is a Mobile Investments Strategies (MIS) problem for two generations. It consists in optimizing subscribers and network dynamics subject to capacity and strategic guidelines constraints for two network technologies over a discrete time horizon. Network investments decisions under consideration are installation of the newest technology and addition of modules for both technologies. Through subsidies investments, subscribers can shift from the current technology to the newest one. As mentioned in Chapter 2, this shifting procedure depends on two factors:

• the amount of subsidies proposed to the subscribers,

• the level of deployment for the newest technology.

The contribution of this chapter is three-fold:

• provide a realistic model,

• strengthen the model with valid inequalities,

• assess economic and computational performances through numerical experiments.

In this framework, we do not take into account the coverage overlappings and we do not consider refarming strategies. The network investments are performed only on existing sites, on which subscribers are located. The subscribers subscribe to one of the two mobile technologies considered. The remainder of this chapter is organized as follows. Section 3.2 describes the Mobile Investments Strategies problem, for which a mixed integer formulation is provided and linearized in Section 3.3. Section 3.4 introduces the aforementioned valid inequalities. These models are numerically assessed in Section 3.5 on real-life instances. Concluding remarks are given in Section 3.6. This work has been published as journal paper [START_REF] Cambier | Optimizing the investments in mobile networks and subscriber migrations for a telecommunication operator[END_REF].

Problem description

The time horizon is taken as multi-period with equally-sized time periods denoted by t ∈ T = {1, . . . , t} (typically 5 periods of one year each). We add "0" for denoting the beginning of the time horizon.

The whole area is served by existing telecommunication sites potentially equipped with at most two mobile network technologies. We thus consider a set G = {CG, N G} of mobile network CHAPTER 3. THE MIS PROBLEM generations (the current one and the newest one being deployed) and a set S = {1, . . . , N S } of telecommunication sites. As we have already mentioned, the network capacity on a site can be increased in two ways: by deploying a technology on a site or by adding new modules of an already deployed technology. In this chapter, we assume that the current technology CG is deployed on all sites at the beginning of the time horizon and that only the newest technology N G can be deployed during the time horizon with a cost per site of CA N G . The binary parameter Z 0 s,N G , s ∈ S, is equal to 1 iff the newest network technology N G is deployed on site s at the beginning of the time horizon. The initial number of modules on each site is denoted by M 0 s,g , s ∈ S, g ∈ G. For each site and for each deployed technology, adding new modules is possible with a unitary cost of CM g , g ∈ G. Note that, as mentioned in Section 2.7, we consider that network costs do not vary over the time horizon as, in an operational context, they are settled through long-time procurement with suppliers (covering the network life-cycle). Technical constraints impose an upper bound on the number of modules that can be added to a site for each technology, which we note M g , g ∈ G.

Let us introduce CAP g , g ∈ G, the unitary capacity of a module of each network technology.

The initial number of subscribers to each technology associated with each site is denoted by U 0 s,g , s ∈ S, g ∈ G. We recall that the subscribers considered are dimensioning subscribers (see Sections 2.4.1 and 2.4.2).

For technical reasons, subscribers cannot be served by a more recent technology than the one they subscribe to. Hence, CG subscribers have to be served by CG technology. For quality of experience motivations, we introduce a load balancing rule stating that N G subscribers associated to a site s ∈ S are served by N G technology if deployed on s and CG technology otherwise.

We recall that the whole investments in user upgrades are made towards the newest technology N G and that the upgrade mechanism modeling subscribers willing to shift to N G technology depends only on two parameters. The first one is the value of the subsidy denoted by σ. The set of possible values taken by σ will be denoted by K. This set is finite due to practical considerations (modeling traditionally used marketing offers : for instance, 20% savings on the new phone). The second one is an indicator of the level of N G technology deployment. This indicator will be taken as a range of coverage c (low, medium low, medium high and high coverages for instance). The range of coverage of a given time period will be measured as the range of the proportion of sites on which N G technology is deployed, denoted α and referred as sites coverage, in what follows. For modeling coverage ranges, we partition the interval [0, 1] into C smaller intervals [L c , U c [, and define C = {1, . . . , C}. The function modeling the upgrade mechanism, denoted by f : K × C → [0, 1], indicates the proportion of subscribers willing to shift to N G technology if they receive the given subsidy σ ∈ K under a given range of coverage c ∈ C at the beginning of the time period t ∈ T . This function is assumed non-decreasing in both arguments. We denote by N t , t ∈ T , g ∈ G the forecast percentage of incoming users subscribing to technology g in time period t. New subscribers are assumed to be assigned to sites proportionally to the total number of subscribers at the end of the previous time period.

As already pointed out, network and subscriber dynamics are linked. First, each network generation has to be dimensioned to handle the traffic demand per subscriber D t o,g , t ∈ T , o ∈ G g ∈ G. These demands are forecast Average Usage per User, converted in traffic demand by the dimensioning rules mentioned in Chapter 2. As CG subscribers are only served by CG, we simplify notations by stating that a CG subscriber will have the demand D t

CG . An N G subscriber will have the demand D t N G,N G if served by N G and D t N G,CG otherwise. We assume that D t CG ≤ D t N G,CG << D t N G,N G . Indeed, we consider than the technical limitations on connections make the traffic generated by a N G user on CG far lower than the traffic generated by a N G user on N G, and superior or equal to the traffic generated by a CG user. Second, telecommunication operators are ranked according to their performance. Therefore, we decide to focus on requiring satisfying levels for two key performance indicators: the proportion of sites covered by N G at the end of the time horizon, which is denoted by α t and the averaged quality of experience to the corresponding subscribers. The averaged quality of experience is guaranteed by asking for a minimal proportion of the total number of subscribers being N G subscribers associated with N G sites. These subscribers benefit indeed from the new performances and have the maximum throughput. The thresholds required at the end of the time horizon associated with these two targeting indicators are respectively denoted by α and QoE.

Decisions are taken over the time horizon. These decisions are the deployment of N G technology, the number of modules added (for all technologies), and the subsidies given to the subscribers from older technologies for shifting to N G technology. The problem defined in this work, denoted as the Mobile Investments Strategies (MIS) problem, consists in finding the decisions which minimize network and subscribers investments over the time horizon while satisfying capacity and targeting constraints.

A network representation of the MIS for an example with three sites and two time periods is provided in Figure 4.

Parameters introduced in this section are summed up below:

• CA N G is the cost of adding N G technology,
• CM g is the cost of adding a module of a technology g ∈ G,

• M 0 s,g stands for the initial number of modules of technology g ∈ G on site s ∈ S,

• M g stands a technical upper bound on the number of modules of technology g ∈ G,

• Z 0 s,N G stands for the initial presence (yes/no) of N G technology on site s ∈ S,

• U 0 s,g is the initial number of subscribers on site s ∈ S to technology g ∈ G,

• D t o,g is the unitary demand of a subscriber to technology o ∈ G served by technology g ∈ G at time period t ∈ T ,

• N t g is the percentage of incoming user subscribers to technology g ∈ G at time period t ∈ T .

• CAP g is the capacity of adding a module of a technology g ∈ G,

• f (σ, c) is the reaction to the subsidy offered σ ∈ K under range of coverage interval c ∈ C,

• σ t ∈ K is the value of the subsidy offered at time period t ∈ T ,

• L c stands for the lower bound of coverage range c ∈ C,

• U c stands for the upper bound of coverage range c ∈ C,

• α 0 stands for the sites coverage at the beginning of the time horizon,

• α t stands for the sites coverage at the end of time period t ∈ T ,

• c t ∈ C is the range of coverage of α t-1 for each time period t ∈ T ,

• α and QoE are the thresholds fixed as strategic guidelines.

A network representation of the MIS problem for an example with three sites and two time periods is provided in Figure 4.

Mathematical modeling

We provide in this section a mixed-integer formulation for the problem described in Section 3.2. We define the set of decision variables used in our formulation in Section 3.

Decision variables

For modeling the network investment, we use the following variables:

• For t ∈ T ∪ {0}, s ∈ S, let us introduce the binary variable

z t s,N G =
1, if the newest technology is deployed at site s at the end of time period t, 0, otherwise.

• For t ∈ T ∪ {0}, s ∈ S, g ∈ G, the integer variable m t s,g represents the total number of modules of technology g deployed on site s at the end of time period t.

As for modeling the number of users on each site, we use the following continuous variables:

• For each t ∈ T ∪ {0}, s ∈ S, g ∈ G, let u t s,g denote the total number of subscribers to technology g in site s at the end of time period t (we denote an upper bound on this quantity by U t s,g ),

• For each t ∈ T , s ∈ S, o, g ∈ G 2 , let u t s,o,g denote the total number of subscribers to technology o served by technology g in site s at the end of time period t.

In addition, the notations σ t , c t , and α t introduced in the previous section become optimization variables:

• For each t ∈ T , let σ t be the value of the subsidy, in ke, offered to subscribers to former technologies for shifting to technology N G at the beginning of time period t,

• For each t ∈ T , let α t = s∈S z t s,N G N S
be the redundant variable that denotes the N G sites coverage (fraction of sites where N G technology is deployed) at the end of the time period t,

• For each t ∈ T , let c t denote the interval of C to which α t-1 belongs.

The upgrade function, representing the percentage of users reacting positively to a subsidy σ ∈ K for a given coverage c ∈ C, is denoted by f (σ, c) and will be modeled explicitly in Section 3.3.3.

Remark 1. The total number of subscribers is constant as it does not depend on the values taken by the optimization variables. We denote this constant by U T OT t s for each time period t and each site s. It is recursively defined as:

U T OT 0 s = U 0 s,CG + U 0 s,N G U T OT t s = (1 + N t CG + N t N G )U T OT t-1 s

General formulation

The MIS can be modeled as the following mixed-integer program (MIP):

min t∈T σ t f σ t , c t s∈S u t-1 s,CG + s∈S g∈G CM g (m t s,g -M 0 s,g ) + s∈S CA N G (z t s,N G -Z 0 s,N G ) (3.1) s.t. m t s,CG ≤ M CG ∀s ∈ S, ∀t ∈ T , (3.2) m t s,N G ≤ M N G z t s,N G ∀s ∈ S, ∀t ∈ T , (3.3)
m t-1 s,g ≤ m t s,g ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (3.4)
u t s,N G = u t s,N G,CG + u t s,N G,N G ∀s ∈ S, ∀t ∈ T , (3.5)
u t s,N G,CG ≤ U t s,N G (1 -z t s,N G ) ∀s ∈ S, ∀t ∈ T , (3.6)
D t CG u t s,CG + D t N G,CG u t s,N G,CG ≤ CAP CG m t s,CG ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (3.7)
D t N G,N G u t s,N G,N G ≤ CAP N G m t s,N G ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (3.8)
u t s,CG = u t-1 s,CG + N t CG U T OT t-1 s -f σ t , c t u t-1 s,CG ∀s ∈ S, ∀t ∈ T , (3.9)
u t s,N G = u t-1 s,N G + N t N G U T OT t-1 s + f σ t , c t u t-1 s,CG ∀s ∈ S, ∀t ∈ T , (3.10) s∈S u t s,N G,N G ≥ QoE( s∈S U 0 s,N G + U 0 s,CG ), (3.11)
α t ≥ α, (3.12
)

α t N S = s∈S z t s,N G ∀t ∈ T ∪ {0}, (3.13)
α t-1 ∈ [L c t , U c t ] ∀t ∈ T , (3.14)
u 0 s,g = U 0 s,g ∀s ∈ S, ∀g ∈ G, (3.15)
m 0 s,g = M 0 s,g ∀s ∈ S, ∀g ∈ G, (3.16)
z 0 s,N G = Z 0 s,N G ∀s ∈ S, (3.17)
m t s,g ∈ Z ∀s ∈ S, ∀t ∈ T ∪ {0}, ∀g ∈ G, (3.18) z t s,N G ∈ {0, 1} ∀s ∈ S, ∀t ∈ T ∪ {0}, (3.19)
u t s,g ≥ 0 ∀s ∈ S, ∀t ∈ T ∪ {0}, ∀g ∈ G, (3.20) u t s,o,g ≥ 0 ∀s ∈ S, ∀t ∈ T , ∀o, g ∈ G 2 , (3.21)
σ t ∈ K ∀t ∈ T , (3.22)
c t ∈ C ∀t ∈ T . (3.23)
We denote this formulation by M N L . The objective function (3.1) minimizes both subscribers migration costs and network investments. The first term stands for the offered subsidies (user upgrades), the second term for the adding of new modules for increasing the capacity (densification), and the third term for the deployment of the newest technology N G (coverage extension). Constraints (3.2)-(3.4) are the network dynamic constraints. Constraints (3.2)-(3.3) define the upper bounds on the numbers of modules for each technology deployed on each site. These constraints also ensure that if a technology is not deployed, no corresponding modules can be added. Constraints (3.4) prevent from decommissioning by imposing the number of modules of each technology to be non-decreasing during the time horizon. Constraints (3.5)-(3.8) are the network dimensioning constraints, in charge of making the link between the network dynamic and the subscriber dynamic. Constraints (3.5) ensure that on each site, N G subscribers can be served by CG or N G technologies. If N G technology is not installed, they are served by CG technology (see capacity constraints thereafter). Constraints (3.6) state that they are served by N G technology if it is installed, ensuring the load balancing rule. Constraints (3.7) and (3.8) are the capacity constraints: the installed capacities of each technology on each site have to be sufficient for providing services for all users located at this site and having to be served by this technology. They also ensured the technical incompatibility stating that CG subscribers cannot be served by N G technology.

Constraints (3.9)-(3.10) are the subscriber dynamic constraints. They define the total number of subscribers to CG and N G technologies at each site and each time period, taking into account former CG subscribers who decide to shift to N G technology, thanks to subsidies and coverage improvements. Constraints (3.11)-(3.12) stand for the model strategic guidelines and refer to the end of the time horizon. Constraint (3.11) ensures the threshold of subscribers covered by the newest technology is met. Note that this quantity is proportional to the quality of experience which measures the percentage of users having access to the new technology throughput. Constraint (3.12) imposes that the threshold on the number of sites on which N G is deployed is met. Constraints (3.13) stand for defining variables α t . Constraints (3.14) define the range of coverage used in the subsidy function as the range of coverage to which belongs α t-1 . Constraints (3.15)-(3.17 Remark 2. The size of formulation M N L can be reduced by replacing variables m t s,g for each t ∈ T \ { t} by m t s,g and removing constraints (3.4). Indeed variables m are only required to be lowerly and upperly bounded and to be non-decreasing over the time horizon while the objective function only depends on m t s,g . However, we choose to present a model with variables m t s,g as a generic basis for businesses applications where budget has to be controlled over time, thus requiring the temporal dynamic of the number of modules. We will assess numerically in Section 3.5 a set of constraints smoothing the costs for the operator by bounding budget fluctuations by a percentage p. Let the budget spent in each year be denoted by

B t = σ t f σ t , c t s∈S u t-1 s,CG + s∈S g∈G CM g (m t s,g -m t-1 s,g ) + s∈S CA N G (z t s,N G -z t-1 s,N G ) ∀t ∈ T .
(3.24) so the objective function (3.1) is actually equal to t∈T B t . The cost equilibrium set of constraints can be written as follows:

(1 -p) × t ∈T B t t ≤ B t ≤ (1 + p) × t ∈T B t t ∀t ∈ T . (3.25)
With constraints (3.25) added to formulation M N L , variables m t s,g are no longer redundant. Remark 3. The time dependency of the technology installation variable z cannot be removed. Indeed, the upgrade reaction at period t ∈ T depends on variables z t-1 (constraints (3.13) and (3.14)). Hence, modifying the period of installation impacts the total upgrade reaction and the objective value. Note that the coverage will not always be set to the highest value due to the subsidies costs.

Upgrade function modeling

As we have mentioned, the upgrade function (function characterizing the proposition of CG subscribers that shift to NG technology) is non-decreasing in both the subsidy amount σ and the range of coverage c. To shorten the notation, we denote by f σ,c the percentage of subscribers that react positively when subsidy σ ∈ K is offered and the N G sites coverage belongs to the range [L c , U c [, formally defined as f (σ, c). Aiming to incorporate this in our formulation, we introduce a binary variable δ t σ,c for each t ∈ T , σ ∈ K, c ∈ C, taking value equal to 1 iff σ t is offered and α t-1 ∈ [L c , U c [. The first term of objective function (3.1) from Section 3.3.2 can be rewritten as follows:

t∈T σ∈K c∈C σf σ,c δ t σ,c s∈S u t-1 s,CG .
Also, constraints (3.9) and (3.10) can be written as:

u t s,CG = u t-1 s,CG + N t CG U T OT t-1 s - σ∈K c∈C f σ,c δ t σ,c u t-1 s,CG ∀s ∈ S ∀t ∈ T , (3.26) u t s,N G = u t-1 s,N G + N t N G U T OT t-1 s + σ∈K c∈C f σ,c δ t σ,c u t-1 s,CG ∀s ∈ S ∀t ∈ T . (3.27)
We linearize the products of binary variables δ t σ,c and continuous positive variables u t-1 s,CG using a classical method [START_REF] Fortet | Boole algebra and its application to operation research[END_REF]. For denoting this product, we introduce the continuous positive variables

π t σ,c,s,CG = δ t σ,c u t-1 s,CG for each t ∈ T , σ ∈ K, c ∈ C, s ∈ S.
Consequently, the MIS can be formulated as the following mixed-integer linear program (MILP). min

t∈T σ∈K c∈C s∈S σf σ,c π t σ,c,s,CG + s∈S g∈G CM g (m t s,g -M 0 s,g ) + s∈S CA N G (z t s,N G -Z 0 s,N G ) (3.28) s.t. (3.2) -(3.7), (3.11) -(3.13), (3.15) -(3.17) u t s,CG = u t-1 s,CG + N t CG U T OT t-1 s - σ∈K c∈C f σ,c π t σ,c,s,CG ∀s ∈ S, ∀t ∈ T , (3.29)
u t s,N G = u t-1 s,N G + N t N G U T OT t-1 s + σ∈K c∈C f σ,c π t σ,c,s,CG ∀s ∈ S, ∀t ∈ T , (3.30)
σ∈K c∈C

δ t σ,c = 1 ∀t ∈ T , (3.31)
σ∈K δ t σ,c ≤ 1 + U c -α t-1 ∀t ∈ T , ∀c ∈ C, (3.32)
σ∈K δ t σ,c ≤ 1 + α t-1 -L c ∀t ∈ T , ∀c ∈ C, (3.33)
π t σ,c,s,CG ≤ δ t σ,c U t-1 s,CG ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, (3.34)
π t σ,c,s,CG ≤ u t-1 s,CG ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, (3.35)
π t σ,c,s,CG ≥ u t-1 s,CG -(1 -δ t σ,c )U t-1 s,CG ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, (3.36)
m t s,g ∈ Z ∀s ∈ S, ∀t ∈ T ∪ {0}, ∀g ∈ G, (3.37)
z t s,N G ∈ {0, 1} ∀s ∈ S, ∀t ∈ T ∪ {0}, (3.38)
u t s,g ≥ 0 ∀s ∈ S, ∀t ∈ T ∪ {0}, ∀g ∈ G, (3.39)
u t s,o,g ≥ 0 ∀s ∈ S, ∀t ∈ T , ∀o, g ∈ G 2 , (3.40) δ t σ,c ∈ {0, 1} ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, (3.41)
π t σ,c,s,CG ≥ 0 ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C. ( 3

Valid inequalities

Preliminary computational experiments on small instances showed that the solutions of the linear relaxation of model M present variables z and δ fractional. Consequently, we propose several valid inequalities in this subsection to reinforce the model. The strength of these inequalities is assessed numerically in Section 3.5.2. Proposition 1. Considering a time period t ∈ T ∪ {0} and a site s ∈ S, inequality

z t s,N G ≤ z t+1 s,N G (3.43)
is valid for formulation M.

Proof. This result is implied by constraints (3.3) and (3.4).

Proposition 2. Considering a time period t ∈ T and a range of coverage c ∈ C, for all time periods t ≥ t, inequality

σ∈K c <c δ t σ,c ≤ 1 - σ∈K c ≥c δ t σ,c (3.44)
is valid for formulation M.

Proof. This set of constraints states that if at a time period t ∈ T , the range of coverage is greater or equal to c ∈ C , then the range of coverage for posterior time periods cannot be smaller. As defined in Section 3.2, the N G sites coverage is indeed non-decreasing over the time horizon.

Proposition 3. Considering a time period t ∈ T and a site s ∈ S, equality c∈C σ∈K

π t σ,c,s,CG = u t-1 s,CG (3.45)
is valid for formulation M.

Proof. Following the Reformulation Linearization Techniques (see [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF] for more details), we obtain these constraints by multiplying each constraint from set (3.31) by variables u t-1 s,CG for each s ∈ S. The product obtained in the left member is then replaced by the corresponding linearization variable. Proposition 4. Considering a time period t ∈ T and a range of coverage c ∈ C, inequality

N S L c σ∈K δ t σ,c ≤ s∈S z t s,N G (3.46)
is valid for formulation M.

Proof. The network is in a range of coverage c ∈ C only if technology N G is deployed on at least N S L c sites (remember that N S is the total number of sites and is constant over the time horizon).

Proposition 5. Let U t s,N G denote a lower bound on the number of N G subscribers on site s at time period t. Considering a time period t ∈ T and a site s ∈ S, inequality

D t N G,N G U t s,N G CAP N G z t s,N G ≤ m t s,N G (3.47)
is valid for formulation M.

Proof. If N G technology is deployed on a site s ∈ S at a time period t ∈ T , we know that N G subscribers have to be served by N G technology. By computing a lower bound on the quantity of N G subscribers at this site and on this time period, we can hence compute a corresponding lower bound on the number of modules required for satisfying the capacity constraints (3.7).

Proposition 6. Let U t s,N G denote an upper bound on the number of N G subscribers on site s at time period t. Considering a time period t ∈ T and a site s ∈ S, every optimal solution of the MIS satisfies the following inequality:

m t s,N G ≤ max(M 0 s,N G , D t N G,N G U t s,N G CAP N G )z t s,N G . (3.48)
Proof. If N G technology is not deployed on a site s ∈ S at a time period t, the number of modules for this technology on this site at this time period is 0. If N G technology is deployed on a site s ∈ S at a time period t, we know that only N G subscribers on this site can be served by N G technology. By computing an upper bound of the quantity of N G subscribers on this site at this time period, we can hence compute a corresponding upper bound of the number of modules needed to satisfy the capacity constraints (3.7). Installing more than this bound costs CA N G by additional module without any impact of the feasibility, and such a solution can hence not be the optimal one.

Remark 5. Values for bounds U t s,N G and U t s,N G are computed with the following recursive formulas:

U 0 s,N G = U 0 s,N G = U 0 s,N G U t s,N G = U t-1 s,N G + N t N G U T OT t-1 s + (U T OT t-1 s -U t s,N G ) min σ∈K f σ,C U t s,N G = U t-1 s,N G + N t N G U T OT t-1 s + (U T OT t-1 s -U t s,N G ) max σ∈K f σ,cinit

Case study for 3G and 4G

The purpose of this case study is two-fold. First, we assess the scalability of our MILP formulation and the impact of the proposed valid inequalities. Second, we observe the characteristics of the solutions in terms of costs, considering several business scenarios, including when the investment expenses are smoothed along the time horizon.

Instances and platform

Numerical tests are performed on instances of French telecommunication operator Orange in the French areas of Bretagne and Pays de la Loire representing a case study with two network generations: 3G and 4G. The full area contains 1075 sites: 700 equipped only with 3G technology and 375 equipped with both technologies. From this large instance, we create a set of smaller instances, in order to have different scenarios characterized by the number of sites and the 4G initial coverage: rural scenarios where the 4G technology is initially deployed on 17% of the sites, suburban scenarios where this proportion is equal to 34% and urban scenarios where it is equal to 68%. The real data include the number of modules and subscribers for each site. There are no new incomers in these instances, and the only evolution in the number of subscribers is hence due to subsidy. Other parameter values of this case study are realistic values taken from telecommunication equipment sellers. Each site can carry a maximum of four 3G modules (carrier) of 5MHZ with a capacity of 3 Mbps and a cost of 3 ke each and a maximum of five 4G modules of 10 MHZ (bandwidth) with a capacity of 25 Mbps and a cost of 16 ke each. The cost for adding the 4G technology on a site is 75 ke. The subscribers monthly demands are yearly forecast: D 3G = D 4G,3G increases from 1 Gb per month to 2 Gb per month; while D 4G,4G increases from 2 Gb per month to 5 Gb per month. We consider 10 values for the subsidy offered, σ ∈ {0, 100, 150, 200, 250, 300, 350, 400, 450, 500}e. We also rely on four levels of 4G sites coverage: low, medium low, medium high and high respectively refer to ranges (in%) [0, 25[, [25, 50[, [50, 75[ and [75, 100]. The curves from Figure 5 Table 8: Reaction of the subscribers (in %) on reference markets for given subsidies and coverage levels.

Two other upgrades functions are also considered for adapting to very technology-reluctant markets and technology-friendly markets. We ask for final target objectives of QoE = 80% for the quality of experience and α = 70% for the 4G sites coverage. We optimize on the typical time horizon of five years discretized in five time periods of one year. The unit of the objective value is ke.

The computations have been made on a server of 32 processors Intel Xeon of CPU 5110 clocked at 1.6 GHz each. The code has been written in Julia 1.1.0, with the use of the optimization package JuMP (see [START_REF] Dunning | JuMP: A modeling language for mathematical optimization[END_REF]) and the solver used is CPLEX 12.8 (default branch-and-bound algorithm). The time limit for MILP solving is set to 1800 seconds for the tests presented in Sections 3.5.2 and 3.5.3. We have observed in our experiments that removing the dependency of variables m on time period t does not help improving the solution found nor the gap.

Results for algorithmic tests

Our objectives in this section are to assess the scalability of our formulation (including the impact of the proposed valid inequalities) and to test its sensitivity to the type of areas. Hence we focus on twelve instances considering four sizes between 50 and 200 sites and the three types of areas mentioned above. The upgrade function used here is the reference one (see Table 8). Instances features are displayed in Tables 9, 10 and 11, column "N S " standing for the number of sites and column "density" standing for the density scenario (rural R, suburban S or urban U ). The solutions of the linear relaxation and of the MILP are computed with and without the valid inequalities from Section 3.4. More precisely, we test formulations (M), (M + each family of valid inequality) and (M + all families of valid inequalities). The obtained root gap for each tested formulation is displayed in Table 9. The root gap is given in percentage, and is obtained by dividing the difference between the value of the best solution found and the value of the continuous relaxation, by the value of the best solution found. The best root gap among the formulations with a single valid inequality is in bold. For each formulation, the value of the best solution found by CPLEX within the time limit is displayed in Table 10. We label the value with the character '*' if the branch-and-bound procedure converges. The best solution found is in bold.

The corresponding final gap is displayed in Table 11. The final gap is given in percentage, and is obtained by dividing the difference between the best solution and the best lower bound found, by the value of the best solution. The best value for the final gap is in bold and the second best is in italic. First, we provide insight on the relative efficiency of each family of valid inequalities. We observe, on Table 9, tighter relaxations when using the valid inequalities. More precisely, a significant improvement on the relaxation is enabled by the RLT set of inequalities (3.45). Improvements on the root gaps can also be seen in urban instances by adding the sets (3.43) or (3.48). Indeed, when the new technology is already deployed on most sites, the non-decreasing of z reduces the search space. For this reason, these instances are the ones for which adding all inequalities rather than only inequalities (3.45) significantly improves the root gap. Moreover, we observe that inequalities (3.45) also have the best impact among the different valid inequalities for reducing the final gap (see Table 11). The solution found with inequalities (3.45) is always the best one found, as it can be observed in Table 10, but using the inequalities all together enables us to find the same solutions, with (for most instances) a slightly lower final gap.

For the following tests and observations, we will hence focus on the formulation including all families of valid inequalities. First, referring to scalability, we observe that the branch-and-bound procedure converges to optimality for the three instances of 50 sites and the urban instances of 100 and 150 sites (and nearly converges for the urban instance of 200 sites). Besides, the final gap remain under 4 % for all instances. Second, we focus on the sensitivity to the type of area. We notice that the problem proves easier to solve in urban areas, which can be explained by the decisions on coverage extension needed to satisfy the strategic targets: having more sites already covered by the newest technology results indeed in fewer decisions to take. However, the relaxation is weaker (see Table 9) due to the shape of the subsidy function (beginning with an high coverage means higher reactions but also higher gaps between continuous reactions and discrete reactions). This enlightens that the problem practical difficulty is strongly correlated with the question of coverage extension. We notice that the resulting coverage extension investments also have a significant financial impact. For instance, the optimal solution for the rural instance of 50 sites is around two times more expensive than the optimal solution for the urban instance.

Results for business-oriented tests

In this section, we assess the impact of several business-oriented scenarios from both algorithmic and financial perspectives:

• smoothing the costs over the time horizon,

• considering three upgrade functions: the reference upgrade used in the algorithmic tests, the technology-reluctant and technology-friendly upgrades.

The technology-reluctant and technology-friendly upgrades functions considered are given in Tables 12 and 13, respectively. Table 13: Reaction of the subscribers (in %) on Technology-Friendly markets for given subsidies and coverage levels.

For these purposes, and in order to have a sufficient expected number of optimal solutions (according to the algorithmic tests) for assessing financial aspects, we consider a set of 18 instances made of:

• for the 50 sites instances: the three densities and the three types of market (9 instances),

• for the 100, 150 and 200 sites instances: suburban density and the three types of markets (9 instances).

These 18 instances are presented under "Instance" in Table 14. Columns "N S " and "density" have the same meaning as in section 3.5.2. The type of market is displayed in column "upgrade": "T.F. markets", "Ref. markets" and "T.R. markets" stand, respectively for technology-friendly, reference and technology-reluctant markets. We want to assess on these instances the impact of cost equilibrium, i.e. when we add constraints (3.25). These constraints enforce all period expenses to lie between (1-p) and (1+p) times the quotient of the total expenses over the time horizon by the number of time periods, where p is a parameter setting the maximal allowed budget fluctuation -set at 10% for the following tests.

Note that the valid inequalities still hold, except for inequalities (3.48), which are hence removed. Results for both formulations "M" and "M + cost equilibrium" are displayed in Table 14. For each formulation, the indicators provided are the best solution found in column "sol", the final gap in column "f-gap" and the root gap in column "r-gap". These indicators have the same definition as in Section 3.5.2. The last column "overcost" gives the resulting overcost (the relative gap in % between the values of the solutions without and with the cost equilibrium set of constraints).

From a computational point of view, adding the cost equilibrium constraints hardens the problem. We see indeed in Table 14 that the proof of optimality is obtained only for the urban instances of 50 sites.

From a financial point of view, we consider the 50 sites instances in order to analyze the characteristics of an optimal solution. We thus draw the features of the solution for the 50 sites suburban instance with the upgrade for the reference markets, when we do not require the cost to be smoothed, in Figure 6. The 4G sites coverage, the amount of subsidies given and the reaction of the subscribers are plotted. On the 4G sites coverage curve, we can notice that the 4G sites coverage at the end of the time horizon is 80% and that this value is not reached progressively throughout the time horizon. Indeed, the 4G sites coverage at the end of the first year is already nearly equal to this final value. This fast deployment is made to benefit from more upgrade thanks to coverage improvements (for instance the natural effect of coverage improvement can be observed at the second time period, over which the switch from coverage range medium low to range high enables the model not to offer any subsidy). This enlightens the financial interest for the operator in quickly having a network of good quality. However, it results also in large budget variations, with the first year costing more than four times the second most expensive year, and almost nothing spent over the second year, as we can see in Figure 7. These important variations do not match with the financial context of a telecommunication operator as investments should be distributed along the whole time horizon. We plot in Figure 8 the counterpart of Figure 6 when costs are required to be smoothed. We see in these curves that the range of coverage high is reached in four years in the solution with cost equilibrium instead of one without cost equilibrium (see Figure 6). The effect of the subsidies is hence considerably weakened, which can be observed on the reaction curve of Figure 8. This has an impact on the upgrade investments, which become higher (for instance 250e per user instead of 200 are offered in the last year). Besides, in the second year, a subsidy of 150e is offered while in the solution without imposing cost equilibrium the coverage improvement enables the model not to offer any subsidy. These subsidies investments have important effects on the costs of the corresponding time periods, as can be observed in Figures 7 and9. By comparing the previous instance with the other 50 sites instances for reference markets in rural and urban areas, we see the influence of the initial density on the overcost resulting from the cost smoothing. This effect can be seen in Table 14, column "overcost" and rows Ref.markets: the overcost is around 12% for rural and suburban instances while it is only 1% for urban ones. The needed investments for reaching the upper range of coverages are indeed lower when starting from higher initial 4G sites coverages, reducing gap between solutions with and without cost equilibrium. We hence are able to quantify the overcost to get business-fit solutions and see that this overcost is particularly reduced for urban instances.

Finally, with regards to the type of markets, we notice that there seems to be no algorithmic sensitivity to the choice of the upgrade function. In what concerns the financial sensitivity, we notice that, as expected, since more upgrade investments are needed, the cost is higher on reluctant markets. For instance, the cost for the suburban instance of 50 sites with the upgrade for reluctant markets is 33% more expensive than the instance with the upgrade for technology-friendly markets.

Computational tests on large instances

In this section, we assess our exact solution method on 10 instances corresponding to different French territorial divisions. Two regions: Bretagne (divided into 4 departments: Finistère, Côtes d'Armor, Morbihan and Ille et Vilaine) and part of Pays de la Loire (divided into 3 departments: Mayenne, Sarthe, Maine et Loire) are hence considered. As the planification is made for 5 years, the computational time is not what matters most for the operator, so we test larger time limits in order to see if it enables us to find better solutions and to reduce the gaps.

Instances are displayed in Table 15. The name of the territorial division (department/region), its number of sites and its initial 4G sites coverage in % are respectively stored under "Ter. Div.", "N S " and "α 0 ". The best solution found and the final gap are labelled in the same way as above, and indicated for three different time limits: half an hour, two hours and five hours.

We observe that, with a five-hour time limit, the final gap obtained is below 5% for 8 large real-life instances. However, the model struggles to find a good quality solution for the two largest instances.

Conclusion

The problem introduced in this chapter models multi-year investments planning for a telecommunication operator. Encompassing several real aspects faced by operators, our problem consists in optimizing network and subscriber dynamics under capacity and strategic constraints. In particular, we have modeled the fraction of subscribers adopting a new technology as depending on the coverage of that technology. In addition, the operator can provide subsidies to encourage the subscribers to shift faster to that technology. We have provided a non-linear MIP formulation for this problem, which we linearize and strengthen with several sets of valid inequalities. Computational tests have been made for a real 3G/4G case-study. The efficiency of the valid inequalities in improving the performance has been underlined, as well as the relevance of the branch-andbound procedure performed on the tightened MILP for solving scaled real-life instances. For the largest instances, the solver struggles to find a feasible solution and hence using a heuristic algorithm would be interesting to find a good-quality primal feasible solution. This issue is tackled in Chapter 5.

Besides, this problem does not encompass the full scope of generations of the operator (2G/3G/4G/5G), and the different levers and dynamics induced. The proposed model associates subscribers to a unique telecommunication site, which can lead to over-dimensioning. These aspects are treated in the next chapter.

Chapter 4

Practical variants for the Mobile Investments Strategies problem

Introduction

The MIS problem introduced in Chapter 3 tackles the optimization, over a discrete time horizon, of three important components of the strategy of the telecommunication company:

• network dynamic,

• subscriber dynamic,

• strategic guidelines (quality of experience, coverage).

The MIS problem, however, focuses on the two generations context, while a telecommunication operator has several generations to operate. Some additional levers on network and subsidies policies arise when considering more-than-two generations. Besides, as stated in Chapter 2, the refarming policy of the operator also plays an important role in the multi-generation mobile investments strategies. In this chapter, we also consider the introduction of sites coverage overlapping to prevent from over-dimensioning and the possibility of installing new sites for tackling coverage densification or/and extension contexts.

Therefore, the contributions of this chapter are:

• providing a more-than-two generation model enabling to test these different policies and levers for the operator,

• adding a third dynamic with the spectrum management,

• being able to take into account coverage overlappings, and to tackle coverage extension contexts with new sites installations,

• assessing economic and computational performances through numerical experiments.

In this chapter, we thus introduce several structuring problems faced by the operator, as well as extensions/modifications of the mathematical model from Chapter 3 which enable to tackle these different variants. The extension to more-than-two generation contexts and to different investment policies is presented in Section 4.2. Section 4.3 tackles the modeling of refarming strategies. Section 4.4 tackles the introduction of coverage overlapping which possibly reduces network investments. Section 4.5 integrates the possibility of modeling new sites. Three case studies are performed to assess the different models in Section 4.6.

More-than-two generation mobile investments strategies problem

The more-than-two generation problem is described in Section 4.2.1 and modeled in Section 4.2.2.

Key decision policies in more-than-two generation contexts

Three important questions arise for the operator when aiming to tackle more-than-two generation problems.

1. It has to decide its network investments policy, i.e. which technologies can be deployed (or not) over the time horizon and for which technologies new modules can be added.

2. It has to define its subsidies policy, i.e. to which current subscriptions and for shifting to which technologies the subsidies are offered. Note that, if allowed by the regulatory context, offered subsidies could have different values according to the current and/or targeted subscription. Furthermore, we stress the fact that reactions (and thus the modeled upgrade function) could also be different with respect to current or targeted technologies.

3. It has to define its load balancing policy, i.e. which network technologies are preferred to serve subscribers of different subscriptions while satisfying technical incompatibilities and deployment of the technology on the associated site. Note that this rule could be no preference among compatible and deployed technologies, a strict priority order (served by the most efficient compatible and deployed technology) or a mix of them (for instance, served by the most efficient and compatible technology if deployed, and no preference among less efficient technologies otherwise).

To have a generic model, we differentiate the set of subscriptions type O (to which the users subscribe) and the set of network technologies G (which are installed on the network).

Remark 6. This distinction makes sense for model refinements in two ways:

• The set of network technologies G is not necessarily the same set as the set of generations {2G, 3G, 4G, 5G}. Indeed, specific affiliates constraints can lead to separate technologies for a generation, for example separating the FDD (Frequency-division duplexing) and the TDD (time-division duplexing) technologies.

• The set of subscriptions type O is not necessarily the same set as the set of generations. Indeed, separating subscribers to the same technology in different groups enables to refine the approximations of subscribers demand, by creating several groups with different demand profiles. For instance, 4G subscribers could be divided in 4G-low consumption subscribers, 4G-normal usage subscribers, and 4G-very high consumption with different marketing decision for each of these profiles. Besides, this distinction also facilitates the integration of specific marketing constraints such as "users to be served in priority" rules.

For modeling the installation policies, we hence introduce for each network technology g ∈ G the binary parameters: InvA g and InvM g indicating, respectively, if network technology g or a module of it can be installed or not. We assume that the oldest network technology is always installed to avoid infeasibility. We also assume that the newest network technology N G can always be installed and that its capacity can always be increased. We assume that the subsidies are performed towards a unique subscription type denoted by N O and that N O subscribers are -and are the only ones to be -served by N G technology. This hypothesis is performed for readability of the model, but is not necessary for the following results. In case of several network technologies corresponding to the latest generation, the quality of experience and coverage definitions should be modified accordingly, taking into account all newest network technologies. The same transformations can be performed in case of several subscription types corresponding to the latest generation; however in this case knowing how are dispatched the subsided subscribers among the different subscription types, would be necessary to model the subscribers dynamic.

As In what concerns the subsidies mechanism, we assume that it makes subscribers shift to N O subscription type. So far, the shifting function has been defined as depending on the subsidy proposal and the network state of coverage. In the case of marketing data for different behaviors according to the current subscription types, this function depends also on the current subscription type of the subscribers. Parameter f σ,c is hence replaced with f σ,c,o . We can also adapt, for each t ∈ T , the decision variable σ t by introducing a subsidy proposal σ t o for each subscription o ∈ O, hence enabling the operator to target different categories of subscribers (e.g.: giving higher subsidies to the subscribers served by saturated networks).

This problem is denoted by MG-MIS (More-than-two Generation Mobile Investments Strategies) throughout the manuscript.

Mathematical modeling

We provide in this section a model that tackles the different levers presented in Section 4.2.1. Parameters used in the modeling are either adapted from Chapter 3 or described in Section 4.2.1.

They are summed up below:

• Parameter adapted for multi technology/subscription types framework:

-CA g is the cost of adding network technology g ∈ G, We modify some of the decision variables introduced in Chapter 3: Consequently, we can model the more-than-two generation mobile investments strategies problem M G -M IS as follows:

-Z 0 s,
• u t s,
min t∈T σ∈K c∈C s∈S o∈O\{N O} σ × f σ,c,o × π t σ,c,s,o + s∈S g∈G CM g (m t s,g -M 0 s,g ) + s∈S g∈G CA g (z t s,g -Z 0 s,g ) (4.1) s.t. m t s,g ≤ M g z t s,g ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (4.2)
m t-1 s,g ≤ m t s,g ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (4.3)
m t s,g ≤ M 0 s,g + M g × InvM g ∀s ∈ S, ∀g ∈ G (4.4) z t s,g ≤ Z 0 s,g + InvA g ∀s ∈ S, ∀g ∈ G (4.5) u t s,o = g∈G|CPo,g =0 u t s,o,g ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (4.6)
u t s,o,g ≤ U t s,o (1 -z t s,k ) ∀(o, g, k) ∈ OXG 2 |CP o,g < CP o,k , ∀s ∈ S, (4.7
)

o∈G D t o,g u t s,o,g ≤ CAP g m t s,g ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, (4.8)
u t s,o = u t-1 s,o + N t o U T OT t-1 s - σ∈K c∈C f σ,c π t σ,c,s,o ∀s ∈ S, ∀t ∈ T , ∀o ∈ O \ {N O}, (4.9)
u t s,N O = u t-1 s,N O + N t N O U T OT t-1 s + o∈O\{N O} σ∈K c∈C f σ,c,o π t σ,c,s,o
∀s ∈ S, ∀t ∈ T , (4.10)

s∈S u t s,N O,N G ≥ QoE × s∈S U T OT t s , (4.11)
α t ≥ α, (4.12)
σ∈K c∈C

δ t σ,c,o = 1 ∀t ∈ T , (4.13
)

σ∈K δ t σ,c,o ≤ 1 + U c -α t-1 ∀t ∈ T , ∀c ∈ C, (4.14)
σ∈K δ t σ,c,o ≤ 1 + α t-1 -L c ∀t ∈ T , ∀c ∈ C, (4.15)
π t σ,c,s,o ≤ δ t σ,c,o U t-1 s,o ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ G, (4.16
)

π t σ,c,s,o ≤ u t-1 s,o ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ G, (4.17)
π t σ,c,s,o ≥ u t-1 s,o -(1 -δ t σ,c,o )U t-1 s,o ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ G, (4.18)
u 0 s,o = U 0 s,o ∀s ∈ S, ∀o ∈ O, (4.19)
m 0 s,g = M 0 s,g ∀s ∈ S, ∀g ∈ G, (4.20)
z 0 s,g = Z 0 s,g ∀s ∈ S, ∀g ∈ G, (4.21)

Mobile investment strategies problem with refarming strategies

In this section, we introduce a new dynamic that the telecommunication company has to manage: the refarming strategies (see Section 2.5). The MIS problem with refarming strategies is described in Section 4.3.1. Section 4.3.2 presents an adaptation of formulation M M G for modeling this problem.

Key features of spectrum dynamic and refarming policies

In this section, we aim to introduce the spectrum dynamic, which enables the operator to make savings by reallocating parts of the spectrum bandwidth which were previously used for older technologies. Subscribers are hence still served on sites by technologies g ∈ G but these technologies are now implemented on frequency bands b belonging to set B = {b 1 , . . . , b N B }. Installing a capacity module for a given network technology hence requires bandwidth on a given band for this network technology. The increase in capacity is directly linked to the increase in bandwidth. The bandwidth corresponding to each capacity module is denoted by ω g , g ∈ G. We define Ω t b as the total spectrum holding allocated on band b ∈ B at time period t ∈ T to the operator. We assume that this value is the same for all the considered sites. The notation for the number of modules for each site s ∈ S, each technology g ∈ G on each band b ∈ B at the beginning of the time horizon is M 0 s,g,b .

Remark 9. The spectrum holding parameter Ω t b , t ∈ T , b ∈ B is decided by the regulator. As mentioned in Chapter 2, the operator can increase it by buying parts of the spectrum throughout auctions. Such mechanisms are outside the scope of this thesis: this parameter is assumed known for each band and each time period, as a result of either past auctions or as part of a planned scenario of spectrum holding extension through auctions. Frequency band Technology We can distinguish in the example from Table 16 three types of bands usage:

t 1 t 2 t 3 t 4 t 5 b 1 g 1 g 2 N G SH 0 0 10
• The frequency band b 1 is dedicated to the new technology from the beginning. This means this band was not used for previous network technologies. In the example of France, the bands 800 MHz and 2600 MHz were first used for 4G, and the bands 700 MHz and 3400 MHz will first be used for 5G.

• The frequency band b 2 is partially refarmed over the time horizon. At the end of the time horizon, 5 MHz of each older technology are kept by the operator, as some services still require the old technologies. Such bands are called "legacy bands".

• The frequency band b 3 is progressively refarmed to be fully dedicated to the new technology at the end of the time horizon.

As the refarming strategy requires to decrease the capacity for current technologies, we remove the non-decreasing rules for modules and introduce a cost of removal CR g for each g ∈ G \ {N G}. We still require the number of modules for technology N G to be non-decreasing over the time horizon, as this is the technology the operator aims to deploy.

The resulting optimization problem will be referred to as the R-MG-MIS (Refarming Multi-Generation Mobile Investments Strategies) problem throughout the manuscript.

Mathematical modeling

To take into account refarming strategies, we introduce new variables m t s,g,b , that stand for the number of modules of network technology g ∈ G operating on band b ∈ B on site s ∈ S at time period t ∈ T ∪ {0}, to consider the spectrum dynamic. We have hence by definition the following equality:

m t s,g = b∈B m t s,g,b , ∀t ∈ T ∪ {0}, ∀s ∈ S, ∀g ∈ G. (4.31)
We reformulate the objective in order to model refarming strategies taking into account the possibility of removing modules. We observe indeed that, in presence of modules removal, the expression s∈S g∈G CM g (m t s,g -M 0 s,g ) no longer computes the cost of adding new modules correctly. In this context, we have to evaluate the cost at each time period and for each band. The positive terms will appear multiplied by the installation cost CM g while the negative ones will appear multiplied by the removal cost CR g .

We hence introduce two new positive variables defined by inequalities:

incr t s,g,b ≥ m t s,g,b -m t-1 s,g,b (4.32
)

and decr t s,g,b ≥ m t-1 s,g,b -m t s,g,b (4.33)
Consequently, the objective can be reformulated as follows: To model refarming strategies, the following constraints are added to the formulation.

min t∈T σ∈K c∈C s∈S o∈O\{N O} σ × f σ,c × π t σ,c
ω g m t s,g,b ≤ ω t g,b ∀s ∈ S, ∀t ∈ T , ∀g ∈ G, ∀b ∈ B, (4.35)
Constraints (4.35) stand for the maximal bandwidth allocated in the refarming plan to a technology on a band. With parameters verifying

g∈G ω t g,b ≤ Ω t b ,
we obtain that the total bandwidth used on each site is lower than the spectrum holding.

We In case of not-yet planned refarming strategies, or as source of comparison with the assessed strategies, we provide a framework where the total bandwidth used on each site is lower than the spectrum holding, but the division of the allocation between generations is not imposed. In this framework, constraints (4.35) are removed and replaced by the following (less constraining) constraints:

g∈G ω g m t s,g,b ≤ Ω t b , ∀b ∈ B, ∀t ∈ T . ( 4

Mobile investments strategies problem with users not exclusively located on sites

In this section, we aim to tackle coverage overlappings by separating the set of telecommunication sites serving the subscribers with the set of areas A (where the subscribers are located). A description of the problem, where subscribers are located on areas, is provided in Section 4.4.1. A mathematical modeling is provided in Section 4.4.2.

Key features of geography

Considering overlapping between sites coverage is required to avoid over-dimensioning. As it can be seen on the example from Section 2.4.3, taking into account the coverage overlappings possibly enables savings by reducing the number of sites on which the newest technology has to be installed. We assume that the whole territory is divided into areas where subscribers are located. The initial number of subscribers for each subscription type and each area is denoted by U 0 a,o , a ∈ A, o ∈ O. Technically, a subscriber has to be served by a technology installed on a site covering him. We approximate sites coverage by disks of radii provided by Table 17. Given the small sizes of the areas relatively to the ranges, we assume that subscribers are uniformly located in the areas. A given site can serve on a given area at most a fraction of the total number of subscribers of this area. For the sake of simplicity, we hence assume that fraction to be proportional to the intersection of the site range and the area. For that purpose, we introduce the parameter E a,s,g , a ∈ A, s ∈ S, g ∈ G which is equal to the percentage of subscribers of area a that can (geographically) be served by site s for technology g. We add a threshold effect and take into account only values of E greater than 0.1. We provide an example of coverage ranges of two existing sites in Figure 10 and its associated bipartite multigraph in Figure 11. A non-labeled edge stands for a value of 1, a labeled edge for a value equal to the label, and an absence of edge for a value of 0. The load balancing policies are still modeled by CP o,g but are assumed to be site by site: subscribers are not served by a technology on a given site if a technology with strictly higher priority is installed on this site. We refer to this problem as the Mobile Investments Strategies problem with Geographical features and denote it as GEO-MIS. It consists in minimizing the network investments on existing and new sites and the subsidies investments while satisfying geographical ranges, load balancing policies, capacity constraints, and strategic guidelines constraints. As for modeling the number of subscribers on each area served by each site, we use the following continuous variables:

• for each t ∈ T , a ∈ A, s ∈ S, o, g ∈ G 2 , u t
a,o,s,g denotes the total number of subscribers to subscription type o on area a served by technology g of site s at the end of time period t.

Consequently, the GEO-MIS problem can be modeled as follows:

min t∈T σ∈K c∈C a∈A o∈O\{N O} σ × f σ,c,o × π t σ,c
σ∈K δ t σ,c,o ≤ 1 + U c -α t-1 ∀t ∈ T , ∀c ∈ C, ∀o ∈ O, (4.52
)

σ∈K δ t σ,c,o ≤ 1 + α t-1 -L c ∀t ∈ T , ∀c ∈ C, ∀o ∈ O, (4.53)
π t σ,c,a,o ≤ δ t σ,c,o U t-1 a,o ∀a ∈ A, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O, (4.54)
π t σ,c,a,o ≤ u t-1 a,o ∀a ∈ A, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O, (4.55)
π t σ,c,a,o ≥ u t-1 a,o -(1 -δ t σ,c,o )U t-1 a,o ∀a ∈ A, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O, (4.56)
u 0 a,o = U 0 a,o ∀a ∈ A, ∀o ∈ O, (4.57)
m 0 s,g = M 0 s,g ∀s ∈ S, ∀g ∈ G, (4.58)
z 0 s,g = Z 0 s,g ∀s ∈ S, ∀g ∈ G, (4.59)

Mobile investments strategies with densification or coverage extension

As mentioned in Section 2.2.3, new sites installations can occur in three contexts:

• densification, when existing sites are not sufficient for desaturating the traffic,

• coverage extension, to serve territories that were not already covered,

• micro cells.

The lever of adding new sites is described in Section 4.5.1. The way they can be modeled by adaptation of formulation M GEO is provided in Section 4.5.2.

Key features and potential locations for new sites installation

For tackling new sites installation, we consider the context where subscribers are located on areas and we partition the set of telecommunication sites S in two subsets:

• Set of existing telecommunication sites E

• Set of potential NG telecommunication sites P

We assume that the oldest technology is installed on each site of set E and that the possibilities of installing technology and increasing capacity on these sites are fixed with parameters Inv A and Inv M -see Section 4.2.1. Sites from P are assumed to be only N G sites, i.e. only the newest technology N G can be installed on each site from P. We provide an example of coverage ranges of two existing sites and one new site in Figure 12 and its associated bipartite multigraph in Figure 13. Each new site costs the sum of the installation cost (due to civil engineering) which is denoted by CI and the technology installation costs of the technology installed.

Mathematical modeling

Formulation M GEO can easily be adapted to model new sites installations. In this section, we will present a modeling in the context of microcells (see Section 2.2.3): only the newest technology N G is installed on such sites, which have a lower range than the existing sites. We introduce for each p ∈ P the binary variable:

y p =    1 if

Case studies

Aiming to test scalability and economic performances of the different variants presented, three case studies are performed in this section: Section 4.6.1 assesses more-than-two generation levers on four-generation instances while Section 4.6.2 focuses on refarming strategies. Section 4.6.3 measures the impact of taking into account overlapping on three generation instances. For all these case studies, we use a server of 16 processors Intel Xeon of CPU 5110 and clocked at 1.6 GHz each. The code has been written in Julia 1.1.0, and the solver used is CPLEX 12.8 (default branch-and-bound algorithm).

Case study on multi-generation levers

The purpose of this case study is two-fold. First, we assess the scalability of CPLEX algorithms for solving our MILP formulations for multi-generation instances. Second, we test realistic business scenarios regarding the different rules described in Section 4.2.1.

Among the possible business scenario, we focus on the following variants for each lever, labeled and defined as follows:

• network investment rules:

reference: Possibility of increasing the capacity for all technologies and of installing only the newest technology, all installations: Possibility of increasing the capacity for all technologies and of installing all technologies,

• load balancing:

strict priority order: Subscribers served by the closest technology relative to their subscription type among the technology installed, priority + indifference: Subscribers served by the technology corresponding to their subscription type if installed and indifference otherwise, total indifference: Subscribers served by any installed technology,

• subsidies for subscriber migration:

subscriber reaction depends on the level of coverage of the newest technology and the given subsidy,

subscriber reaction depends on the level of coverage of the newest technology, on the given subsidy and the types of subscription (with, in both cases, the possibility of differentiating or not the subsidy proposal),

As shown by the results from Chapter 3, scalability for two generations is assessed until 50 sites. As we have four generations and in order to have optimal solutions for assessing economic performances of the different variants, we will test the model with 5 sites, with a half an hour time-limit. To test all rules, these instances are four technologies instances (2G/3G/4G/5G). We have one subscription type (o2G,o3G,o4G,o5G) by generation, and the technical compatibility rule states that a subscription type oxG can be served by yG technology, where x, y ∈ {2, 3, 4, 5} and y ≤ x. 2G is installed with one module on all sites. 5G is not installed at the beginning of the time horizon and no subscriber has yet subscribed to subscription type o5G. Values for 5G costs and consumption are taken from forecast data. Four instances have been generated which such settings.

Impact of network management policies

Our objectives in this section are to assess both algorithmic and financial impact of network investments and load balancing choices. We test the three considered rules for the load balancing, as well as two rules for the investments. We hence have six configurations by instances. The upgrade function used here corresponds to the reference market function (see Section 3.5). The subsidy mechanism used is considered independent from the reaction and the decision.

Instances are displayed in the left three columns of Table 18, column "investments" for the investment scenario used, and "load balancing policies" for the load balancing scenario used. Results are presented in the right four columns of Table 18. The following indicators are used for both formulations. Column "sol" stands for the value of the solution obtained by CPLEX within the time limit. The solver computation time, in seconds, is given in column "time". Column "f-gap" (final gap) represents the gap between the solution found and the best lower bound found while "o-gap"(origin gap) stands for the gap between the solution found and the linear relaxation.

First, in what concerns the investment rules, we observe that installing only the newest technology is not always feasible. During the first period, the effect of the subsidies is limited by the initial level of deployment and the number of modules that can be installed for 3G and 4G technologies is bounded. The installation of 4G technology can hence be sometimes required for serving 4G subscribers as they cannot be handled fully by 3G and as they cannot be served by 5G (technical incompatibility).

For instances which are feasible without new installations, we observe that performing an installation is not the best strategy (as the important subsidies needed for the guidelines will make the subscribers shift anyway and reduce the number of clients on these technologies), and hence the costs are equal in both scenarios. These results enlighten the importance of subsidies for desaturating the oldest technologies, allowing the operator to prioritize network investments on the newest one.

Regarding the costs of optimal solutions, we observe that the instances where more indifference occurs have a strictly cheaper solution. More liberty is indeed offered for choosing the technology with remaining capacity, reducing the investments (2% gap on average for the four instances considered).

Impact of targeted subsidy proposals

Next, we aim at testing the financial and scalability impact of different subsidy mechanisms:

• the reaction to the subsidy proposal can (or not) depend, in addition to its amount and of the level of deployment, on the current subscription type of the subscribers,

• the subsidy proposal is differentiated (or not) according to the current subscription type of the subscribers. We choose hence to use the strict priority order rule for load balancing and the reference rules for investments. The four instances are then tested with two scenarios for reactions, "ref. reaction" stands for the scenario of previous subsection and "2G boost" for a scenario where the reaction of 2G subscribers is doubled. Instances are displayed in the two left columns of Table 19, column "upgrade" standing for the upgrade function used. Results are presented in the right part of Table 19: the columns below "Different decisions" correspond to the model with different decisions and those below "Same decisions" to the model imposing a unique subsidy. The following indicators are used for both formulations. Column "sol" stands for the value of the solution obtained by the solver within the time limit. The solver computation time, in seconds, is given in column "time". Column "f-gap" (final gap) represents the gap between the solution found and the best lower bound found while "o-gap" (origin gap) stands for the gap between the solution found and the linear relaxation. Column "extra cost" provides the gap between the solution with differentiation allowed and the solution without.

Differentiating in the modeling according to the different offers hardens the problem. The solver does not converge in half an hour, even for 50 sites. The number of nodes visited by the branch-and-bound algorithm is indeed two to four times more important with the differentiation. However, we see that the gap between the value of the best solution found in half an hour and the optimal solution of the framework when a unique subsidy decision is imposed, is already around 6%. The saving made by non imposing a unique subsidy decision is hence important, due to the possibility of focusing the subsidies investments on the population which is the most responsible for network congestion. This focus of subsidies investments is illustrated by comparing Figure 14 with Figure 15. We observe in Figure 14 that the 4G generation is targeted in priority in order to invest in 5G rather than in 4G technology. This also has an influence on the arrival of the new technology, with the highest range of coverage reached in the scenario with differentiation (Figure 14) at the last time period, while it is reached a period sooner (Figure 15) in the scenario without differentiation.

Impact of technology shutdowns and/or new frequency band acquisitions

In this section, we aim to use the refarming modeling for assessing different refarming strategies in a 2G/3G/4G context. As the first tests for 5G are performed on new frequency bands, this corresponds to the current context. In order to assess the refarming plan integration, we consider three generations (technology and subscription types are identical to the generation set) instances (2G/3G/4G) larger in number of sites than previously in this chapter: 50, 100, 150, 200 and 400 sites, since refarming strategies are being planned at the scale of a region or an affiliate. These sites are the same sites as in the instances of section 3.5.1. 2G technology is installed with one or two modules on all sites on frequency band 900 MHz and/or 1800 MHz. 3G is deployed on frequency bands 900 MHz and/or 2100 MHz. 4G can be installed on new frequency bands 800

MHz and 2600 MHz, as well as on frequency band 2100 MHz when this band has been partially or fully refarmed. A removal cost is introduced and fixed to one third of the installation cost. The load balancing policies, subsidies, and investments are set to reference policies. The strategic guidelines minimal thresholds are still set to 80% for the quality of experience QoE and 70% for the coverage α. The time limit for MIP solving is set to 18000 seconds (5 hours). Three refarming scenarios are compared and provided in Table 20, Table 21 and Table 22.

In all scenarios, no modifications on frequency bands 800 MHz and 2600 MHz are possible while 2G technology on frequency band 1800 MHz needs to be fully refarmed. Differences between scenarios come from decisions of refarming in bands 900 MHz and 2100 MHz, as well as the decision to use new frequency band 700 MHz for 4G. In the first refarming plan, at the end of the time horizon, 5 MHz are conserved for 2G and 3G on the 900 MHz frequency band (legacy band), while the frequency band 2100 MHz is fully refarmed (all 20 MHz available are dedicated to 4G technology). The second refarming plan differentiates itself by keeping 10MHz for 3G on frequency band 2100 MHz. For 4G, 10 additional MHz are available on the new 700 MHz band for the last two years. The third refarming plan consists in 2G and 3G shutdown (full stop of these technologies including end of services and removal of equipments), allowing full spectrum resources dedicated to 4G, including the new 700 MHz frequency band. Table 22: Refarming plan scenario 3

These three scenarios are assessed on three-generation instances for 50 to 200 sites, on scalability and business point of view. Results for the different frameworks are presented in Table 23. "No decommission" refers to the problem MG-MIS, modeling the case where parameter Mg , g ∈ G handles the limitations due to spectrum, the division between the different bands is not performed in the modeling and non decreasing constraints (4.3) are imposed. "No imposed refarming" refers to a framework where decommissioning is allowed, and the spectrum holding has to be satisfied (constraints (4.3.2)), but no refarming plans are imposed. Under "Refarming strategies", labels "RP1", "RP2" and "RP3" respectively refer to the three different refarming plans 1,2 and 3.

Instance

Refarming On a scalability point of view, we observe that three generation instances of more than 50 sites are difficult to solve. The proof of optimality is obtained in 18000 seconds only for the instances of 50 and 100 sites with refarming plan 1 and for the instances from 50 to 200 sites with refarming plan 3.

From a business point of view, first, comparing the column "no decommission" with the other ones, we observe that the refarming plans induced extra costs. Second, comparing the different refarming strategies, we observe that the scenario which keeps resources for 3G (refarming plan 2) is the less expensive one. Hence, the shutdown of 2G and/or 3G can lead to higher costs due to:

• removal costs of the already installed modules,

• subsidies costs to make all (or most subscribers in case of legacy bands) subscribers to the old technology shift (and hence being able to remove it completely).

In particular, the way laggards -reluctant subscribers -are modeled considerably increases the subsidies cost. Such results have to be refined by more marketing data, however, they enlighten the fact that laggards demand much more financial incentive than the other subscribers. Due to their limited usage of data services, they have indeed no reason to change their phone and/or subscription. Yet, a full shutdown of technology is not possible without making the laggards shift, which considerably increases the subsidies cost and hence the total investments cost. However, these additional costs have to be put in balance with savings that could be imputed to refarming, in particular the energy and operational expenditures savings, as well as the gain of new subscribers thanks to the improvements of debit.

Besides, the quantification of extra costs of the different scenarios enables the operator to evaluate the new band price. This valuation can be used for bidding in spectrum auctions.

Impact of sites coverage overlappings

In this section, we aim to enlighten the impact of sites coverage overlappings on both computational and business points of view. Hence, we will consider 3G/4G instances with only existing sites on which are installed either 3G or both 3G and 4G. These instances are subsets of sites extracted from the real data, geographically coherent, and of different densities (urban, rural, or suburban). We know positions of existing sites as well as numbers of subscribers within their range (from the network data).

To build a no-overlapping framework, we consider one area per existing site, these areas partition the territory and include subscribers from the associated site. We assume that all subscribers of an area can be covered by and only by network technologies of the corresponding site (graph on Figure 4 becomes a bi-identity graph). Inversely, to build the areas for the overlapping framework, we randomly simulate points with a Uniform Point Process (with the number of points as input) and obtain the areas by computing the Voronoi cells (see [START_REF] B Laszczyszyn | Stochastic Geometry Analysis of Cellular Networks[END_REF]) of both existing sites and simulated points. For each technology, subscribers associated with an existing site are uniformly dispatched on the areas including on its coverage surface. The number of subscribers for a given area is hence obtained by summing sites contributions. We then build the parameter E by checking for each site whose areas (simulated or associated with another existing site) are included within its coverage surface for each technology.

We want to assess the impact of sites coverage overlappings in three different cases: urban, rural, and suburban. We select the city center of Rennes for the urban instance, extend it with the neighborhood for the suburban instance and select two rural instances in the west countryside of Rennes. For each of these three instances, we test four configurations: the no-overlapping framework and three simulation configurations (depending on the size of the area considered) with the random process described above. Features of the different instances are displayed in Table 24, column "N S " standing for the number of (existing) sites, column "surface" for the whole instance surface area, column "density" for urban (U), rural (R) or suburban (SU), column "overlap" for the framework used ("Y" meaning overlapping framework and "N" no-overlapping framework) and column "average size " for the average surface of the area. In the no-overlapping framework, we have indicated in this column the 4G coverage surface of a site in 4G. Column N A N S stands for the product of the number of sites and number of areas. For each overlapping configuration, we run five simulations and compute the average of the results.

Results are stored in the same table. Column "sol" stands for the value of the solution obtained by the solver within the time limit, labeled with a "sol * " if the branch-and-bound procedure converges. The solver computation time, in seconds, is given in column "time". Column "f-gap" (final gap) represents the gap between the solution found and the best lower bound found while "r-gap" (root gap) stands for the gap between the solution found and the linear relaxation. Columns "added 4G sites" and "added 4G modules" stand respectively for the number of performed installations of 4G technology and the number of 4G modules added in the solution found by the solver.

From the computational point of view, we observe that taking into account the overlappings reduces significantly the final gap obtained by the solver in half an hour or the computation time when the optimal solution is found. For example, in the suburban instance, optimal values are not obtained within the time-limit, but the gap of the first simulated instance has a gap 14 times lower than in the no-overlapping framework. Due to the increase in size (one additional dimension), we could have expected the problem to harden when considering the overlappings. However, the flexibility introduced by the overlappings allows converging faster. We notice that smaller areas harden the problem as expected. This can be seen in the rural instance of 65 sites and area surface of 35km 2 , for which the convergence is not obtained in the half an hour time limit.

From the economical point of view, we observe important savings for the different densities when taking into account the overlappings. Let us focus first on the solutions for which we have the convergence in both frameworks, enabling us to compare optimal solution values. Taking into account overlappings allows savings of around 35% in the urban solution and 20% in the rural ones. In the suburban instance, for which the solver does not converge in half an hour for both frameworks, savings are of around 20 %. As shown by the right columns of Table 24, these savings are mainly due to the allowed reduction of 4G installation. In the optimal solutions of the urban instance, 4G is equipped on 4 sites when taking into account the overlapping compared to 13 in the no-overlapping framework. Regarding the suburban solutions, 35 sites are equipped instead of 54 when the overlappings are not taken into account, and 35 modules installed instead of 84. We are hence able to enlighten savings due to a reduction in the installations of both modules and antennas and to quantify this reduction.

CHAPTER 4. PRACTICAL VARIANTS FOR THE MIS PROBLEM

Conclusion

The different variants introduced in this chapter enable us to capture the situation of a telecommunication operator which has several generations to manage and decisions to make. MG-MIS encompasses investments, load balancing policies and subsidies policies. In R-MG-MIS, the introduction of the spectrum management dynamic enables the operator to test different refarming strategies, and its impact on the other decisions. The GEO-MIS problem enables to take into account sites coverage overlappings, and new sites installation. Mathematical formulations have been designed for each of these extensions. The computational study enlightens the benefit of some variants, for example, the differentiation of subsidies which enables up to 6% savings. From a scalability point of view, we observe that solving more than 100 sites instances and more than three generations instances require heuristic algorithms in both contexts. The next chapter is dedicated to the design of such algorithms.

Chapter 5

Heuristic algorithms for mobile investments strategies problems

Introduction

In this chapter, we aim to solve the MIS problem and its variants on large instances. In particular, we consider three variants numbered and denoted as follows:

1. Two generations (MIS)

2. Two generations with cost equilibrium constraints (B-MIS)

3. More-than-two generation without (MG-MIS) and with refarming strategies (R-MG-MIS)

Remark 11. In this chapter, we need to distinguish between the MIS problem without cost equilibrium constraints (3.25), simply denoted by MIS, and the MIS problem with such constraints added, denoted by the newly-introduced notation B-MIS.

As large instances, we mean instances for which the exact branch-and-bound method applied on the reinforced MILP does not converge in five hours. In order to solve at this scale, designing heuristics methods is hence required. We observe that for all these variants the main difficulties come from the linearization of the subscribers' reaction. Hence, a simple heuristic approach to the problem would be to fix variables σ t (the amount of the subsidy offered to current generations subscribers) and c t (the coverage range) to specific values σt ∈ K and ct ∈ C for each period t ∈ T and solve the resulting problem optimally. Note that c1 is already fixed to the initial coverage c init . The resulting problem is hence a network investment planning problem, with specific constraints depending on the variant (temporal constraints, load balancing constraints, geographical constraints).

Consequently, we decide to look for solving variants 1-3 above with algorithms based on the following procedure:

• select values to test for the subscriber dynamic (shifting functions) by fixing values for variables σ t and c t ,

• solve each resulting problem, and keep the solution of minimal cost.

Furthermore, let us now denote the subproblem where σ t = σt and c t = ct as the MIS(σ, c).

Remark 12. We use the same notation for all variants of MIS, for example, we will denote the multi-generation problem where σ t = σt and c t = ct as the MG-MIS(σ, c).

For selecting the values to test, we design two algorithms: a variable neighborhood search and a partial enumeration procedure. As for the resulting problem, we propose different solving methods: a mixed-integer formulation for each variant, as well as specific exact or approximated methods (dynamic programming for variant 1, site decomposition for variants 1-3).

The remainder of this chapter is organized as follows. Section 5.2 describes the different methods for the selection of the subscriber dynamic (σ t , c t ). Section 5.3 introduces, for each variant 1-3, mixed integer linear formulations for solving the subproblems obtained once the subscriber dynamic (σ t , c t ) is fixed. Section 5.4 presents simplified formulations for solving M IS(σ, c) without cost equilibrium constraints and a dynamic programming method when an additional assumption is imposed. In Section 5.5, we introduce a site decomposition method for solving the subproblems, remeding for all 3 variants. Section 5.6 assesses numerically the heuristics in different contexts.

For the MIS problem, the combination using a partial enumeration for the selection and the dynamic programming method for solving M IS(σ, c) (Section 5.4) has been published in [START_REF] Cambier | Optimizing the investments in mobile networks and subscriber migrations for a telecommunication operator[END_REF].

Algorithms for selecting the subscriber dynamic

In this section, we introduce two methods for selecting the subscriber dynamic.

Remark 13. For the sake of simplification, throughout the chapter, vectors ct and σt are assumed to be of size t. In case of subsidies differentiation, as in Section 4.2.1, the size of vector σ will be multiplied by the number of current generations. The methodology remains the same.

Our algorithm cannot afford to enumerate, for each time period t ∈ T , all possible values of (σ t , ct ) ∈ K × C since that would result in solving |(K × C) t| problems. When combined with an exact solving method for the subproblem, this approach would actually solve the MIS exactly. Instead, we propose to test a restricted subset W ⊂ (K × C) t of different couples of values for each time period. This procedure is described in Algorithm 1.

Throughout the section, we refer as cost(σ, c) the value of a solution of the problem considered by an exact or approximate method from Section 5.3-5.5.

Algorithm 1: Basic heuristic algorithm for solving variant P

1 INPUT : W ⊂ (K × C) t for (σ, c) ∈ W do 2 cost(σ, c) ← solution cost of P (σ, c) 3 return min (σ,c)∈W cost(σ, c)
The remainder of the section is organized as follows. In Section 5.2.1, we provide formulas for computing the number of subscribers and subsidies costs for a given pair (σ, c). In Section 5.2.2, we discuss some couples (σ, c) which are infeasible and should hence not be tested. Two methods are then presented for building the set W of couples to be tested. The first method, presented in Section 5.2.3, is a variable neighborhood search (VNS), which reduces the number of problems to solve. The second method is a partial enumeration, presented in Section 5.2.4.

Subscribers dynamic constant

We assume that the subscriber dynamic decisions are now fixed to (σ, c). This assumption makes some of the previous decision variables become constants as not depending on any decision variable. Applying constraints (4.9) recursively over the time horizon, we obtain that the number of subscribers to o ∈ O \ {N O} is a constant and is equal to

U t s,o = (1 -f σt ,c t )U t-1 s,o + N t g U T OT t-1 s ∀t ∈ T , ∀s ∈ S. (5.1)
Besides, we recall that the total number of subscribers on a site s ∈ S is constant over the time horizon and designed by U T OT t s . We hence have

U t s,N O = U T OT s - o∈O\{N O} U t s,o ∀t ∈ T , ∀s ∈ S. (5.2)
We can also compute the amount of money spent in subsidies offered to the subscribers, which is equal to the constant upgradecost = t∈T o∈O\{N O} σt f σt ct U t-1 s,o .

(5.3)

Filtering

In this section, we aim to identify simple conditions which are sufficient to detect that a pair (σ, c) should not be considered. First, looking at the properties of the coverage range, we introduce filtering on vector c. We know for the coverage that only three values have to be enumerated (as c 1 is determined by the parameters and c t has no influence on the shifting). We know also that c t is increasing over the time horizon T , which reduces the number of possible combinations when generating c.

Remark 14. The vector c = c 1 , . . . , c t corresponds to an indicator of the N G coverage deployment, and is hence non-decreasing, even in problem R-MG-MIS.

Second, the quality experience threshold QoE imposes a minimal percentage of subscribers which have to shift to the newest technology, which leads to some combinations of σ and c being infeasible. Proposition 8. A pair (σ, c) which does not verify the following equation is infeasible:

s∈S U t s,N G ≥ QoE s∈S U T OT t s (5.4)
Proof. From the quality of experience constraints (4.11), we can derive that:

s∈S u t s,N G ≥ s∈S u t s,N G z t s,N G ≥ QoE s∈S U T OT t s
By replacing variables u t s,N G in this inequality by the constants defined above, we obtain that this inequality is verified.

We define the filtering procedure, denoted f iltering, as the procedure which takes a subset from (K × C) t in input, and remove from this set the infeasible vectors aforementioned.

VNS algorithm

Aiming to reduce the number of problems to solve, we look forward to generating a set W with good properties in the sense that it contains a limited number of pairs to evaluate, and that the cost(σ, c) is not too high (good-quality solutions).

When finding a pair (σ, c) associated with such a solution, it could be interesting to explore around, as the subsidies dynamic can be close to the optimal one. However, a simple descent (always search an improvement from the best solution found) must not be used as we have also to avoid being stuck in a local minimum. A local minimum is for example a solution where any change on vector σ or vector c does not improve the solution found, but there are improvements when modifying σ and c simultaneously.

The Variable Neighborhood Search (VNS) algorithm was introduced in the aim of escaping from local minima by Mladenović and Hansen in [START_REF] Mladenović | Variable neighborhood search[END_REF]. The principle of the VNS is to explore successively different neighborhoods. According to the authors, this systematic change of neighborhood is motivated by three observations:

• a local optimum relative to one neighborhood structure is not necessarily a local optimum for another neighborhood structure,

• a global optimum is a local optimum with respect to all neighborhood structures,

• often most of the local optima are relatively close to each other.

In [START_REF] Hansen | Variable neighborhood search: basics and variants[END_REF], the authors give insights on variants of the VNS. The basic VNS method from [START_REF] Hansen | Variable neighborhood search: basics and variants[END_REF] is described in Algorithm 2. These variants differ by the procedure used in the different phases. The structure of our problem leads us to use a local search for the improvement phase and hence the basic VNS method (Algorithm 12 in the cited paper and reproduced in Algorithm 2).

Algorithm 2: Algorithm for Basic VNS

1 INPUT: iteration maximum k max , neighborhood structure N , initial solution x init ; 2 x ← x init ; 3 repeat 4 k ← 1; 5 while k ≤ kmax do 6 Shake(x, k, N ) ; 7 x ← Local search(x) ; 8 x, k ← Neighborhood change sequential(x, x , k) ; 9 until stopping condition;
Each phase of the VNS algorithm developed here is described below:

Local search

In the basic VNS method, the descent phase is a local search. Our local search function is described next. This local search will be performed by fully exploring the following neighborhood of the incumbent solution and returning the best solution found:

N 1 σ (σ) = σ | ∃i ∈ T , ∀t ∈ T \ {i}, σt = σ t , N 1 c (c) = c | ∃i ∈ T , ∀t ∈ T \ {i}, ct = c t .
This means our local search function returns the best solution among all solutions which have exactly, for each vector, one value different from the starting point.

We

Neighborhood structure and sequential change

We describe next how the function used in line 7 of Algorithm 2 is developed for our problem. The following neighborhood structure -defined by iterator k -is used in our VNS algorithm,

N k σ = σ | ∃L k , ∀t / ∈ L k , σt = σ t N k c = c | ∃L k , ∀t / ∈ L k , ct = c t
where L k is a list of indices (between 1 and t) of size equal to k. Neighborhood N 1 is simply the neighborhood used for the local search, with one component of each vector modified. Neighborhood N k modifies k components of each vector of the solution considered. The number of modified components is hence proportional to the neighborhood step. The change of neighborhood step used in our VNS will be the sequential change, one of the variants for this step presented in [START_REF] Hansen | Variable neighborhood search: basics and variants[END_REF]. If no improvement has been found, the algorithm proceeds to the next neighborhood. If a solution for improving the cost has been found, this solution becomes the new incumbent, and the search resumes from the first neighborhood.

Shaking

The aim of the shaking is to move to a solution in a given neighborhood defined by the current value of iterator k. Given a pair (σ, c) the shaking function returns hence a random couple (σ , c ) ∈ (N k σ , N k c ). With the choice made for the neighborhood structure, we have hence to look for a random solution among all solutions which have exactly, for each vector, k values which differ from the starting point.

Full algorithm

The combination of the presented local search, neighborhood change function and shaking function leads us to Algorithm 3. This algorithm is a slight variation of the basic VNS described in Algorithm 3. This algorithm starts from an initial solution, set by lines 1-4. At each iteration, the incumbent couple (σ, c):

Algorithm 3: VNS algorithm 1 INPUT : initial solution (σ init , c init ), stopping condition k max , neighborhood N ; 2 σ = σ init ; 3 c = c init ; 4 bestcost = cost(σ, c) ; 5 for k ≤ k max do 6 (σ curr , c curr ) ← Shaking(σ, c, k, N ) ; 7 σ min , c min ← argmin (σ,c)∈(N 1 σ curr ,N 1 c curr ) cost(σ, c) ; 8 if cost(σ min , c min ) < bestcost then
1. is perturbed by the shaking which is proportional to the iterator k (line 6)

the local search is performed (line 7)

Next, the algorithm checks if the solution found by the local search is better than the incumbent (line 8). When this is the case, the newly found solution becomes the new incumbent (lines 10-11), and the algorithm resumes to start with this new solution (line 9). Otherwise, the algorithm proceeds to the next neighborhood (line 13). The stopping condition is the maximal number of descents without any improvement, denoted by k max , and stated by line 5.

Remark 15. The vectors c and σ are of size t -2 and t respectively. If k > t, we modify t components.

Partial enumeration

One simple way to select values for W is to look only for particular solutions, with restrictions of the values taken by the coverage range σ and the subsidy proposal c at each time period. The reduction presented in this section has been used for MIS problem from Chapter 3, without cost equilibrium constraints (variant 1).

For the coverage range, we restrict to the following vector clast = (c init , |C|, |C|, |C|, |C|). We will see in Section 5.4 that the MIS problem with this restriction has good tractability properties.

The coverage is hence already determined, and for example, with 5 subsidies possibilities and 5 periods, the number of resulting problems to solve, before the quality of experience filtering from section 5.2.2, is reduced to 5 5 = 3125.

As for the subsidies proposal, an upper bound L can be fixed. We hence restrict K to K where |K | is the number of subsidies whose value is inferior to L.

This partial enumeration method is given in Algorithm 4.

Algorithm 4: Partial enumeration algorithm

1 INPUT : a scalar value L ; 2 W = {(σ, c)|∀t ∈ T , σ t ≤ L & c = clast} ; 3 W ← f iltering(W) ; 4 for (σ, c) ∈ W do 5 cost(σ, c) ← optimal solution cost of M IS(σ, c) 6 return min (σ,c)∈W cost(σ, c)

Reduced mixed-integer formulations for subproblems

At each step of both VNS and enumeration methods from the previous section, an optimization problem has to be solved. The fact that variables σ and c become constants fixed to σ and c enables us to reduce the number of variables. In this section, we provide mixed-integer formulation for the problems M IS(σ, c) and B -M IS(σ, c) in Section 5.3.1 and problems M G -M IS(σ, c) and R -M G -M IS(σ, c) in Section 5.3.2.

Formulations for two-generation problems M IS(σ, c) and B-M IS(σ, c)

In this section, we provide a mixed-integer formulation for M IS(σ, c) that can be extended to solve B -M IS(σ, c). We replace variables u t s,N G and u t s,CG by their constant values U t s,N G and U t s,CG (see equations (5.1) and (5.2)).

Let us now tackle the case of variables u t s,N G,CG and u t s,N G,CG .

Proposition 9. Constraints (3.5) and (3.6) can be replaced with the following constraints in formulation M, for each site s ∈ S and each time period t ∈ T :

u t s,N G,N G = U t s,N G z t s,N G , (5.5)
u t s,N G,CG = U t s,N G (1 -z t s,N G ). (5.6)
Proof. First, let us assume that equations (5.5) and (5.6) are satisfied. For each site s ∈ S, by summing (5.5) and (5.6), we obtain that (3.5) is satisfied. Clearly, equation (3.6) is implied by (5.6).

Reciprocally, let us assume that constraints (3.5) and (3.6) are both satisfied. Two cases can happen. If N G technology is installed (z t s,N G = 1), constraints (3.6) induce u t s,N G,CG = 0 and then u t s,N G = u t s,N G,N G so that equations (5.5) and (5.6) are satisfied. If N G technology is not installed (z t s,N G = 0), we have m t s,N G = 0 (see constraints (3.3)) and u t s,N G,N G = 0 (see constraints (3.8)) so that equations (5.5) and (5.6) are satisfied.

Consequently, the MIS(σ, c) can be formulated as follows

min upgradecost + s∈S g∈G CM g (m t s,g -M 0 s,g ) + s∈S CA N G (z t s,N G -Z 0 s,N G ) (5.7) s.t. m t s,CG ≤ M CG ∀s ∈ S, ∀t ∈ T , (5.8)
m t s,N G ≤ M N G z t s,N G ∀s ∈ S, ∀t ∈ T , (5.9)
m t-1 s,g ≤ m t s,g ∀s ∈ S, ∀t ∈ T , (5.10)
D t CG U t s,CG + D t N G,CG U t s,N G (1 -z t s,N G ) ≤ CAP CG m t s,CG ∀s ∈ S, ∀t ∈ T , (5.11)
D t N G,N G U t s,N G z t s,N G ≤ CAP N G m t s,N G ∀s ∈ S, ∀t ∈ T , (5.12
)

s∈S U t s,N G z t s,N G ≥ QoE s∈S U T OT t s (5.13) s∈S z t s,N G ≥ ᾱ (5.14) s∈S z t-1 s,N G ≥ L ct N S ∀t ∈ T , (5.15)
s∈S z t-1 s,N G ≤ U ct N S ∀t ∈ T , (5.16)
m 0 s,g = M 0 s,g ∀s ∈ S, ∀g ∈ G, (5.17)
z 0 s,N G = Z 0 s,N G ∀s ∈ S, (5.18)
m t s,g ∈ N ∀s ∈ S, ∀t ∈ T ∪ {0}, ∀g ∈ G, (5.19)
z t s,N G ∈ {0, 1} ∀s ∈ S, ∀t ∈ T ∪ {0}. (5.20)
The objective (3.1) can be reformulated into (5.7) where the term standing for subsidies cost is now a constant. Constraints (5.11)-(5.12) ensure the load balancing rules, seen from a network point of view rather than from a subscriber point of view. Constraints (5.11) ensure that CG technology has always to handle the consumption of CG subscribers and has also to handle the consumption of N G subscribers when N G technology is not installed. Constraints (5.12) ensure that when N G technology is installed, it has to handle the consumption of N G subscribers. The threshold constraint can be reformulated as (5.13) since N G subscribers are served by N G if and only if N G is installed. Constraints (5.14)-(5.16) are obtained by applying the definitions of α and c. We denote this formulation by M heur,2gen . Formulation M heur,2gen presented for the MIS(σ, c) problem still holds when smoothing constraints (3.25) are added and can hence be used for solving problem B -M IS(σ, c).

Formulations for more-than-two generations and multi-bands problems

M G -M IS(σ, c) and R -M G -M IS(σ, c)
In the previous section, we have shown how formulation M can be simplified to obtain a MILP with only integer variables m s,g , s ∈ S, g ∈ G and binary variables z s,N G , s ∈ S; tackling hence problems M IS(σ, c) and B-M IS(σ, c). We show in this section that not all these simplifications are possible in more-than-two-generation framework, and provide formulations for problems M G -M IS(σ, c) and

R -M G -M IS(σ, c).
The number of subscribers is still known for each subscription type o ∈ O, but two issues arise, preventing from introducing directly the load balancing policies into the capacity constraints, as done for two generations. First, some load-policies from Chapter 4 can create cases when we do not know which generation serves the subscribers. For instance, for serving a 4G subscriber on 2G/3G site, we could let the model decide between 2G and 3G technologies. Second, other policies like the strict priority order have non-linearities (example: the rule "a 4G subscriber is served by 2G if 4G and 3G are not installed" would require linearization of variables z when trying to express it directly). For these reasons, we look for formulations with variables m t s,g , z t s,g and u t s,o,g for each time period t ∈ T , technology g ∈ G and subscription type o ∈ O, the latter allowing us to know which technology serves which subscribers. The models presented in this section have to be solved at each iteration of the heuristic methods. When applying the partial enumeration or the VNS method introduced in Section 5.2, a subproblem is indeed solved each time we need to evaluate the value cost(σ, c). Averagely, in the VNS case, it represents around 1000 problems for 15 descents. Solving 1000 mixed integer formulations directly is impossible for large instances.

For this reason, we aim in the next sections to find other solving methods, with better computational properties, for each of the three considered variants. In case of the MIS problem, a pseudo-polynomial solving method is presented in Section 5.4. In case of B-MIS, MG-MIS and R-MG-MIS, in absence of further simplifications, we propose to use an heuristic based on a site decomposition in Section 5.5.

Further simplifications and pseudo-polynomial solving

method for problem M IS(σ, c)

In this section, we will focus on simplified formulations for the MIS(σ, c). First, we remove time dependency on variables m (replacing m t s,g by m s,g the number of modules installed at the end of the time horizon for each site s and generation g), which means that smoothing constraints (3.25) cannot be added to the formulations provided (see Remark 2). Moreover, let us recall that D t-1 o,g ≤ D t o,g for each o, g ∈ G and for each t ∈ T . Notice that for each t ∈ T and each site s ∈ S, U t-1 s,N G ≤ U t s,N G . Consequently, formulation M heur,2gen can be simplified significantly. Namely, one readily verifies that constraints (5.11)-(5.12) are satisfied if and only if the following constraints are satisfied:

D t CG U t s,CG +D t N G,CG U t s,N G (1 -z t s,N G ) ≤ CAP CG m s,CG ∀s ∈ S, ∀t ∈ T , (5.21)
D t N G U t s,N G z t s,N G ≤ CAP N G m s,N G ∀s ∈ S. (5.22)
We observe that we can use these constraints to compute a closed form for the optimal value taken by variables m s,g which depends on the values taken by variables z t s,N G . We know indeed that for each site s ∈ S the number of modules installed at the end of the time horizon is:

• for CG technology: -if N G is already installed (Z 0 s,N G = 1): mAI s,CG = max max i∈T D i CG U i s,CG CAP CG , M 0 s,CG
(only CG subscribers are served by CG technology),

if N G is not installed over the time horizon (z t s,N G = 0):

mNI s,CG = max       max i∈T D i CG U i CG,s + D i N G,CG U i N G,s CAP CG     , M 0 s,CG   (all subscribers are served by CG technology), -if N G is installed at time period t ∈ T (z t s,N G -z t-1 s,N G = 1): mt s,CG = max max i<t D i CG U i CG,s +D i N G,CG U i N G,s CAP CG , max i≥t D i CG U i s,CG CAP CG , M 0 s,CG ,
• for N G technology when it is installed (z t s,N G = 1): ms,NG = max

D t N G,N G U t s,N G CAP N G , M 0 s,N G .
Note that if, on a site s ∈ S, mAI s,CG > M CG then z t s,N G = 1 and if ms,NG > M N G then z t s,N G = 0. If both happen, the instance is infeasible. Consequently, we can provide a formulation for the MIS(σ, c) using only binary variables z.

min upgradecost + s∈S CA N G z t s,N G -Z 0 s,N G + ms,NG -M 0 s,N G CM N G z t s,N G + mNI s,CG -M 0 s,CG CM CG 1 -z t s,N G + t∈T mt s,CG -M 0 s,CG CM CG z t s,N G -z t-1 s,N G + mAI s,CG -M 0 s,CG CM CG Z 0 s,N G (5.23) s.t. s∈S U t s,N G z t s,N G ≥ QoE s∈S U T OT t s , (5.24)
z t-1 s,N G ≤ z t s,N G ∀t ∈ T , (5.25)
s∈S z t s,N G ≥ ᾱ, (5.26)
s∈S z t-1 s,N G ≥ L ct N S ∀t ∈ T , (5.27)
s∈S z t-1 s,N G ≤ U ct N S ∀t ∈ T , (5.28)
z 0 s,N G = Z 0 s,N G ∀s ∈ S, (5.29)
z t s,N G ∈ {0, 1} ∀s ∈ S, ∀t ∈ T . (5.30)
We define by S CG ⊂ S the subset of the sites where N G is not installed at the beginning of the time horizon. We also remove from set S CG the sites for which we already know if we will install N G technology or not due to infeasibilities. We notice that we only have to solve the problem on sites of set S CG . As explained next, for tractability reasons we introduce the assumption that c = (c init , C, . . . , C) for each (σ, c) ∈ W,

and study the problem with and without this assumption. '

With assumption (5.31)

The assumption implies that all network investments are performed in the first time period. Hence, we can replace variables z t s,N G for each t ∈ T by variables z t s,N G in formulation M heur,2gen . All costs due to modules for sites of set S \ S CG are labeled into constant netcost. Let constant N inst be the number of sites where we know N G is installed at the end of the time horizon. For each site s ∈ S CG , C1 s = CA N G + ms,NG CM N G denotes the cost implied by deciding to install N G technology and C2 s = mNI s,CG -mAI s,CG CM CG the cost implied by deciding not to.

Therefore, the MIS(σ, c), when c satisfied assumption (5.31) can be further reformulated as the following bidimensional knapsack problem:

min s∈S CG C1 s z t s,N G + C2 s (1 -z t s,N G ) + upgradecost + netcost (5.32) st s∈S CG U t s,N G z t s,N G ≥ QoE s∈S U T OT t s - s∈S\S CG U t s,N G , (5.33)
s∈S CG z t s,N G ≥ max( ᾱ, L C N S ) -N inst , (5.34)
z t s,N G ∈ {0, 1} ∀s ∈ S CG . (5.35)
Proposition 10. The MIS(σ, c) can be solved in

O(N S + |S CG | 2 (CA N G + M N G CM N G )) when ct = C, ∀t ∈ {2, . . . , t}.
Proof. From the arguments given above, this result follows from the fact that the problem becomes a knapsack problem which can be solved by a dynamic programming algorithm.

Without assumption (5.31)

First, notice that assumption (5.31) cannot be made on the optimal solution of the MIS, as enlightened by the following counter example: Let us consider an instance with one single site with 100 subscribers (total number of subscribers constant over the time horizon), initially all CG subscribers. N G technology is not installed at the beginning of the time horizon. Parameter QoE is set to 60%. Two subsidy proposals (0 and 100e) and two coverage ranges (high if N G has been installed and low otherwise) are considered with f 0,low = f 0,high = 0, f 100,low = 40% and f 100,high = 70%. Three 3G modules are already installed, enough for handling all the traffic from the 100 subscribers on 3G networks over the time horizon. One antenna N G has to be installed for a cost of CA N G , and one module N G has to be installed every 65 N G subscribers for a price of CM N G . The optimal solution performs two subsidies in coverage low for a total cost of C1 = CA N G + CM N G + 6.4ke. Installing at the first period would impose to perform at least one subsidy in coverage high and would hence require higher network and subsidies costs: the total cost would be C2 = CA N G + 2CM N G + 7ke.

We hence look in this section at the case where assumption (5.31) is not verified by c. In this case, we have to keep variables z t for each time period t ∈ T . Indeed, the change of range of coverage is a constraint that imposes to delay installations and hence creates temporal variations on z. We notice that formulation with variables z t can be reinforced by replacing equations (5.28) with the following equations:

s∈S z t-1 s,N G = U ct N S ∀t ∈ T |c t = C, (5.36)
Indeed, the installation choices are unconstrained inside the range, and hence the objective drives to perform these installations as soon as possible.

Sites decomposition

In this section, we aim to solve the subproblems of the different variants through a site decomposition heuristic. We will present this method for all the variants considered. From a computational point of view, it will be particularly relevant for variants 2 and 3, as the simplifications presented in section 5.4 for solving problem M IS(σ, c) of variant 1 cannot be used for solving problems

B -M IS(σ, c), M G -M IS(σ, c) and R -M G -M IS(σ, c).
Besides, we notice that the subsidy dynamic is the main coupling constraint for a site decomposition. As σ = σ, the subsidies decision is already known in the problem considered.

In all variants, the remaining "linking constraints" are:

• the quality of experience constraints: (5.13),

• the sites coverage at each time period and the end of time horizon: (5.14), (5.15), (5.16).

We observe that imposing these two constraints on each part of the partition is more restrictive than imposing these constraints on all sites. We hence focus on a site decomposition partition, described in the following. We partition the set S in N bl subsets of (nearly) equal sizes, such

∀bl ∈ {1, . . . , N bl -1}, S bl = 1 + (bl -1) N S N bl , . . . , bl * N S N bl
and

S N bl = 1 + (bl -1) N S N bl , . . . , N S
Remark 16. The case N bl = 1 corresponds to solving exactly the considered problem.

Thereafter, we consider one specific part S bl for a given bl ∈ {1, . . . , N bl -1}.

First, we look at the reduced problem M IS(σ, c) on part S bl . It can be formulated as follows:

min upgradecost + s∈S bl g∈G CM g (m t s,g -M 0 s,g ) + s∈S bl CA N G (z t s,N G -Z 0 s,N G ) (5.
s∈S bl z t-1 s,N G ≥ L ct |S bl | ∀t ∈ T , (5.45
) Proof. We suppose that constraints (5.43), (5.44), (5.45) and (5.46) are satisfied on each set S bl . For each of these sets of constraints, by summing it over all subsets, we obtain the corresponding constraint on the set S.

s∈S bl z t-1 s,N G ≤ U ct |S bl | ∀t ∈ T , ( 5
Consequently, we are able to solve problem M IS(σ, c) by solving formulations M bl for all blocks bl ∈ {1, . . . , N bl }: the cost of problem M IS(σ, c) is equal to obj(M bl ) + upgradecost. We now aim to extend this result for tackling problem B-MIS. We define hence and summing these constraints, we obtain exactly constraints (3.25) which are hence satisfied.

B t (S bl ) = s∈S g∈G CM g (m t s,g -m t-1 s,g ) + s∈S CA N G (z t s,N G -z t-1 s,N G ) ∀t ∈ T . ( 5
Such results can be extended to any temporal budget limitations, for instance stopping the investments at a given period: Proposition 13. Any solution which is for each block bl a solution of formulation M bl with constraints imposing upper or/and lower bounds on one or several B t (S bl ) is a feasible solution for formulation M, with the same constraints on the B t .

We now aim to tackle the case of problems M G -M IS by decomposing the formulation from Section 5. Proof. We suppose that constraints (5.61), (5.62), (5.63) and (5.64) are satisfied on each set S bl . For each of these sets of constraints, by summing it over all subsets, we obtain the corresponding constraint on the set S. Next, we look to extend this result to cost equilibrium constraints and to refarming constraints (problem R -M G -M IS(σ, c) ).

Cost equilibrium constraints can be handled with decomposition and arguments similar to the two-generation case (see Propositions (12) and (13) as well as the associated proofs).

Let us now focus on the case of refarming constraints. We decompose objective 4. [START_REF]Methodologies for valuation of spectrum[END_REF] for each block bl, time period t ∈ T , subsidy proposal σ ∈ K and coverage c ∈ C. These constraints ensure that a unique subsidy proposal is decided for all sites.

Computational experiments

In this chapter, we provide a generic framework for building heuristics algorithm, following the process of Algorithm 1.

More precisely, we design

• two methods for the selection phase: VNS and enumeration,

• for each variant, an integer linear formulation for solving the subproblems,

• for each variant, a site decomposition heuristic for solving the subproblems,

• for variant 1 (problem M IS), a simplified formulation with only binary variables,

• for a specific variant of variant 1 (assumption (5.31)), a dynamic programming.

Each combination of such methods could provide an heuristic to test. In this case-study, we focus on results for variants MIS and B-MIS on two-generation instances. We will indeed assess the different methods presented through these two cases studies, which give the most promising results:

• In the tests for MIS, we assess the partial enumeration method for selecting couples (σ, c) and the dynamic programming method for the solving of problem M IS(σ, c).

• In the tests for B-MIS, we assess the VNS method for selecting couples (σ, c) and the sites decomposition heuristic for the solving of problem M IS(σ, c).

In both tests, we consider the ten instances from Section 3.5. Motivated by the need of solving larger instances (3000 sites for the smallest affiliates), we introduce two bigger instances of 3000 sites and 12000 sites, which are realistic instances based on the instances from Section 3.5. Note that finding a feasible solution the two-generation and 12000 sites instance is out-of-memory for CPLEX solver, even for the MIS problem (variant 1).

The computations have been made on a server of 32 processors Intel Xeon of CPU 5110 clocked at 1.6 GHz each. The code has been written in Julia 1.1.0, and the solver used is CPLEX 12.8 (default branch-and-bound algorithm).

Large two-generation instances

The tests from this section have been published in [START_REF] Cambier | Optimizing the investments in mobile networks and subscriber migrations for a telecommunication operator[END_REF]. We assess the interest of our heuristic for finding good-quality feasible solutions for large instances of the MIS problem. We aim to use the pseudo-polynomial model provided in Section 5.4 for solving the subproblems enumerated through the partial enumeration method designed in Section 5.2.4. As mentioned previously, we have to look for a solution where the range ("high") is reached over the first period. We enumerate the amounts of subsidies σ ∈ W (ten possibilities if we do not restrict) at each time period (five) so as to solve each resulting problem MIS(σ, c). This means that we have to solve 10 5 MIS(σ, c) problems, which we cannot afford. We also observe that with 250 euros of subsidies at each period, we have less than 1% of the initial 3G subscribers remaining at the end of the time horizon and that this situation is feasible for our instances. In addition, we know (see Section 5.2.2) that when the subsidies reaction is not sufficient to reach the threshold of 80% of subscribers being 4G subscribers, the corresponding problem is infeasible. Hence, in our heuristic, we enumerate all σ ∈ {0, 100, 150, 200, 250} and we solve the problem only if the reaction is sufficient to reach the threshold. This gives at most 5 5 = 3125 MIS(σ, c) problems to solve.

In a second step, the solution found by the heuristic is used as an initial solution (MIPstart) for CP LEX solver. The time limit given to the solver is 7200 seconds minus the time of the heuristic in order to compare with the MIP solving in 7200 seconds without providing an initial solution.

Results are presented in Table 25. The column "heuristic" stands for the algorithm described above, the column "MILP" for the MILP without initial solution provided (results discussed in Section 3.5.4) and the column "MIPstart" for the MILP with the heuristic solution provided as MIPstart. The column "gapMILP" reports the gap between the heuristic value and the MILP solution value. We observe that the heuristic finds very good quality solutions for all instances in two hours of total computation time (heuristic + MIPstart). For the two largest instances, these solutions are far better (around 60% savings) than the best solution found without heuristic by the MIP in two hours. These solutions are not improved afterward by CPLEX but using the heuristic as MIPstart enables us to obtain the proof of convergence for the two smallest instances and to have all final gaps below 6%.

Two generations with cost equilibrium constraints

We assess in this section the VNS algorithm for problem B-MIS (cost equilibrium constraints (3.25) are imposed). In front of the difficulty of large instances with cost equilibrium, we use the site decomposition method from Section 5.5 rather than the exact formulation from Section 5.3.1 for solving each subproblem for the largest instances. The number of blocks has to be taken as a compromise value between the computation time savings thanks to the division and the multiplication of the number of problems to solve. Besides, dividing too much has the other disadvantage (in addition to computation time) that it can create parts on which it is impossible to verify the coverage range conditions. For these reasons and thanks to preliminary tests, we choose the number of blocks for each instance to have in each block between 200 and 400 sites to solve. For the seven departments instances, which contain less than 400 sites, we hence take a number of blocks equal to one, which is equivalent to solve exactly each problem M IS(σ, c).

In the following table, these three solving frameworks are respectively denoted by "VNS + exact MILP", "VNS+site dec" and "full exact MILP".

Results obtained when cost equilibrium constraints are imposed in a two-generation framework are presented in Table 26. The cost equilibrium constraints tested in Chapter 3 are taken as a reference for this two-generation test. For the department instances, as mentioned, no site decomposition is performed. The heuristic takes between 5000 and 13000 seconds. The solution found by the heuristic is only 0.5 % more expensive for the "Maine-et Loire" instance. It is 24 % more expensive for "Côtes-d'Armor" instance. The MIPSTART procedure improves the solution found by the heuristic for two departments: "Côtes-d'Armor" and "Ille-et-Vilaine".

We observe that with a five-hour time limit, the MILP does not find any solution for instances of more than 700 sites. On these instances, the heuristic with site decomposition is particularly valuable, as it finds a solution with a cost of 55543 ke for Bretagne (each subproblem is decomposed in two blocks) and a solution with a cost of 84352 ke for the whole instance (each subproblem is decomposed in three blocks). Comparisons with results from Table 25 show that the cost equilibrium extra costs are of 15 and 21 %, assessing hence the good quality of such solutions. The computation time is between five and six hours for these two instances. The MIPSTART procedure (extended to ten hours: five for the heuristic and five for the MIP) provides a solution of 76653 ke for the full instance which corresponds to an extra cost of 10 %.

As for bigger instances, the MILP approach is out-of-memory, even when a MIPSTART solution is provided. The heuristic for the 12000 sites instances run averagely in 550 000 seconds (a week).

We hence conclude of the relevance of VNS+site decomposition approach for solving the cost equilibrium variants.

Conclusion

A generic framework for building heuristics for solving large instances of the MIS problem and its variants has been proposed in this chapter, based on two components: a selection of values to test for subsidies and coverage, and a solving of each obtained subproblem by an exact method or an heuristic. Two methods have been designed for the selection phase: a partial enumeration and a VNS algorithm. Exact methods and heuristics methods have been provided for each of the three variants presented in this chapter. In particular, two combinations have been numerically assessed. First, a partial enumeration of σ and c combined with a dynamic programming method for solving the subproblem enables us to solve heuristically large instances of the MIS. Second, the association of a variable neighborhood search for the selection, of an efficient filtering, and of a site decomposition method has proved to be particularly valuable for the solving of frameworks with cost equilibrium.

Introduction

The subsidies function used in Chapter 3 is only a naive approximate modeling, since many internal and external factors intervene in operator marketing. We hence consider in this section uncertainty on the values of this shifting function, focusing on the two-period case.

We model the shifting function uncertainty via a known polyhedral set, leading to a robust optimization problem. Robust optimization is an efficient framework to handle uncertainty in (mixed-integer) linear optimization problems, see [START_REF] Ben-Tal | Robust optimization[END_REF] and [START_REF] Gabrel | Recent advances in robust optimization: An overview[END_REF] among others. The framework can, in theory, address a wide variety of optimization problems, including discrete variables [START_REF] Buchheim | Robust combinatorial optimization under convex and discrete cost uncertainty[END_REF], non-linear constraints [START_REF] Ben-Tal | Deriving robust counterparts of nonlinear uncertain inequalities[END_REF], and the multi-stage setting where some of the decision variables can adjust their value to the realization of the uncertain parameters, see [START_REF] Delage | Robust multistage decision making[END_REF] and [START_REF] İhsan Yanıkoglu | A survey of adjustable robust optimization[END_REF]. In practice, however, the dimensions of the problems one can expect to solve, and the optimality guarantees of the resulting algorithms strongly depend on each problem characteristics and on the difficulty of the underlying nominal optimization problem. Here one must bear in mind that the underlying model considered in this manuscript is already a difficult MILP that can be solved exactly only for moderate-size instances. This means that the robust counterpart we seek should not be much harder than its nominal variant.

Two specific difficulties happen in our case: some of the integer variables are adjustable, and the constraints of the problem have non-linear dependencies on the shifting function. While both specificities have been addressed in the recent robust optimization literature, they are often addressed through heuristic solution procedures. On the one hand, integer adjustable variables are typically tackled (approximately) by partitioning the uncertainty set [START_REF] Bertsimas | Multistage robust mixed-integer optimization with adaptive partitions[END_REF][START_REF] Postek | Multistage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set[END_REF] or by introducing complex decision rules [START_REF] Bertsimas | Binary decision rules for multistage adaptive mixed-integer optimization[END_REF]. On the other hand, robust optimization with non-linear dependency on the uncertainty parameters can, in some cases, be reformulated efficiently, for instance, when these dependencies are concave functions [START_REF] Ben-Tal | Deriving robust counterparts of nonlinear uncertain inequalities[END_REF]. The non-linear dependencies considered herein will be modeled by (non-concave) bilinear functions for which reformulations exist only in very particular cases, e.g., when the uncertainty set is an ellipsoid [START_REF] Ben-Tal | Robust solutions of uncertain quadratic and conicquadratic problems[END_REF] or if the function is the product of two affine functions [START_REF] Pessoa | Robust network design with uncertain outsourcing cost[END_REF].

We address the adjustable variables through uncertainty partitioning, while the non-linearities are handled by underlining the dominance of the extreme points of the uncertainty set. Specifically, our contribution is three-fold. First, we provide for the deterministic problem a reformulation of formulation M for the two-period case which will be more amenable to the derivation of the robust counterpart. This formulation is strengthened with RLT inequalities (see [START_REF] Sherali | A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems[END_REF]). Second, we provide two robust counterparts (static and adjustable) of the previous model, as well as a solving method. This method analyzes the structure of the problem to reformulate it as a linear mixed-integer formulation with a finite number of constraints and variables. Third, through numerical experiments on realistic instances, we provide insight on the effects of uncertainty, and the importance for the telecommunication company to adapt its decisions to the shifting function outcome in the first stage.

The remainder of this chapter is organized as follows. Section 6.2 presents the two-period reformulation for the deterministic framework. Section 6.3 introduces the static and adjustable robust counterparts. Numerical experiments assess both models in Section 6.4. Concluding remarks are given in Section 6.5.

This work has been submitted to EJOR journal (see [START_REF] Cambier | Optimizing subscriber migrations for a telecommunication operator in uncertain context[END_REF]).

Throughout the chapter, we focus on a two-period framework for the MIS problem, and consider a case where the total number of subscribers is constant over the time horizon.

Please note that looking for making the distinction between the proposal decision and the coverage decision, we introduce binary variables γ t and δ t σ such as:

δ t σ = c∈C δ t σ,c , ∀σ ∈ K, ∀t ∈ T , and
γ t c = σ∈K δ t σ,c ∀c ∈ C, ∀t ∈ T .
Proposition 16. Using these notations, set of constraints (3.31) is equivalent to the following sets of constraints:

c∈C γ t c = 1 ∀t ∈ T , (6.1)
and

σ∈K δ t σ = 1 ∀t ∈ T . (6.2)
6.2 Deterministic problem and formulations

Problem description and notations

The considered framework is the framework from Chapter 3. Let us recall that it is a twogeneration framework, with the following characteristics:

• CG technology is installed on all sites,

• NG technology can be installed on existing sites,

• CG subscribers are served by CG technology,

• NG subscribers are served by NG if installed, and CG otherwise.

As mentioned, we focus our study to a two-period framework. We describe next a reformulation of formulation M from Chapter 3 for the two-period case, which contains only binary and integer variables.

Reformulation

In this section, we will consider a reformulation of M that avoids the recursive structure defined by constraints (3.29) and (3.30) and expresses variables u directly in terms of variables δ, γ and function f . This reformulation will be more amenable to obtain a robust counterpart in our two-period framework.

Proposition 17. The following non-linear equalities are valid expressions for the number of subscribers on each site s ∈ S and each time period t ∈ T in M

u t s,CG = U 0 s,CG t i=1 1 - σ∈K c∈C f σ,c δ i σ γ i c and u t s,N G = U 0 s,CG + U 0 s,N G -u t s,CG = U 0 s,N G + U 0 s,CG 1 - t i=1 1 - σ∈K c∈C f σ,c δ i σ γ i c
Proof. The expression for u t s,CG is obtained by applying recursively over the time horizon constraints (3.29) from formulation M. The expression for u t s,N G is obtained by summing constraints (3.29) and (3.30) which gives u t s,CG + u t s,N G = u t-1 s,CG + u t-1 s,N G and hence recursively

u t s,CG + u t s,N G = U 0 s,CG + U 0 s,N G .
These expressions enable us to replace continuous variables u t s,N G and u t s,CG by expressions that depend only on variables δ and γ. When considering |T | > 2 periods, these new expressions contain a high number of non-linearities (products of δ) which requires each a linearization variable: hence the number of additional variables required is equal to

N V (|T |) = |T | l=2 |T |! (|T | -l)!l! |K| l = (|K| + 1) |T | -1 -|T ||K|.
When focusing on a two-period framework (T = 2), the non-linear terms are direct products of variables δ 1 and δ 2 . We can hence linearize our formulation by adding only |K| 2 variables and 3|K| 2 constraints (see [START_REF] Fortet | Boole algebra and its application to operation research[END_REF]). We observe that variables γ 1 are not needed as the coverage range in the first period depends on the initial percentage of N G sites, and is hence already known.

Proposition 18. Constraints (3.5) and (3.6) can be replaced with the following non-linear equations in formulation M, for each site s ∈ S and each time period t ∈ T :

u t s,N G,N G = u t s,N G z t s,N G (6.3) u t s,N G,CG = u t s,N G (1 -z t s,N G ) (6.4)
Proof. See the proof of Proposition 9, the only difference here is that u t s,N G is not constant which means (6.3)-(6.4) are non-linear.

From Propositions 17 and 18, we hence obtain that continuous variables u can be expressed with the following equations depending on δ, γ and f , for each site s ∈ S and each time period t ∈ T :

u t s,N G,N G = U 0 s,N G + U 0 s,CG 1 - t i=1 1 - σ∈K c∈C f σ,c δ i σ γ i c z t s,N G u t s,CG + u t s,N G,CG = u t s,N G + u t s,CG = U 0 s,N G + U 0 s,CG if z t s,N G = 0, u t s,CG + u t s,N G,CG = u t s,CG = U 0 s,CG t i=1 1 - σ∈K c∈C f σ,c δ i σ γ i c if z t s,N G = 1.
For simplifying the subsequent notations, we denote the total number of subscribers ( s∈S U 0 s,CG + U 0 s,N G ) by UTOT. Consequently, formulation M with two generations and two periods can be reformulated without continuous variables, as follows:

min subcost + s∈S g∈G CMg(m 2 s,g -M 0 s,g ) + s∈S CANG(z 2 s,N G -Z 0 s,N G ) (6.5) s.t. σ 1 ∈K σ 1 f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 ) ≤ subcost s∈S U 0 s,CG , (6.6)
D 1 CG CAPCG(U 0 s,CG + U 0 s,N G )(1 -z 1 s,N G ) ≤ m 1 s,CG ∀s ∈ S, (6.7)
D 1 CG CAPCG U 0 s,CG (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 ) ≤ m 1 s,CG ∀s ∈ S, (6.8)
D 1 N G CAPNG (U 0 s,N G + U 0 s,CG σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )z 1 s,N G ≤ m 1 s,N G ∀s ∈ S, (6.9)
D 2 CG CAPCG (U 0 s,CG + U 0 s,N G )(1 -z 2 s,N G ) ≤ m 2 s,CG ∀s ∈ S, (6.10)
D 2 CG U 0 s,CG CAPCG   1 -   σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )     ≤ m 2 s,CG ∀s ∈ S, (6.11)
D 2 N G CAPNG   U 0 s,N G + U 0 s,CG   σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )     z 2 s,N G ≤ m 2 s,N G ∀s ∈ S, (6.12) s∈S
  U 0 s,N G + U 0 s,CG   σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )     z 2 s,N G ≥ QoE U T OT (6.13) γ t c ≤ 1 + Uc -α t-1 ∀t ∈ T , ∀c ∈ C, (6.14)
γ t c ≤ 1 + α t-1 -Lc ∀t ∈ T , ∀c ∈ C, (6.15
γ t c ∈ {0, 1} ∀t ∈ T , ∀c ∈ C (6.19) δ t σ ∈ {0, 1} ∀t ∈ T , ∀σ ∈ K (6.20)
Constraint (6.6) enables us to compute the subsidies cost subcost by using the expression from Proposition 17 for the number of CG subscribers (note that variable subcost will thanks to the minimization exactly be equal to the subsidies cost, but formulating with a ≤ sign is more amenable for writing the robust counterpart). Load balancing constraints (3.5) and (3.6), capacity constraints (3.7) and (3.8), subscriber dynamic constraints (3.29) and (3.30) and QoE threshold constraint (3.11) from formulation M are replaced by set of constraints (6.7)-(6.13). Constraints (6.7) and (6.10) impose that all subscribers on a site (which is a constant) have to be served by CG technology when N G is not installed. Constraints (6.8) and (6.11) state that CG subscribers have to be served by CG, which is dominated by previous constraints when N G is not installed. Constraints (6.9) and (6.12) impose that when N G is installed N G subscribers have to be served by N G. The same formulas for obtaining the number of N G subscribers are used in the QoE constraint (6.13). Constraints (6.14)-(6.16) ensure the definition of the coverage range. Constraints (6.17) ensure that one and only one subsidy from the set K is offered at each time period, the case when no subsidy is given being represented by σ = 0. Constraints (6.18)-(6.20) define the new variable.

Linearization and RLT cuts

We discuss next how the model presented in Section 6.2.2 is linearized. Notice that all products appearing in this formulation are products of binary variables. We linearize the model presented in Section 6.2.2 by applying Fortet Linearizations (see [START_REF] Fortet | Boole algebra and its application to operation research[END_REF]). For each σ 1 , σ 2 ∈ K 2 , s ∈ S, t ∈ T , we introduce the following new binary variables:

• χ σ,s for linearizing δ 1 σ z 1 s,N G in constraints (6.9),

• π t σ,s for linearizing δ t σ z 2 s,N G in constraints (6.12) and (6.13),

• η σ 1 ,σ 2 for linearizing δ 1 σ 1 δ 2 σ 2 in constraints (6.6) and (6.11)-(6.13),

• ζ σ 1 ,σ 2 ,s for linearizing δ 1 σ 1 δ 2 σ 2 z 2 s,N G = π 1 σ 1 ,s δ 2 σ 2 = π 2 σ 2 ,s δ 1 σ 1 = z 2 s,N G η σ 1 ,σ 2
in constraints (6.12) and (6.13).

Remark 18. The variable δ 2 and hence some of the variables above are also multiplied by γ 2 . As in formulation M, these products are not handled with Fortet linearizations, but by introducing variables δ 2 σ,c = γ 2 c δ 2 σ , for each σ ∈ K and each c ∈ C, and by replacing γ 2 c with σ∈K δ 2 σ,c (term equal to 1 if coverage range is c and 0 otherwise). We choose to keep γ 2 c δ 2 σ in the following for writing simplification. Now, we show how our formulation can be strengthened by applying Reformulation Linearization Techniques (RLT). Multiplying constraints (3.31) for t = 2 by variable z 1 s,N G for each site s ∈ S, we obtain:

σ∈K χ σ,s = z 1 s,N G ∀s ∈ S. (6.21)
Multiplying constraints (3.31) by variable z 2 s,N G for each site s ∈ S, we obtain:

σ∈K π t σ,s = z 2 s,N G ∀t ∈ T , ∀s ∈ S. (6.22)
Multiplying constraints (3.31) for t = 2 by variable δ 1 σ 1 for each subsidy σ 1 ∈ K, we obtain:

σ 2 ∈K η σ 1 ,σ 2 = δ 1 σ 1 ∀σ 1 ∈ K. (6.23)
Multiplying constraints (3.31) for t = 1 by variable δ 2 σ 2 for each subsidy σ 2 ∈ K, we obtain:

σ 1 ∈K η σ 1 ,σ 2 = δ 2 σ 2 ∀σ 2 ∈ K. (6.24)
Summing constraints (6.23) (or (6.24)) on set K, and applying constraints (3.31), we obtain:

σ 1 ∈K σ 2 ∈K η σ 1 ,σ 2 = 1. (6.25)
Multiplying constraints (6.23) by variable z 2 s,N G for each site s ∈ S, we obtain:

σ 2 ∈K ζ σ 1 ,σ 2 ,s = π 1 σ 1 ,s ∀s ∈ S, ∀σ 1 ∈ K. (6.26)
Multiplying constraints (6.24) by variable z 2 s,N G for each site s ∈ S, we obtain:

σ 1 ∈K ζ σ 1 ,σ 2 ,s = π 2 σ 2 ,s ∀s ∈ S, ∀σ 2 ∈ K. (6.27)
Finally, multiplying constraints (6.25) by variable z 2 s,N G for each site s ∈ S, we obtain:

σ 1 ∈K σ 2 ∈K ζ σ 1 ,σ 2 = z 2 s,N G ∀s ∈ S. (6.28)
Summarizing, the formulation presented in section (6.2) can be reinforced by adding constraints (6.22)-(6.28). We denote the corresponding linearized and reinforced formulation by M det,2period .

Robust formulation

In this section, we detail the static and adjustable robust counterparts for formulation M det,2period . The static counterpart is presented in Section 6.3.1. We show in Section 6.3.2 that this formulation can be formulated as a MILP that contains at most twice as many constraints as the nominal problem. Section 6.3.3 presents the adjustable counterpart.

Static robust counterpart

We now consider that the shifting function is uncertain and belongs to the uncertainty polytope F.

Let us recall that the shifting function is a discrete function associating to each couple (σ, c) ∈ K×C a reaction f σ,c ∈ [0, 1]. Therefore, the polytope F is a subset of the finite dimension space [0, 1] |K|•|C| . The realized shifting functions may be different in each period. We thus denote by f 1 ∈ F the shifting function realization in the first period and by f 2 ∈ F the shifting function realization in the second period. In a static framework, the decisions cannot be adapted to mitigate the effects of the uncertainty. Consequently, the static robust counterpart of formulation M det,2period can be formulated as follows.

min subcost + s∈S g∈G CMg(m 2 s,g -M 0 s,g ) + s∈S CANG(z 2 s,N G -Z 0 s,N G ) ( 6
σ 1 ∈K σ 1 f 1 σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 ) ≤ subcost s∈S U 0 s,CG ∀f 1 ∈ F, ∀f 2 ∈ F , (6.30)
D 1 CG U 0 s,CG (1 - σ∈K f 1 σ,c 1 δ 1 σ ) ≤ CAPCGm 1 s,CG ∀s ∈ S, ∀f 1 ∈ F, (6.31)
D 1 N G (U 0 s,N G + U 0 s,CG σ∈K f 1 σ,c 1 δ 1 σ )z 1 s,N G ≤ CAPNGm 1 s,N G ∀s ∈ S, ∀f 1 ∈ F , (6.32)
D 2 CG U 0 s,CG CAPCG   1 -   σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 )     ≤ m 2 s,CG ∀s ∈ S, ∀f 1 ∈ F , ∀f 2 ∈ F , (6.33)
D 2 N G CAPNG   U 0 s,N G + U 0 s,CG   σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 )     z 2 s,N G ≤ m 2 s,N G ∀s ∈ S, ∀f 1 ∈ F , ∀f 2 ∈ F , (6.34) s∈S   U 0 s,N G + U 0 s,CG   σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 )     z 2 s,N G ≥ QoE U T OT, ∀f 1 ∈ F, ∀f 2 ∈ F . (6.35)
Let us denote this formulation by M stat . Being a robust mixed-integer linear programming with polyhedral uncertainty, formulation M stat has an infinite number of constraints.

Remark 19.

As for the deterministic model, formulation M stat can be linearized and reinforced by constraints (6.22)-(6.28).

Constraints dominance

We observe that the previous formulation contains constraints involving quadratic dependencies on f . This is the case for each constraint that involves the numbers of subscribers to each offer in the second period, i.e. constraints (6.30), (6.33), (6.34) and (6.35). Handling constraints with non-linear dependencies of the uncertain parameters may not be easy in general. Fortunately, we show in this section that the specific structure of our constraints is simple enough to lead to a direct reformulation based on the dominance of set F by two vectors denoted by f and f . In what follows, let δ represent the value of δ in a feasible solution of M stat and let σ denote the subsidy offered in that solution. Similarly, let γ2 represent the value of γ 2 in a feasible solution of M stat and let c2 denote the range of coverage in the second period in that solution. Our reformulation is based on the following properties satisfied by any feasible solution of formulation M stat :

Proposition 19. The term σ∈K f 1 σ,c 1 δ1 σ is equal to f 1 σ1 ,c 1 .
Proof. This comes directly from constraints (3.31), σ1 being the index of the only non-zero component of δ1 .

Proposition 20. The term

σ∈K c∈C f 2 σ,c δ2 σ γ2 c is equal to f 2 σ2 ,c 2 .
Proof. This result comes from constraints (3.31) and (6.16), σ2 being the index of the unique non-zero component of δ2 and c2 being the index of the unique non-zero component of γ2 .

These two simple results enable us to replace all robust constraints by equivalent sets of constraints, involving at most the two aforementioned vectors f and f , which are defined as follows for each subsidy offered σ ∈ K and each coverage range c ∈ C:

• the weakest possible reaction is f σ,c = min f ∈F f σ,c , • the strongest possible reaction is f σ,c = max f ∈F f σ,c .
Next, we present reformulations for the constraints that are linear in the uncertainty f . Proposition 21. Constraints (6.31) are satisfied if and only if the following constraints are satisfied:

D 1 CG U 0 s,CG (1 - σ∈K f σ,c 1 δ 1 σ ) ≤ CAP CG m 1 s,CG , ∀s ∈ S. (6.36)
Proof. We see that constraints (6.31) are equivalent to max

f 1 ∈F D 1 CG U 0 s,CG (1 - σ∈K f 1 σ 1 ,c 1 δ 1 σ ) ≤ CAP CG m 1 s,CG ∀s ∈ S, ⇔ D 1 CG U 0 s,CG (1 -min f 1 ∈F σ∈K f 1 σ,c 1 δ 1 σ ) ≤ CAP CG m 1 s,CG ∀s ∈ S.
From Proposition 19 and the definition of f , we have

σ∈K f σ,c 1 δ1 σ = f σ1 ,c 1 = min f 1 ∈F f 1 σ1 ,c 1 = min f 1 ∈F σ∈K f 1 σ,c 1 δ1 σ .
which means constraints (6.31) are equivalent to constraints (6.36).

Proposition 22. Constraints (6.32) are satisfied if and only if the following constraints are satisfied:

D 1 N G (U 0 s,N G + U 0 s,CG σ∈K f σ,c 1 δ 1 σ ) ≤ CAP CG m 1 s,CG ∀s ∈ S. (6.37)
Proof. The proof relies on the definition of f and on arguments similar to those used in the proof of Proposition 21.

Next, we focus on the constraints of M stat that involve quadratic dependencies on f . Proposition 23. Constraints (6.33) are satisfied if and only if the following constraints are satisfied:

D 2 CG U 0 s,CG CAPCG   1 -   σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )     ≤ m 2 s,CG ∀s ∈ S. (6.38)
Proof. First, we see that if constraints (6.33) are satisfied, then constraints (6.38) are satisfied since f ∈ F.

Reciprocally, let us assume that constraints (6.38) are satisfied. Due to Propositions 19 and 20, we know that:

σ 1 ∈K f 1 σ 1 ,c 1 δ1 σ + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ2 σ 2 γ2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ1 σ ) = f 1 σ1 ,c 1 + f 2 σ2 ,c 2 (1 -f 1 σ1 ,c 1 ).
To simplify notations, let us denote f 1 σ1 ,c 1 and f 2 σ2 ,c 2 by x and y respectively. We also denote f σ1 ,c 1 by x, f σ1 ,c 1 by x, f σ2 ,c 2 by y and f σ2 ,c 2 by y.

Recalling that (x, y) ∈ [0, 1] 2 , we wish to find out where function g(x, y)

= x + y(1 -x) = x + y -xy defined on (x, y) ∈ [x, x] × [y, y] ⊆ [0, 1] 2 reaches its minimal value. First, notice that g(x, y) = x + (1 -x)y ≥ x + (1 -x)y = g(x, y) ∀x ∈ [x, x], ∀y ∈ [y, y],
and symmetrically g(x, y) ≥ g(x, y), ∀x ∈ [x, x], ∀y ∈ [y, y]. Consequently, g(x, y) ≥ g(x, y), ∀x ∈ [x, x], ∀y ∈ [y, y], and we thus have:

max f 1 ∈F ,f 2 ∈F D 2 CG U 0 s,CG CAP CG 1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 ) = D 2 CG U 0 s,CG CAP CG 1 - min f 1 ∈F ,f 2 ∈F σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ ) ≤ D 2 CG U 0 s,CG CAP CG 1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ ) ≤ m 2 s,
  U 0 s,N G + U 0 s,CG   σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )     ≥ QoE U T OT. (6.39)
Proof. The proof relies on arguments similar to those used in the proof of Proposition 23.

Proposition 25. Constraints (6.34) are satisfied if and only if the following constraints are satisfied:

D 2 N G CAPNG   U 0 s,N G + U 0 s,CG   σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 )     ≤ m 2 s,N G ∀s ∈ S (6.40)
Proof. The proof relies on studying the maximum of function g and on arguments similar to those used in the proof of Proposition 23.

We consider next constraints (6.30) which require an argument slightly more involved.

Proposition 26. Constraints (6.30) are satisfied if and only if the following constraints are satisfied:

σ 1 ∈K σ 1 f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ ) ≤ subcost s∈S U 0 s,CG (6.41
)

σ 1 ∈K σ 1 f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f σ 1 ,c 1 δ 1 σ 1 ) ≤ subcost s∈S U 0 s,CG (6.42)
Proof. First, we see that if constraints (6.30) are satisfied, constraints (6.41) and (6.42) are satisfied since f ∈ F and f ∈ F.

Reciprocally, let us assume that constraints (6.41) and (6.42) are both satisfied: due to Propositions 19 and 20, we know that

σ 1 ∈K σ 1 f 1 σ 1 ,c 1 δ1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f 2 σ 2 ,c 2 δ2 σ 2 γ2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ1 σ 1 ) = σ1 f 1 σ1 ,c 1 + σ2 f 2 σ2 ,c 2 (1 -f 1 σ1 ,c 1 ).
We use the same notations as those introduced in the proof of Proposition 23. In addition, we denote σ1 by a and σ2 by b. We wish to find out where function h(x, y) = ax + by(1 -x) defined on x ∈ [x, x] × [y, y] ⊆ [0, 1] 2 reaches its maximal value with a and b positive reals. First notice that we have:

h(x, y) = ax + by(1 -x) ≤ ax + by(1 -x) = h(x, y) ∀x ∈ [x, x], ∀y ∈ [y, y].
Hence, our function is maximal for y = y. With y fixed to y, h(x, y) becomes a linear function of x defined on [x, x]. Therefore, We thus have for each f 1 ∈ F, f 2 ∈ F:

h(x, y) ≤ max {h(x, y), h(x, y)} ∀x ∈ [x, x]
σ 1 ∈K σ 1 f 1 σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f 2 σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 ) ≤ max σ 1 ∈K c 1 ∈C σ 1 f σ 1 ,c 1 δ 1 σ 1 + σ 2 ∈K c 2 ∈C σ 2 f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K c 1 ∈C f σ 1 ,c 1 δ 1 σ 1 ), σ 1 ∈K c 1 ∈C σ 1 f σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C σ 2 f σ 2 ,c 2 δ 2 σ 2 γ 2 c 2 (1 - σ 1 ∈K c 1 ∈C f σ 1 ,c 1 δ 1 σ 1 ) ≤ subcost s∈S U 0 s,CG
, which means that constraints (6.30) are satisfied.

Summarizing the above results, we have shown that formulation M stat is equivalent to the following mixed-integer linear programming, with a finite number of constraints:

Adjustable robust counterpart

In this section, we consider a framework in which the telecommunication company can take benefit from the knowledge of the uncertainty realization in the first period when deciding the subsidy offered in the second period. We obtain a two-stage model where the company can adapt to the uncertainty through a second-stage decision: the amount of subsidy offered in the second period. We model this decision by variables δ 2 σ (f 1 ) defined for each f 1 ∈ F. Let us recall that all decisions concerning network investments are taken as planning decisions and considered to be taken in the first stage, which means that δ 2 σ (f 1 ) is the only second-stage decision. This decision is often called the recourse in the robust optimization literature.

Plugging the recourse variables into the robust model leads to a mixed-integer formulation with an infinite number of variables since one variable δ(f ) arises for each f ∈ F. Therefore, we propose an adjustable robust partition method in the line of [START_REF] Bertsimas | Reformulation versus cutting-planes for robust optimization[END_REF], partitioning our uncertainty set F into a finite number L of parts. Notice that, unlike [START_REF] Bertsimas | Reformulation versus cutting-planes for robust optimization[END_REF], we partition the uncertainty set from the start. We denote the index set of the partition by L = {1, . . . , L}. We hence have F = ∪ L l=0 F(l) with ∀l ∈ L, l ∈ L \ {l}, F(l) ∩ F(l ) = ∅ and consider the piecewise constant recourse defined by: δ 2 (f ) = δ 2 (f ) ∀f, f ∈ F(l), ∀l ∈ L Thus, we replace δ 2 σ (f ) by δ 2 σ,l which indicates the recourse decision taken when f ∈ F(l) for each l ∈ L. Consequently, the robust adjustable counterpart of formulation M det,2period can be written as follows: ), (6.7), (6.10), (6.14) -(6.20), (6.31) -(6.32),

σ 1 ∈K σ 1 f 1 σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C σ 2 f 2 σ 2 ,c 2 δ 2 σ 2 ,l γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ ) ≤ subcost s∈S U 0 s,CG
∀l ∈ L, ∀f 1 ∈ F (l), ∀f 2 ∈ F , (6.44)

D 2 CG U 0 s,CG CAPCG   1 -   σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 ,l γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ )     ≤ m 2 s,CG
∀s ∈ S, ∀l ∈ L, ∀f 1 ∈ F(l), ∀f 2 ∈ F , (6.45)

D 2 N G CAPNG   U 0 s,N G + U 0 s,CG   σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 ,l γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ )     z 2 s,N G ≤ m 2 s,N G
∀s ∈ S, ∀l ∈ L, ∀f 1 ∈ F(l), ∀f 2 ∈ F , (6.46) Let us denote this formulation by M adj,L where L is the number of parts. Formulation M adj,L is obtained by replacing each set of constraints involving the second period in formulation M stat (constraints (6.30),(6. f σ,c , for each l ∈ L. We notice that formulation M adj,1 is equivalent to formulation M stat .

s∈S   U 0 s,N G + U 0 s,CG   σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ + σ 2 ∈K c 2 ∈C f 2 σ 2 ,c 2 δ 2 σ 2 ,l γ 2 c 2 (1 - σ 1 ∈K f 1 σ 1 ,c 1 δ 1 σ 1 )     z 2 s,N G ≥ QoE U T
Remark 20. As for the deterministic and static models, formulations M adj,L can be linearized and reinforced by RLT equalities. The only slight difference is that for each linearization or equality implying variables δ 2 σ in the deterministic model, we have now L constraints corresponding to each part.

Numerical experiments

In this section, we assess numerically our static and adjustable models. We first describe the uncertainty set used in the experiments in Section 6.4.1. The instances used and computational settings are described in Section 6.4.2. Then, scalability and economic results are presented in Section 6.4.3.

In particular, we will assess the relevance of the adjustable models compared to the deterministic and static ones. For the adjustable models, we consider three different values for L, {2, 4, 8}, to assess the scalability and economic relevance of refining the number of parts in the partition. For each model, we assess both model solution cost and simulated cost of the first-stage. The simulated cost of the first-stage is obtained by discretizing the uncertainty set in 200 values and solving 200 optimization problems, each of which considers the first-stage decisions fixed, the shifting function realization of the first period equal to the corresponding value and using the static model for finding the best second-stage decision.

Design of the uncertainty set

Let fσ,c denote the nominal value of f σ,c . We define an uncertainty set that enables us to control the variation around this value. Letting Γ denote the amplitude of the variation, we define

F = f ∈ [0, 1] |C|•|K| |(1 -Γ) fσ,c ≤ f σ,c ≤ (1 -Γ) fσ,c + Γ, c ∈ C, σ ∈ K .
An illustration of F for a nominal function corresponding to the reference example from Chapter 3 and a deviation of Γ = 0.25 is provided in Figure 16. We see that the uncertainty set is not symmetric around the nominal value fσ,c as the downward deviation from fσ,c can be as large as Γ fσ,c while the upward deviation is bounded by Γ(1 -fσ,c ) for σ ∈ K and c ∈ C, with these deviations depending on the nominal value. This definition of the uncertainty set enables us to control that each possible reaction belongs to [0, 1].

For the adjustable model, we need to partition F into L parts. We choose to define for each l in {1, • • • , L}

F(l) = f ∈ [0, 1] |C|•|K| |(1 -Γ) fσ,c + l -1 L Γ ≤ f σ,c ≤ (1 -Γ) fσ,c + l L Γ, c ∈ C, σ ∈ K ⊆ F.
An illustration of the partition for L = 3 and the example from Figure 16 is provided in Figure 17.

Instance parameters

We aim to assess the different models presented in Section 3.3 on a realistic instance for three different amplitude values Γ. We use the same 100 sites instance as in Section (3. We use the uncertainty set for f defined by these nominal values and an amplitude value Γ ∈ {0.25, 0.30, 0.35}. Results obtained with each formulation are presented in Table 28. The value of the best solution found and the solving time in seconds are provided respectively in columns "sol" and "time" of Table 28. Column "first-stage" stands for the value of the subsidy offered in the first period and multi-column "second-stage" for the value of the subsidy offered in the second period. For the adjustable models, each line presents second-stage values ordered from lowest to highest reaction cases.

Results

On a scalability viewpoint, we observe that the convergence of the branch-and-bound procedure is obtained in less than 2 minutes for the deterministic, static, and adjustable (L = 2) models for each amplitude value. For each model, the larger the amplitude is, the faster the convergence is. We also observe that whatever the amplitude is, the static model is not harder to solve than the deterministic model. Refining the number of parts considerably increases the model size (in terms of constraints and variables). Our results enlighten the lack of scalability of such refinements. For Γ = 0.25 and L = 8, the solver does not converge within the two-hour time limit.

Next, we observe that the deterministic decision for the first-level (200 e) is never taken by any of the robust frameworks. We see that for an amplitude Γ = 0.25, the first-stage decision for the subsidy proposal is different between the static and adjustable models: static (250 e) and adjustable (350 e for all values of L). For Γ = 0.30 deviation, the first-stage decisions for the subsidy proposal are 300 e for the static model and 350 e for all adjustable models. These differences are explained by an impact on network installations (fewer installations) in the adjustable cases. For Γ = 0.35 deviation, the decision for the static and all adjustable models is the same: 350 e. From our results, we conclude that using the 2 parts model (L = 2) is sufficient since it converges a lot faster than using 4 or 8 parts and provides the same first-stage solution in each case.

To estimate the costs, we use the first-stage decisions given by the three different models, deterministic, static, and adjustable (with L = 2), and generate 200 scenarios for the corresponding uncertainty realization by partitioning the uncertainty set into intervals of equal length. We then solve one optimization problem for each of the 200 scenarios to compute the best second-period decision. Each of these problems thus amounts to solve a nominal variant of the problem where the first-stage decisions are fixed to the values provided by the model and f 1 depends on the considered scenario.

The simulations costs (curve formed by all generated scenarios) are plotted for each value of Γ on Figures 18,19 and 20. The worst-case costs are given under column "worst-case costs" in Table 29. The curves show us that these worst-case costs are obtained for the scenarios where the uncertainty is the lower, as these functions are mostly decreasing. We see that for each amplitude value, in the worst-case, the first-stage decision of the adjustable model is the best one.

From an economic viewpoint, we first notice from Table 28 that the optimal cost from the deterministic framework (6999 ke) is around 30% lower than the best solution found (obtained with the adjustable model) in the worst-case (for Γ = 0.25). This can be explained by computing the worst-case for the QoE threshold when Γ = 0.25 and the decisions taken by the deterministic model are imposed. This value is equal to 0.71 while the demanded threshold is 0.8. Deterministic decisions lead hence to infeasibility in the robust context, which requires higher subsidies for robust decisions. The impact on the cost in a robust context is three-fold. The cost indeed increases,

• since the subsidy proposal is higher,

• since these subsidies have a higher nominal effect (more reactions due to decisions),

• if the subscribers react better than expected (more reactions due to uncertainty). Furthermore, we observe that for Γ = 0.35, the deterministic first-stage decision is infeasible (see Table 29 and Figure 20) when the uncertainty realization is lower than 20% (first 40 scenarios). Indeed, the maximal nominal reaction for the second period is 90% which means the worst-case is 58.5%. With an initial 4G subscribers percentage of 40%, this is not enough for reaching 80% of subscribers being 4G and hence the QoE threshold of 80% of subscribers being 4G served by 4G is infeasible (even when all sites are equipped).

Conclusion

In this chapter, we have introduced and strengthened a new formulation for the two periods and two generations MIS using only integer variables. Assuming that the discrete shifting function can take any value in a given polytope, and optimizing against the worst-case outcome, we have proposed a robust counterpart for the problem. We have handled integer recourse variables by partitioning the uncertainty set while the non-linear dependencies on the uncertain parameters have been tackled by a careful analysis of dominating scenarios. Numerical experiments have been performed for static and adjustable robust frameworks on a 100 sites instance, with an uncertainty set controlling variation around the nominal value and parametrized by an amplitude Γ. Our results have illustrated the scalability of the different robust models for 100 sites as well as the economical relevance of the static and adjustable first-stage decisions over the deterministic one. These decisions can lead to saving costs as high as 30% of the total costs in the case Γ = 0.3, while the deterministic solution becomes infeasible for Γ = 0.35. Our results have also underlined the impact of the quality of experience threshold, which is responsible for the higher subsidies decisions and the higher costs it involves.

Chapter 7

Conclusion 7.1 Synthesis

This thesis has introduced several strategic decision problems faced by a telecommunication company when planning optimally its network and marketing investments. Approximated and exact solving methods have been provided for each of the corresponding optimization problems:

• For the mobile investments strategies problem (MIS), we have designed:

a mixed integer linear formulation, a formulation using only binary and integer variables, provided for the two-period case, heuristic methods for large instances based on the following scheme. First, selecting the subscriber dynamic decisions, either by a VNS algorithm or a restricted enumeration. Second, solving the subproblem, either by mixed-integer formulation or by a dynamic programming method when temporal constraints are not imposed.

• For the problem with sites coverage overlappings and new sites installation (GEO-MIS) we have provided a mixed-integer formulation.

• For the more-than-two generation (MG-MIS) problem, as well as the problem with refarming constraints (R-MG-MIS), we have designed:

a mixed-integer linear formulation, heuristics based on VNS algorithms for selecting the subscriber dynamic decisions, and a site decomposition method for the resulting problem.

• For the static robust counterpart of MIS, we have reduced the problem to the solving of a mixed integer linear formulation similar to the formulation for the two-period deterministic case, where values for reaction of the subscribers have been replaced by the worst-case values.

• For the adjustable robust counterpart of MIS, we have used a fixed partition method, partitioning the reaction of the first period in K parts. On each part, the recourse is assumed constant (piece-wise linear recourse), which enables us to do the same transformation as for the static counterpart and hence to solve it as a mixed integer linear formulation.

The mixed integer linear formulations have been reinforced with several valid inequalities specific to the problem, based on upper and lower bounds on number of subscribers and on properties of coverage ranges. The linearization has been reinforced thanks to the application of the Reformulation Linearization Techniques.

The models presented above and the dedicated solving methods developed have enabled us to perform case-studies for answering strategic key questions for Orange.

CHAPTER 7. CONCLUSION

The first case study has been designed on 3G/4G instances and has enlightened and quantified the benefit for the operator from, when possible, deploying quickly the newest technology for attracting subscribers towards this technology. When the full deployment is not possible due to budget restrictions, the subsidies expenses are considerably increased. The multi-generation case-study quantifies the impact of different network and subscriber policies. Our results have enlightened in particular the benefit that could be raised by differentiating the subsidy proposals according to the different generations of the subscribers. This enables indeed to measure the impact of targeting marketing investments towards the subscribers served by the most saturated network technologies. The impact of taking into account sites coverage overlappings has also been quantified. In what concerns the refarming strategies, the models can assess if a planned refarming strategy is feasible and provide a subscriber dynamic trajectory ensuring at minimal cost the feasibility. Results of the corresponding case study enlighten the important effort on marketing investments that telecommunication companies should perform in order to reduce the traffic on older network technologies and hence be able to refarm.

In collaboration with a developer's team from Orange Labs, a decision-aid prototype has been conceived to encapsulate the algorithms developed during this thesis. The aim of the prototype is to facilitate the use of these algorithms by decision-takers. The tool hence enables the decisiontakers to launch an optimization, to get back the results and to analyze these results through graphical visualizations.

Perspectives

Two main perspectives are derived from this thesis. First, a research perspective: the handling of the competition between telecommunication operators through the lens of game theory. Second, the operational use of the designed methods.

The competition between operators can be treated through the models developed in this thesis thanks to new incomers parameters and strategic guidelines, but it requires to know information about the decisions taken by the other operators. In further research, analysis based on game theory should be developed for modeling the competition. The information in such games is incomplete, as the operator does not know all information about the deployment and decisions from its competitors.

As for operational use and deployment of the designed algorithms, additional constraints may be required to reflect specific contexts of Orange affiliates. These constraints would require slight adaptation of the designed models. The tool designed during this thesis is a prototype whose main utility is to enlighten the potential of such models. An integration of this tool to a portal of tools developed by Orange Labs and made available to Orange affiliates is scheduled to take place in 2021.

  4 KB/s 64 KB/s 2 MB/s 1 GB/s > 1 GB/s Table

  4 KB/s 64 KB/s 2 MB/s 1 GB/s > 1 GB/s Table

Figure 3 :

 3 Figure 3: Illustration of an over-dimensioning case due to absence of consideration of overlappings.

Figure 4 :

 4 Figure 4: Network representation of the MIS problem (three sites, two time periods).

  ) refer to the initial conditions. Finally, constraints (3.18)-(3.23) define the domain of the variables. Section 3.3.3 details function f and linear modeling of constraints (3.14).

Figure 5 Figure 5 :

 55 Figure 5: Example of upgrade function

. 42 )Remark 4 .

 424 We denote this formulation by M. Constraints(3.29) and(3.30) are the linearizations respectively of constraints(3.26) and(3.27). Constraints(3.31) ensure that one and only one subsidy from the set K is offered at each time period, the case when no subsidy is given being represented by σ = 0. Constraints (3.32) and (3.33) ensure that, for each time period, variables δ t σ,c are set according to the coverage. Constraints (3.32) (respectively (3.33)) set all δ related to a range to 0 if the coverage is greater (resp. smaller) than the upper (resp. lower) bound of the range. Constraints (3.34)-(3.36) are the typical linearizations of the products of a binary variable with a continuous one. Constraints (3.37)-(3.42) define the domain of all variables in the formulation. We can define the initial range of coverage c init as the range containing the initial sites coverage (depending on values Z 0 s,N G ∀s ∈ S). As sites coverage values are increasing, we can use set C = {c init , . . . , C} instead of C, hence reducing the formulation size.

Figure 6 :

 6 Figure 6: Evolution of the coverage, subsidies decisions and reactions over the time horizon (optimal solution of 50 sites suburban instance).

Figure 7 :

 7 Figure 7: Evolution of the costs over the time horizon (optimal solution of 50 sites suburban instance).

  coverage (% of sites) Amount of subsides offered (ke) Proportion of subscribers who upgrade

Figure 8 :Figure 9 :

 89 Figure 8: Evolution of the coverage, subsidies decisions and reactions over the time horizon (solution of 50 sites suburban instance) when cost equilibrium constraints are imposed.

  for the load balancing policies, we introduce the parameter CP o,g , o ∈ O, g ∈ G. For each subscription type o ∈ O, this parameter indicates: • when CP o,g = 0: a technical incompatibility to serve the subscribers to subscription type o ∈ O by technology g ∈ G, • when CP o,g > 0: the technical possibility to serve the subscribers to subscription type o ∈ O by technology g ∈ G. In this case, the subscribers to subscription type o are served by the technology(ies) having the highest priority (represented by the value CP o,g ) among the available technologies.

  g stands for the initial presence (yes/no) of network technology g ∈ G on site s ∈ S, -U 0 s,o is the initial number of subscribers on site s ∈ S to subscription type o ∈ O, -D t o,g is the unitary demand of a subscriber to subscription type o ∈ O served by technology g ∈ G at time period t ∈ T , • Unmodified parameters: -CM g is the cost of adding a module of a technology g ∈ G, -M 0 s,g stands for the initial number of modules of technology g ∈ G on site s ∈ S, -M g stands a technical upper bound on the number of modules of technology g ∈ G, -N t g is the percentage of incoming user subscribers to technology g ∈ G at time period t ∈ T , -CAP g is the capacity of adding a module of a technology g ∈ G, f σ,c is the reaction to the subsidy offered σ ∈ K under range of coverage interval c ∈ C, -L c stands for the lower bound of coverage range c ∈ C, -U c stands for the upper bound of coverage range c ∈ C, α 0 stands for the sites coverage at the beginning of the time horizon, α t stands for the sites coverage at the end of time period t ∈ T , α and QoE are the thresholds fixed as strategic guidelines, • Parameters introduced for the levers: -InvA g and InvM g indicate, respectively, if a network technology g ∈ G or a module of network technology g ∈ G can be installed or not, -CP o,g , o ∈ O, g ∈ G denotes the compatibility/priority matrix, modeling the load balancing rules, f σ,c,o is the reaction of subscribers to subscription type o ∈ O to the subsidy offered σ ∈ K under range of coverage interval c ∈ C.

For

  each band and each network technology, let us denote by ω t g,b the maximum spectrum allocated to technology g ∈ G on band b ∈ B at time period t ∈ T . For each band b ∈ B, we have g∈G ω t g,b ≤ Ω t b (impossible to allocate more than the total spectrum holding). This means that on a given band b ∈ B for increasing one ω t g,b we may need to decrease another ω t g ,b , which is the key of a refarming process. An example of such refarming strategies (defined by the values for ω t g,b and Ω t b ) is provided in Table 16 for a framework with three network technologies and three frequency bands. Rows SH represent the values of the spectrum holding Ω t b while the other rows provide the respective values of ω t g,b .

. 36 ) 7 .

 367 Proposition We can reinforce formulations M M G and M M G,ref arm by adding valid inequalities (3.45)-(3.48).

Figure 11 :

 11 Figure 10: Ranges of two telecommunication sites

Figure 12 :Figure 13 :

 1213 Figure 12: Two existing sites and one future site.

Figure 14 :Figure 15 :

 1415 Figure 14: Decision taken when differentiation in subsidies enabled

  observe that we have (|T | • (|K| -1) • (|C| -1) solution costs to evaluate for each iteration of the local search. Assuming |T | = 5, |C| = 3, |K| = 10, we have hence 90 problems to solve for each iteration of the local search.

9 k ← 1 ; 10 ( 13 k

 911013 σ, c) ← (σ min , c min ) ; 11 bestcost ← cost(σ min , c min ) ; 12 else ← k + 1

First, let us

  look at the simplification of formulation M M G for problem M G -M IS(σ, c). Starting from formulation M M G , we replace: • the subsidies cost in the objective by constants upgradecost, • variables u t s,o for each subscription type o ∈ O and each site s ∈ S at each time period t ∈ T by the constants U t s,o • constraints (4.9)-(4.10) and (4.13)-(4.18) with (5.15)-(5.16). Now, this formulation for problem M G -M IS(σ, c) can be extended for tackling problem R -M G -M IS(σ, c), as follows. The network part of the objective is modified as in (4.34) and the refarming constraints (4.31), (4.32), (4.33) and (4.35) are added to the formulation.

  Consequently, we are able to solve problem M G -M IS(σ, c) by solving formulations M bl M G for all blocks bl ∈ {1, . . . , N bl }: the cost of problem M G -M IS(σ, c) is equal to obj(M bl M G ) + upgradecost.

( 3 .

 3 2) -(3.4), (3.12) -(3.13), (3.16) -(3.19)

  and h(x, y) ≤ max {h(x, y), h(x, y)} ∀x ∈ [x, x], ∀y ∈ [y, y].

  min {(6.29) s.t. (3.2) -(3.4), (6.7), (6.10), (6.36) -(6.42), (3.31) -(3.41)}

  . (3.2) -(3.4), (3.12) -(3.13), (3.16) -(3.19

  [START_REF] Bazelon | Spectrum value[END_REF])-(6.35),(3.31)) with L sets of constraints -one for each part. We observe that in each part F(l), l ∈ L, constraints (6.44)-(6.47) can be reformulated in the same way as for the static model, with in the first period f and f replaced by f (l) and f (l) defined by f σ,c (l) = min f ∈F (l) f σ,c and f σ,c (l) = max f ∈F (l)

Figure 16 :Figure 17 :

 1617 Figure 16: Example of uncertainty set with reference function and Γ = 0.25 (projected on a given range c = [0.75, 1]).

Figure 18 :Figure 19 :

 1819 Figure 18: Simulations with first-stages imposed for a deviation Γ = 0.25

Figure 20 :

 20 Figure 20: Simulations with first-stages imposed for a deviation Γ = 0.35

Table 1 :

 1 47 %, cette croissance étant particulièrement importante en Afrique (65 %). Une expansion du réseau est ainsi nécessaire pour soutenir une telle augmentation du trafic.

	Service	2015	2018
	Vidéos Youtube regardées	2.78 M 4.3 M
	Heures de Netflix regardées	69444	266000
	Consultation d'Instagram	38000	174000

Utilisations de quelques services sur internet par minute (d'après [2])

Table 3 :

 3 Number of usages of some services happening worldwide on the internet per minute (from [2]).

	Service	2015	2018
	Youtube videos viewed 2.78 M 4.3 M
	Netflix hours watched	69444	266000
	Instagram scrolling	38000	174000

  Commercial use of cell phones has started with 2G technologies (GSM and EDGE) in the early 1990s. This technology has enabled progress in communications and the use of smaller devices compared to the analogical ones, which have contributed to the explosion of mobile communications. A new communication service, the SMS (Short Message Service), also appeared with 2G. Following the evolution of usages and the development of the internet, 2G technology has progressively evolved around the year 2000 for enabling light internet access. New performances for massive internet usages were reached with 3G technology (UMTS), enabling new usages (media sharing in social networks, etc.). 4G technology (LTE) has improved the throughput for such services and has reduced the latency. 4G technology has also enabled us to watch live streaming events in high definition and to play online video games.

	CHAPTER 2. MOBILE INVESTMENTS STRATEGIES CONTEXT
	2.1.1 A brief history of mobile telecommunication generations: from
	2G to 5G

1.1. Key stakes of 5G technology are provided in Section 2.1.2. The problem of how dealing with older technologies is treated in Section 2.1.3.

Table 6 :

 6

Approximated range radius (in km) for three frequencies for three density contexts

Table 7 :

 7 Spectrum holdings in France (Source: ARCEP).

	Frequency Band \Operator Orange France	SFR	Bouygues Telecom Free Mobile
	700 MHz	2x10 MHz	2x5 MHz	2x5 MHz	2x10 MHz
	800 MHz	2x10 MHz	2x10 MHz	2x10 MHz
	900 MHz	2x10 MHz	2x10 MHz	2x9.8 MHz	2x5 MHz
	1800 MHz	2x20 MHz	2x20 MHz	2x20 MHz	2x15 MHz
	2100 MHz	2x19.8 MHz	2x19.8 MHz	2x14.8 MHz	2x5 MHz
	2600 MHz	2x20 MHz	2x15 MHz	2x15 MHz	2x20 MHz

  are hence discretized into the table of values shown in Table8, which constitutes our reference upgrade function.

	Coverage level \Subsidies (in e)	0	100 150 200 250 300 350 400 450 500
	low	0	0	0	0	0	0	0	0	0	0
	medium low	0.5	5	12	21	30	40	42	43	44	45
	medium high	5	10	20	30	40	50	60	62	64	65
	high	10	20	33	45	58	70	80	83	87	90

Table 9 :

 9 Root gap values for 12 instances (4 sizes, 3 densities) tested with each family of valid inequalities

	Instance					Root gap
	N S density M + (3.43) + (3.44) + (3.45) + (3.46) + (3.47) + (3.48) + (3.43)-(3.48)
	50	R	25	25	25	19	25	25	25	19
		S	32	32	32	24	32	32	32	24
		U	61	58	61	45	61	61	55	27
	100	R	26	26	26	20	26	26	26	20
		S	31	32	31	24	31	31	31	23
		U	62	59	62	47	62	62	57	28
	150	R	28	25	25	20	26	25	25	20
		S	38	31	31	24	31	32	31	24
		U	63	59	62	47	62	62	57	29
	200	R	28	25	24	18	24	24	25	18
		S	36	31	31	23	30	32	30	23
		U	63	59	62	46	62	62	56	29

Table 10 :

 10 Best solution for 12 instances (4 sizes, 3 densities) tested with each family of valid inequalities

	Instance				Best solution found by CPLEX
	N S density	M	+ (3.43) + (3.44) + (3.45) + (3.46) + (3.47) + (3.48) + (3.43)-(3.48)
	50	R	4173	4103*	4103*	4103*	4103*	4103*	4103*	4103*
		S	3458	3458*	3458*	3458*	3458*	3458*	3458*	3458*
		U	2021*	2021*	2021*	2021*	2021*	2021*	2021*	2021*
	100	R	8347	8347	8347	8347	8401	8347	8347	8347
		S	7036	6902	6861	6861	6861	6861	6861	6861
		U	3864	3861*	3861*	3861*	3861*	3861*	3861*	3861*
	150	R	12783	12308	12247	12242	12344	12247	12263
		S	11179	10049	10027	9990	10049	10146	10030	9990
		U	5692	5522*	5522*	5522*	5522*	5522*	5522*	5522*
	200	R	17021	16309	16167	16036	16127	16036	16318
		S	14266	13305	13305	13094	13094	13567	13221
		U	7828	7616	7616	7616	7619	7616	7619	7616

Table 11 :

 11 Final gaps for 12 instances (4 sizes, 3 densities) tested with each family of valid inequalities

	Instance					Final gap
	N S density	M	+ (3.43) + (3.44) + (3.45) + (3.46) + (3.47) + (3.48) + (3.43)-(3.48)
	50	R	6.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00
		S	5.97	0.00	0.00	0.00	0.00	0.00	0.00	0.00
		U	0.00	0.00	0.00	0.00	0.00	0.00	0.00	0.00
	100	R	10.62	4.52	3.13	3.59	6.33	1.90	6.46	1.14
		S	14.92	4.81	3.17	2.55	3.60	3.67	4.37	2.50
		U	7.18	0.00	0.00	0.00	0.00	0.00	0.00	0.00
	150	R	16.71	9.65	5.62	4.43	7.91	6.87	6.87	4.12
		S	20.72	10.49	4.34	3.91	4.13	10.45	7.71	3.47
		U	7.22	0.00	0.00	0.00	0.00	0.00	0.00	0.00
	200	R	16.73	10.53	7.99	3.59	10.55	8.84	9.80	2.48
		S	18.85	10.06	12.22	2.77	11.03	13.59	12.28	3.06
		U	7.73	1.83	1.01	0.49	1.96	1.86	2.27	0.07

Table 12 :

 12 Reaction of the subscribers (in %) on Technology-Reluctant markets for given subsidies and coverage levels.

	Coverage level \Subsidies (in e) 0 100 150 200 250 300 350 400 450 500
	low	0	0	0	0	0	0	0	0	0	0
	medium low	0	1	5	10	15	20	25	26	27	28
	medium high	1	5	10	20	30	35	40	45	50	50
	high	5 10	23	36	48	55	60	65	70	70

Table 14 :

 14 Best solution found, final gap and root gap for cost equilibrium and other upgrade functions

		Instance		M		M + cost equilibrium overcost
	N S density	upgrade	sol	f-gap r-gap	sol	f-gap r-gap
	50	R	T.F. markets	3622	0.00	23	4410	5.19	32	22
			Ref. markets	4103	0.00	19	4589	0.90	26	12
			T.R. markets	4417	0.00	19	4962	2.05	26	12
		S	T.F. markets	2890	0.00	30	3600	1.73	40	25
			Ref. markets	3458	0.00	23	3877	1.70	31	12
			T.R. markets	3847	0.00	23	4192	0.04	28	9
		U	T.F. markets	1264	0.00	43	1742	0.00	77	38
			Ref. markets	2021	0.00	27	2043	0.00	11	1
			T.R. markets	2443	0.00	22	2470	0.00	34	1
	100	S	T.F. markets	5729	0.00	29	7142	2.54	40	25
			Ref. markets	6861	0.25	23	7767	7.95	31	13
			T.R. markets	7625	2.83	22	8389	7.64	28	10
	150	S	T.F. markets	8459	1.71	30	13650 26.22	54	61
			Ref. markets	9990	0.98	23	11642 11.12	34	17
			T.R. markets 11150 3.59	23	12130 6.66	29	9
	200	S	T.F. markets	11075 3.27	28	17984 26.15	53	62
			Ref. markets	13094 3.06	23	35768 52.99	71	173
			T.R. markets 14517 3.43	22	15949 6.49	28	10

Table 15 :

 15 Solution and final gap for large instances

	Instance			MILP (half an hour) MILP (two hours) MILP (five hours)
	Ter. Div.	N S	α 0	sol	f-gap	sol	f-gap	sol	f-gap
	Finistère	210	36	13885	7.00	13406	4.91	13406	4.61
	Côtes d'Armor	149	29	10420	3.38	10420	1.94	10420	1.48
	Morbihan	168	38	11178	4.08	11178	3.32	11178	2.75
	Ille et Vilaine	214	43	12400	3.76	12115	2.73	12115	2.15
	Mayenne	73	31	4879	1.62	4879	0.92	4879	0.50
	Sarthe	116	33	7729	3.23	7729	2.39	7728	1.64
	Maine et Loire	145	28	9877	4.68	9877	4.05	9877	3.65
	Bretagne	741	37	∞	∞	128109	100.00	128109	57.03
	Pays de la Loire 334	30	∞	∞	22470	4.26	22464	4.00
	Full instance	1075 35	∞	∞	169968	92.80	169968	92.80

  o is a continuous variable denoting the number of subscribers to subscription type o ∈ O at time period t ∈ T on site s ∈ S, • u t s,o,g is a continuous variable denoting the number of subscribers to subscription type o ∈ O served by network technology g ∈ G at time period t ∈ T on site s ∈ S,

• z t s,g is a binary variable equal to 1 iff at time period t ∈ T , technology g ∈ G is installed on site s ∈ S, • δ t σ,c,o is a binary variable equal to 1 iff at time period t ∈ T , subsidy σ is proposed to subscribers to subscription type o ∈ O \ {N O} if the coverage level of N G technology is equal to c ∈ C, • π t σ,c,s,o stands for the product of variables u t s,o and δ t σ,c .

  ) enforce the network dynamic rules. In particular, constraints (4.4) and (4.5) prevent from installing or adding capacity modules for a technology when the corresponding parameter is equal to 0. These constraints are not active otherwise. Constraints (4.6)-(4.8) refer to the network dimension constraints, ensuring capacity constraints and load balancing rules, making hence the link between the network dynamic and the subscriber dynamic. In particular, constraints (4.7) model the load balancing policies, stating that subscribers to a given offer have to be served by the most prioritized technology among the installed technologies. Constraints (4.9) and (4.10) stand for the subscriber dynamic constraints. They enable us to compute the total number of subscribers to each subscription type at each site and each time period. Constraints (4.11) and (4.12) ensure the model strategic guidelines and refer to the end of the time horizon. Con-Remark 7. Imposing to give the same subsidies proposal to subscribers to subscription types o 1 and o 2 ∈ O can be modeled easily adding constraintsδ t σ,c,o 1 = δ t σ,c,o 2 ∀t ∈ T , ∀σ, ∀c ∈ C,in formulation M M G . Such constraints can hence be added to the modeling if the promotions performed by the affiliates do not target a specific technology. . The cost equilibrium set of constraints in the more-than-two generation case can be written as follows:

	m t s,g ∈ Z αN S = s∈S z t s,g ∈ {0, 1} z t s,N G u t s,o ≥ 0 u t s,o,g ≥ 0 δ t σ,c,o ∈ {0, 1} π t σ,c,s,o ≥ 0 We define: B t = σ∈K c∈C s∈S o∈O\{N O} so the objective function (4.1) is actually equal to σf σ,c π t σ,c,s,o + s∈S g∈G CM g (m t ∀s ∈ S, ∀g ∈ G, ∀t ∈ T ∪ {0}, ∀s ∈ S, ∀g ∈ G, ∀t ∈ T ∪ {0}, ∀s ∈ S, ∀t ∈ T ∪ {0}, ∀o ∈ O, ∀s ∈ S, ∀t ∈ T , ∀o ∈ O, ∀g ∈ G, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O, ∀s ∈ S, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O. (4.22) (4.23) (4.24) (4.25) (4.26) (4.27) (4.28) s,g -m t-1 s,g )+ s∈S g∈G CA g (z t s,g -z t-1 s,g ) ∀t ∈ T , (4.29) B t B t Constraints (4.2)-(4.5Remark 8. Constraints (3.25) can also be adapted in the more-than-two generation framework. (1 -p) × t ∈T t ≤ B t ≤ (1 + p) × t ∈T t ∀t ∈ T . (4.30)

straints (4.13) ensure that one and only one subsidy from the set K is offered to the subscribers of each targeted subscription type at each time period. Constraints (4.14) and (4.15) set the range of coverage for each time period according to the coverage. Constraints (4.16)-(4.18) ensure that the linearization variables π model the product of variables δ by variables u. Constraints (4.19)-(4.21) refer to the initial conditions while constraints (4.22)-(4.28) define the domain of all variables in the formulation.

We denote this formulation by M M G . t∈T B t

Table 16 :

 16 Representation of a refarming plan

  ,s,o + Remark 10. The new variables incr t s,g,b and decr t s,g,b only appear in the objective function and in inequalities (4.32) and (4.33).

			CM g incr t s,g,b
		t∈T s∈S g∈G
	+	CA g (z t s,g -Z 0 s,g ) +	CR g decr t s,g,b .	(4.34)
	s∈S g∈G	t∈T s∈S g∈G\{N G}
		The equalities incr t s,g,b = max{0, m t s,g,b -m t-1 s,g,b } and decr t s,g,b =
	max{0, m t-1 s,g,b -m t s,g,

b } are hence verified for each site s ∈ S, each network technology g ∈ G and each band b ∈ B. Besides, decr t s,N G,b = 0, ∀s ∈ S, ∀b ∈ B.

  hence formulate the R-MG-MIS problem as follows:

	min (4.34)
	s.t. (4.2), (4.4) -(4.28)
	(4.31)
	(4.32) -(4.33)
	(4.35)
	m t s,g,b , incr t s,g,b , decr t s,g,b ≥ 0	∀t ∈ T , ∀s ∈ S, ∀g ∈ G, ∀b ∈ B,
	and we denote this formulation by M M G,ref arm .

Table 17 :

 17 Approximated range radius (in km) for three frequencies for three density contexts4.4.2 Mathematical modelingAiming to integrate sites coverage overlapping, we modify variables associated to subscribers, which are now located on set A.• for each t ∈ T ∪{0}, a ∈ A, o ∈ O, u t a,o denotes the total number of subscribers to subscription type o on area a at the end of time period t (upperly-bounded by U

t a,o ).

  Let us denote this formulation by M GEO . Constraints related to the load balancing policies, capacity and subscribers dynamic have been modified since users are now located on site a ∈ A. Constraints (4.45) ensure the geographical range conditions.

	m t s,g ∈ Z		∀s ∈ S, ∀g ∈ G, ∀t ∈ T ∪ {0},	(4.60)
	αN S =	z t s,N G		(4.61)
	s∈S
	z t s,g ∈ {0, 1}	∀s ∈ S, ∀g ∈ G, ∀t ∈ T ∪ {0},	(4.62)
	u t a,o ≥ 0		∀a ∈ A, ∀t ∈ T ∪ {0}, ∀o ∈ O,	(4.63)
	u t a,o,s,g ≥ 0		∀a ∈ A, ∀s ∈ S, ∀t ∈ T , ∀o ∈ O, ∀g ∈ G,
				(4.64)
	δ t σ,c,o ∈ {0, 1}	∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O,	(4.65)
	π t σ,c,a,o ≥ 0		∀a ∈ A, ∀t ∈ T , ∀σ ∈ K, ∀c ∈ C, ∀o ∈ O.
				(4.66)

Table 18 :

 18 Results for 50 sites

	Instance	investments	load balancing policies	sol	time f-gap o-gap
		Reference	Strict priority order	7458	0.00	39.92
			Priority + indifference	7456	0.00	39.90
	1	All installations	Total indifference Strict priority order	7395 7458	0.00 0.00	39.41 53.19
			Priority + indifference	7456	0.00	53.18
			Total indifference	7395	0.00	52.79
		Reference	Strict priority order	6647	0.00	39.74
			Priority + indifference	6644	0.00	39.71
	2	All installations	Total indifference Strict priority order	6597 6647	0.00 0.00	39.28 53.14
			Priority + indifference	6644	0.00	53.12
			Total indifference	6597	0.00	52.79
		Reference	Strict priority order	infeasible
			Priority + indifference	8087	0.00	39.00
	3	All installations	Total indifference Strict priority order	8044 8185	0.00 0.00	38.68 50.73
			Priority + Indifference	8087	0.00	50.13
			Total indifference	8044	0.00	49.86
		Reference	Strict priority order	7779	0.00	39.55
			Priority + indifference	7772	0.00	39.50
	4	All installations	Total indifference Strict priority order	7713 7779	0.00 0.00	39.03 49.96
			Priority + indifference	7772	0.00	49.92
			Total indifference	7713	0.00	49.53

Table 19 :

 19 Results for 50 sites

			Different decisions		Same decisions	extra cost
	upgrade	instance	sol	time f-gap o-gap	sol	time	f-gap o-gap
	classicreac		6990 1800 24.75 41.11	7458	106	0.00 39.92	6.28
			6300 1800 21.74 41.02	6647	168	0.00 39.74	5.22
			infeasible			infeasible
			7382 1800 23.78 41.94	7779	106	0.00 39.55	5.10
	2Gboost		7024 1800 24.08 44.99	7389	304	0.00 40.73	4.94
			6202 1800 26.42 44.05	6596	311	0.00 40.63	5.97
			infeasible		infeasible
			7285 1800 26.52 44.67	7725	271	0.00 40.51	5.70

Table 23 :

 23 Refarming results (5 hours time limit)

	Strategies

Table 24 :

 24 Results for overlappings tests

	Instance

  This formulation is directly adapted from M heur,2gen with constraints applied on set S bl .For each subset bl, we denote this formulation by M bl .

			.46)
	m 0 s,g = M 0 s,g	∀s ∈ S bl , ∀g ∈ G,	(5.47)
	z 0 s,N G = Z 0 s,N G	∀s ∈ S bl ,	(5.48)
	m t s,g ∈ N	∀s ∈ S bl , ∀t ∈ T ∪ {0}, ∀g ∈ G,
			(5.49)
	z t s,N G ∈ {0, 1}	∀s ∈ S bl , ∀t ∈ T ∪ {0}.	(5.50)

Proposition 11

. Any solution which is for each subset bl a feasible solution of formulation M bl , is a feasible solution for formulation M.

  .51) Proposition 12. Any solution which is for each block bl a solution of formulation M with the following cost equilibrium constraints on part S bl We suppose that, for each block, constraints (5.52) are satisfied. By using B t =

			B t (S bl )			B t (S bl )
	(1 -p) ×	t ∈T	t	≤ B t (S bl ) ≤ (1 + p) ×	t ∈T	t	∀t ∈ T .	(5.52)
	is a feasible solution for formulation M with constraints (3.25) added.
	Proof.

bl B t (S bl )

  3.2 on each part S bl , as follows: , coverage threshold (5.62) and definitions of the variables are now defined on set S bl . Constraints (5.63) and (5.64) ensure that the range of coverage is equal to the one defined by vector c. Constraints (5.61) ensure the quality of service threshold on set S bl .For each subset bl, we denote this formulation by M bl M G . Proposition 14. Any solution which is for each subset bl a feasible solution of formulation M bl M G , is a feasible solution for formulation M M G .

	z t-1 s,N G ≤ U ct |S bl |	∀t ∈ T ,		(5.64)
	s∈S bl
	m 0 s,g = M 0 s,g	∀s ∈ S bl , ∀g ∈ G,	(5.65)
	z 0 s,g = Z 0 s,g	∀s ∈ S bl , ∀g ∈ G,	(5.66)
	u t s,o,g ∈ R	∀s ∈ S bl , ∀g ∈ G, ∀o ∈ O	(5.67)
	m t s,g ∈ N	∀s ∈ S bl , ∀g ∈ G, ∀t ∈ T ∪ {0},	(5.68)
	z t s,g ∈ {0, 1}	∀s ∈ S bl , ∀t ∈ T ∪ {0}.	(5.69)
	Network dynamic constraints (5.54)-(5.57), load balancing constraints (5.58) and (5.59), capacity
	constraints (5.60)
	min	CM g (m t s,g -M 0 s,g )	+	CA g (z t s,g -Z 0 s,g )	(5.53)
	s∈S bl g∈G	s∈S bl g∈G
	s.t. m t s,g ≤ M g z t s,g	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G,	(5.54)
	m t-1 s,g ≤ m t s,g	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G,	(5.55)
	m t s,g ≤ M 0 s,g + N M g × InvM g	∀s ∈ S bl , ∀g ∈ G,	(5.56)
	z t s,g ≤ Z 0 s,g + InvA g	∀s ∈ S bl , ∀g ∈ G,	(5.57)
	U t s,o =	u t s,o,g	∀s ∈ S bl , ∀g ∈ G, ∀t ∈ T , ∀o ∈ O,	(5.58)
	g∈G:CPo,g =0
	u t s,o,g ≤ U t s,o (1 -z t s,k )	∀(o, g) ∈ {(o, g) ∈ OXG, CP o,g < CP o,k }, ∀s ∈ S bl ,
					(5.59)
	D t o,g	u t s,o,g ≤ CAP g m t s,g	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G,	(5.60)
	o∈G
	U t s,N O z t s,N G ≥ QoE ×	U T OT t s ,		(5.61)
	s∈S bl	s∈S bl
	z t s,N G ≥ α|S bl | ,			(5.62)
	s∈S bl
	z t-1 s,N G ≥ L ct |S bl |	∀t ∈ T ,		(5.63)
	s∈S bl

  Proposition 15. Any solution which is for each block bl a solution of formulation M bl ref arm is a feasible solution for formulation M M G ref arm . Proof. We observe that constraints (5.71)-(5.75) are imposed on each site and hence site decomposable. This is also true for the network cost (5.70). Consequently, we are able to solve problem R -M G -M IS(σ, c) by solving formulations M bl ref arm for all blocks bl ∈ {1, . . . , N bl }: the cost of problem R -M G -M IS(σ, c) is equal to obj(M bl ref arm ) + upgradecost. Remark 17.Note that trying this approach on any of the variants considered here without subscriber dynamic fixed would impose the dualization of the following linkings constraints δ t σ,c = δ t

				bl,σ,c
				on each
	site:
	min	CM g incr t s,g,b
	t∈T s∈S bl g∈G
	+	CA g (z t s,g -Z 0 s,g ) +	CR g decr t s,g,b ,	(5.70)
	s∈S bl	t∈T s∈S bl g∈G\{N G}
	as well as the refarming constraints:
	ω g m t s,g,b ≤ ω t g,b ,	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G, ∀b ∈ B,	(5.71)
	incr t s,g,b ≥ 0,	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G, ∀b ∈ B,	(5.72)
	decr t s,g,b ≥ 0,	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G, ∀b ∈ B,	(5.73)
	incr t s,g,b ≥ m t s,g,b -m t-1 s,g,b ,	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G, ∀b ∈ B,	(5.74)
	decr t s,g,b ≥ m t s,g,b -m t-1 s,g,b ,	∀s ∈ S bl , ∀t ∈ T , ∀g ∈ G, ∀b ∈ B,	(5.75)
	We define by M bl ref arm the formulation
		min (5.70) s.t. (5.54) -(5.69), (5.71) -(5.75).

Table 25 :

 25 Solution and final gap for large instances

	Instance			heuristic	gapMILP	MILP	MIPstart
	Ter. Div.	N S	α 0	sol	time		sol	f-gap	sol	f-gap
	Finistère	210	36	13406 505	0	13406	4.91	13406 3.14
	Côtes d'Armor	149	29	10420 617	0	10420	1.94	10420 1.64
	Morbihan	168	38	11178 551	0	11178	3.32	11178 2.06
	Ille-et-Vilaine	214	43	12115 776	0	12115	2.73	12115 2.32
	Mayenne	73	31	4879	127	0	4879	0.92	4879	0.00
	Sarthe	116	33	7729	186	0	7729	2.38	7229	0.00
	Maine et Loire	145	28	9877	221	0	9877	4.06	9877	0.72
	Bretagne	741	37	47106 3197	-63.41	128109 100.00 47106 3.51
	Pays de la Loire 334	30	22467 4113	-0.01	22470	4.26	22464 3.01
	Full instance	1075 35	69497 5997	-59.00	169968 92.80	69497 5.42

Table 26 :

 26 Solution and final gap for large instances with cost equilibrium constraints with VNS

	Instance		MILP	VNS+sitesdec		MIPSTART
	Ter div	NS	α 0	sol	f-gap nbblocks	sol	time	sol	f-gap
	Finistère	210	36 14853 6.04	1	15455	10682 14921 4.88
	Côtes-d'Armor	149	29 11865 9.65	1	15719	4811	11818 3.52
	Morbihan	168	38 12347 6.30	1	12804	12767 12347 4.36
	Ille-Et-Vilaine	214	43 13304 3.28	1	13427	8483	13301 2.53
	Mayenne	73	32	5563	0.99	1	5572	10173	5563	1.57
	Sarthe	116	34	8598	2.40	1	9530	9362	8634	4.83
	Maine-et-Loire	145	30 11215 3.04	1	11278	11151 11215 5.13
	Bretagne	741	37	NA	NA	2	55543	16916 55543 13.15
	Pays-de-Loire	334	31 25206 5.11	1	26279	12016 25206 6.38
	Full	1075 35	NA	NA	3	84352	21020 76563 6.38
	fictive	3000 35	NA	NA	8	235362 116694	NA	NA
	fictive	12000 35	NA	NA	32	905314 544267	NA	NA

  )

	γ t c = 1,	∀t ∈ T	(6.16)
	c∈C
	δ t σ = 1	∀t ∈ T	(6.17)
	σ∈K
	subcost ≥ 0.		(6.18)

  CG ,

	which means that constraints (6.33) are satisfied.
	Proposition 24. Constraints (6.35) are satisfied if and only if the following constraints are sat-
	isfied:
	s∈S

  OT, ∀l ∈ L, ∀f 1 ∈ F (l), ∀f 2 ∈ F ,(6.47)

	δ 1 σ = 1,	(6.48)
	σ∈K
	δ 2 σ,l = 1	∀l ∈ L,
	σ∈K
		(6.49)
	δ 1 σ ∈ {0, 1}	∀σ ∈ K,
		(6.50)
	δ 2 σ,l ∈ {0, 1}	∀σ ∈ K, ∀l ∈ L .
		(6.51)

Table 27 :

 27 5.2), adapted for a two-period framework. At the beginning of the time horizon, 34 sites are equipped with both 3G and 4G technologies while 66 are 3G-only sites. The network parameter values are realistic values taken from telecommunication equipment sellers. The strategic guideline for quality of experience QoE is fixed to 80% and the coverage threshold alpha to 70%. Regarding the subscriber dynamic, values for fσ,c are recalled in Table27. Reaction of the subscribers (in %) on reference markets for given subsidies and coverage levels.

	Coverage level \Subsidies (in e )	0	100 150 200 250 300 350 400 450 500
	low	0	0	0	0	0	0	0	0	0	0
	medium low	0.5	5	12	21	30	40	42	43	44	45
	medium high	5	10	20	30	40	50	60	62	64	65
	high	10	20	33	45	58	70	80	83	87	90

Table 28 :

 28 Solutions for 0.25, 0.30 and 0.35 deviations

	Γ	model	sol	time first-stage (σ 1 )		second-stage (σ 2 )
		deterministic 6999	19	200		250
	0.25	static	9691	18	250		350
		adj (L = 2)	9643	78	350	300		250
		adj (L = 4)	9643	347	350	300	250	250	200
		adj (L = 8)	9580 7200	350	300 300 300 250 250 250 200 200
	0.30	static	10097	10	300		350
		adj (L = 2)	10066	36	350	300		250
		adj (L = 4)	10066 274	350	300	300	250	150
		adj (L = 8)	9965 3095	350	300 300 300 250 250 250 150 250
	0.35	static	10957	8	350		350
		adj (L = 2)	10767	28	350	350		250
		adj (L = 4)	10671 130	350	350	300	250	200
		adj (L = 8)	10671 1105	350	350 350 300 300 300 200 150 100

Table 29 :

 29 Simulated cost for 0.25, 0.30 and 0.35 deviations

	Γ	model for first-stage first-stage (σ 1 ) worst-case cost
	0.25	deterministic	200	10671
	0.25	static	250	9659
	0.25	adj	350	9270
	0.30	deterministic	200	13074
	0.30	static	300	10081
	0.30	adj	350	9636
	0.35	deterministic	200	infeasible
	0.35	static	350	10565
	0.35	adj	350	10565

La GSM Association est un organisme d'échange d'origine européenne qui représente les intérêts des opérateurs mobiles dans le monde.

Remerciements

I can't carry it for you, but I can carry you -Samwise Gamgee, Lord Of The Rings, J.R.R. Tolkien

List of Tables

LIST OF TABLES

Solutions for 0.25, 0.