Project Manager: Conf. Dr. Eng. Guillaume DUCOFFE – R4

Overall objective of the project

The main objective of the project is the design and validation of a reliable solver for practical scenarios of facility location problems in Romania.

Project description

The Romanian government has proposed itself an ambitious program about infrastructures: ranging from the development of the highway network throughout the country to the building of new crucial facilities such as schools and hospitals. Successful completion of this program requires solving the difficult problem of rightfully choosing the location for these new facilities. We propose ourselves to design (and test) a fully functional prototype for solving facility location problems based on our past algorithmic expertise in this area. The prototype would account for the specificities of Romanian national infrastructure topologies in order to gain in efficiency. Nevertheless, the properties needed for our algorithms to be valid are sufficiently general so that they could applied to a great deal of different topologies with only slight code changes and no loss in efficiency. This latest feature, we believe, could be of importance for future, more advanced, industrial applications.

Estimated results

• release of a new software, FLIPS, for facility location problems in Bucharest and in Romania.

Obtained results

Phase 1/2022, the title of which is "Creation of a database and analytic instruments for facility location studies in Romania’’, has been composed of four main activities:

• Activity 1.1, the title of which is "Creation of a database for facility location studies in Romania’’, has resulted in a database, stored as MS Excel files, with some information regarding public transport, locations of all main schools and hospitals, and population densities, in Bucharest and (partially) other main cities in Romania.
• Activity 1.2, the title of which is `"Detailed study about state-of-the-art software solutions for facility location problems’’, has resulted in a comparative study between some existing solutions for solving linear programs. A performance study has also been realized for ILP solvers, SAT solvers and combinatorial methods, applied to some facility location problems.
• Activity 1.3, the title of which is `"Implementation of new algorithms for advanced network analysis’’, has resulted in the implementation and testing of several graph algorithms, for testing some geometric properties such as Helly number. All source codes have been written in Python.
• Activity 1.4, the title of which is "Project management and Dissemination’’, has resulted in the publication of three scientific articles (two articles in national scientific journals, and one article accepted at an international conference), and the submission of two more articles for publication in some ISI journals. Furthermore, a bibliographic study about facility location problems and the most recent techniques in classification theory has been realized.

Phase 2/2023, the title of which is "Studies on facility location problems for Romania: algorithms and advanced network analysis’’, has been composed of four main activities:

• Activity 2.1, the title of which is "Analysis of facility location networks’’, has resulted in a detailed analysis of the geometric properties of the public transportation network in Bucharest (encoded as a graph). Information about this network has been extracted from the database created during the first phase of this project (Activity A.1.1). Furthermore, the analysis has been done using the algorithms implemented during the first phase of the project (Activity A.1.3).
• Activity 2.2, the title of which is "Implementation of efficient algorithms for facility location problems’’, has resulted in the implementation and testing of several algorithms, and related data structures, for the k-Center and k-Median problems. This activity has required the thorough reading of more than 14 scientific articles. Furthermore, a performance study has also been realized, using synthetic networks (random graphs).
• Activity 2.3, the title of which is "Hypotheses validation’’, has resulted in a preliminary study about the optimality of the main high school locations in Bucharest.
• Activity 2.4, the title of which is ‘’Project management and Dissemination’’, has resulted in the publication of three scientific articles (one article in an international scientific journal, and two articles in international conferences), and the submission in two more articles for publication in ISI journals and conferences.

Phase 3/2023, the title of which is "Building and testing of a new solver for facility location problems’’, has been composed of three main activities:

• Activity 3.1, the title of which is "Simulation of facility location problems’’, has resulted in the elaboration of four ‘’business cases’’ for our solver: one for universities locations in Bucharest (based on the Bucharest city map analyzed during Activity 2.1), and three more for sensors installation in various environments (underground, vineyard, network). The latter three business cases were built on top of datasets collected by Beia International for past or ongoing projects.
• Activity 3.2, the title of which is "Performance study and runtime analysis’’, has resulted in a runtime comparison between our new solver and state-of-the-art ILP-based and SAT-based solvers (already considered during Activity 1.2). The performance study has been realized using synthetic networks (random graphs).
• Activity 3.3, the title of which is ‘’Project management and Dissemination’’, has resulted in the publication of three scientific articles in international scientific journals.  
  

Dissemination

1. Ducoffe, G. Obstructions to Faster Diameter Computation: Asteroidal Sets. 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). In LIPIcs, Volume 249, IPEC 2022 (December 2022). doi:10.4230/LIPIcs.IPEC.2022.10
2. Ducoffe, G. Obstructions to Faster Diameter Computation: Asteroidal Sets. Journal version. Submitted. Available at https://arxiv.org/pdf/2209.12438
3. Ducoffe, G. A variation of Boolean distance. Bulletin Mathematique de la Societe des Sciences Mathematiques de Roumanie, 2022, 65(113), No. 4, pp. 405-419. WOS:000965780200005
4. Ducoffe, G. The power of interval models for computing graph centralities. Romanian Journal of Information Technology and Automatic Control. 2022, 32 (4), pp.33-44. doi:10.33436/v32i4y202203. WOS:000924067500003
5. Ducoffe, G. Distance problems within Helly graphs and k-Helly graphs. Theoretical Computer Science, 2023, 946, no.113690. doi:10.1016/j.tcs.2023.113690. WOS:000923734600001
6. Dragan, F.F. and Ducoffe, G. $\alpha_i$-Metric Graphs: Radius, Diameter and all Eccentricities. 49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2023). In Lecture Notes in Computer Science, Volume 14093, pp. 276-290, Springer.
7. Radulescu, C.-Z., Radulescu, M. and Boncea, R. A revised group DEMATEL method with application on facility location problem in context of Internet of Things. 10th International Conference on Information Technology and Quantitative Management (ITQM 2023). In Procedia Computer Science, Volume 221, pp. 9-16, Elsevier.
8. Dissaux, T., Ducoffe, G. and Nisse, N. Treelength of series-parallel graphs. Discrete Applied Mathematics, 2023, 341, pp. 16-30. doi:10.1016/j.dam.2023.07.022. WOS:001059041300001
9. Ducoffe, G. Balancing graph Voronoi diagrams with one more vertex. Accepted. To appear in Networks, Wiley.
10. Ducoffe, G., Habib, M., Pitois, F. and Feuilloley, L. Pattern detection in ordered graphs. Submitted. Technical report available at https://arxiv.org/pdf/2302.11619.
11. Berge, P., Ducoffe, G. and Habib, M.  Subquadratic-time algorithm for the diameter and all eccentricities on median graphs. Accepted. To appear in Theory of Computing Systems, Springer.

Final Scientific Report (2022 - 2023)

For more details, download Raport științific final