PhD title: “Algorithmic and Structural Properties of box-TDI Polyhedra

Scope. A large part of optimization problems amounts to optimizing a linear program, where the feasible region is a polyhedron defined by linear inequalities. The complexity of solving such problems is heavily influenced by the structure of the polyhedron. In particular, when a polyhedron is integer, it is well known that we can solve such problems in polynomial time on the size of the problem [7]. In practice, one of the most efficient algorithms is still the Simplex Method developed by Dantzig. Even if this method is known for having bad theoretical performances [8, 10], it has seen a renewed interest and several theoretical advances [5], in particular some recent developments connect the structure of a polyhedron and the efficiency of this algorithm [1]. One other point of interest for this algorithm is the strong connection with the polyhedral structure of the problem itself. In particular, one key factor influencing the performance of the simplex algorithm is the combinatorial diameter of the polyhedron, which bounds the number of pivots required in the worst case. In this context, a weak form of the Hirsch Conjecture is valid for several classes of polyhedra. Among them, polytopes defined by Totally Unimodular Matrices [2, 6] and polymatroids [12]. Box-TDI polyhedra are the polyhedra that can be described by a box-TDI system. This class includes as special cases polyhedra described by Totally Unimodular Matrices [3] and polymatroids [11]. The main goal of this project is to study whether box-TDI polyhedra, in particular those described by Totally Equimodular Matrices, admit improved diameter bounds. This result is known to hold for some cases, like the fractional stable set polytope [9]. Objectives. This PhD project will focus on the following key objectives: • Investigate whether the diameter of box-TDI polyhedra, in particular those described by totally equimodular matrices admits tighter bounds than general polyhedra, particularly in relation to the Hirsch conjecture. • Studywhether classic optimization algorithms, such as the simplex and interior point methods, perform efficiently on box-TDI polyhedra. • Explore the combinatorial and geometric characteristics of box-TDI polyhedra that influence algorithmic per formance. This topic fits perfectly within the research directions of LAMSADE’s Pˆole 2, as it mixes combinatorial optimization considerations with matricial and geometrical aspects. Planning for the first year. • September-December 2026: compose a solid foundation on the topic of box-TDI polyhedra, as well as a knowledge of the recent results on the Simplex Method. • January-August 2027: apply the recent techniques, proposed for instance in [2], to Box-TDI polyhedra, and deduce a upper bound on the diameter of such polyhedra. • September-December 2027: writing of the paper. Impact and consequences. This research is expected to contribute to a deeper understanding of the relationship between polyhedral structure and the complexity of linear optimization algorithms. By investigating diameter bounds and structural properties of box-TDI polyhedra, the project may extend known results for totally unimodular and related classes of polyhedra to a broader setting. Establishing refined diameter bounds or identifying structural features that facilitate efficient pivoting could provide new insights into the theoretical behavior of the simplex method and other optimization algorithms on structured polyhedra. Beyond its theoretical relevance, such results may inform the design and analysis of algorithms for classes of integer and linear programs arising in combinatorial optimization, thereby strengthening the connections between polyhedral theory, algorithmic complexity, and practical optimization methods. Planning for 3 years. The research direction will be adjusted based on progress in the first year. However, a tentative plan is: • (2028)- Generalize recent advances on the Simplex Method [1, 5] to deduce its theoretical complexity on box-TDI polyhedra. • (2029)- Finalize theoretical contributions, refine algorithmic analysis, and prepare the PhD dissertation Required skills. The candidate should have a Master’s degree in Mathematics, Computer Science, Operations Research, or a closely related field. A solid background in mathematics, especially in linear algebra and polyhedra, will be highly valued. Familiarity with integer programming concepts and techniques is expected, given the optimization focus