A Compact Mixed Integer Linear Formulation for Safe Set Problems
| Autor: | Pierre Hosteins |
|---|---|
| Přispěvatelé: | Évaluation des Systèmes de Transports Automatisés et de leur Sécurité (COSYS-ESTAS ), Université de Lille-Université Gustave Eiffel |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
Mathematical optimization
Control and Optimization Linear programming Computer science CONTROLE COMMANDE RECHERCHE OPERATIONNELLE 0211 other engineering and technologies Computational intelligence 010103 numerical & computational mathematics 02 engineering and technology 01 natural sciences SAFE SET VARIABLE REDUCTION SYMMETRY-BREAKING SURETE DE FONCTIONNEMENT Partition (number theory) 0101 mathematics SYSTEME LINEAIRE SECURITE Polynomial number 021103 operations research GRAPH PARTITIONING OPTIMISATION MODELISATION TRANSPORT FERROVIAIRE MIXED INTEGER LINEAR PROGRAMMING PROGRAMME DE CALCUL SIMULATION CONNECTED SAFE SET MODELE LINEAIRE [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC] NETWORK CONTROL |
| Zdroj: | Optimization Letters Optimization Letters, Springer Verlag, 2020, 21p. ⟨10.1007/s11590-020-01540-z⟩ |
| ISSN: | 1862-4472 1862-4480 |
| DOI: | 10.1007/s11590-020-01540-z⟩ |
| Popis: | The Safe Set Problem is a type of partitioning problem with particular constraints on the weight of adjacent partition components. Several theoretical results exist in the literature along with a mixed integer linear formulation. We propose a new, more compact, Mixed Integer Linear Program for the (Weighted) Safe Set Problem and Connected Safe Set Problem with a polynomial number of variables and constraints, based on a flow from an additional fictitious node. The model is enriched by symmetry-breaking considerations and a variable reduction subproblem. We test the model on a benchmark of small instances which underline the difficulty of solving the Safe Set Problem through mathematical programming approaches. We also compare it with the only existing formulation in the literature and find that our approach is usually more efficient on a set of benchmark instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink