## Research Topics

Below you find a description of my research areas, each appearing with the related publications (papers that cross different subjects appear multiple times).

Extended formulations

Algorithms for solving constrained optimization problems are highly dependendent on the size of the system of constraints describing the feasible region: the larger its size, the larger the running time of the algorithms (in both theory and practice, assuming all other parameters stay the same). It is often the case that a feasible region can be expressed more succintly as the image under an affine map of a convex set living in an higher dimensional space. Such a convex set is called an *extension* and its description via a system of constraints an *extended formulation* for the original feasible region.

A typical question I investigate in this area is: what is the minimum number of constraints in a (linear) extended formulation for the feasible region P of a linear program? This is called the *extension complexity* of P. Papers **EF4, EF6, EF9, EF10, EF11** and the survey **EF1** deal with this question for feasible regions of problems arising in combinatorial optimization, including matching problems under preferences (aka matching markets). Papers **EF2, EF8** deal with more general integer and certain quadratic problems.

Somehow suprisingly, questions on extension complexity can be reformulated, and sometimes solved, using techniques from seemingly far away areas of mathematics and computer science, like algebraic geometry and boolean Fourier analyis. I am / have been investigating some of these connections. In **EF3, EF7** we explore in particular the relationship between extension complexity and communication protocols, a classical topic in theoretical computer science. In **EF5** we bound the minimum increase in the number of variables needed to obtain certain extended formulations with ''few'' constraints. Current ongoing work also deals with the relationship between extended formulations and Sum of Squares proofs.

My current work in this area is supported by an award from the ONR. Previously, it was supported by an award and then a gift from the Swiss National Science Foundation.

**EF11**. Affinely representable lattices, stable matchings, and choice functions. With Xuan Zhang. Accepted for publication in**Mathematical Programming**. An extended abstract has appeared in the proceedings of**IPCO 2021**.**EF10.**Pitch, extension complexity, and covering problems. With D. Bienstock and Xuan Zhang.**Operations Research Letters**49 (2021), pp. 357-364.**EF9.**Quasi-popular matchings, optimality, and extended formulations. With T. Kavitha.**Mathematics of Operations Research**, 47(1), pp. 427-457. An extended abstract has appeared in the proceedings of**SODA 2020**.**EF8.**New limits of treewidth-based tractability in optimization. With G. Munoz and S. Pokutta. Accepted for publication in**Mathematical Programming**.**EF7.**Extended formulations from communication protocols in output-efficient time. With M. Aprile.**Mathematical Programming**, 183 (2020), pp. 41--59. An extended abstract has appeared in the proceedings of**IPCO 2019**.**EF6.**Separation algorithm and extended formulations for the stable set polytope in claw-free graphs. With G. Oriolo and G. Stauffer. Accepted for publication in**Mathematical Programming**. An extended abstract has appeared in the proceedings of**SODA 2012**.**EF5.**Balas formulation for the union of polytopes is optimal. With M. Conforti and M. Di Summa.**Mathematical Programming**, 180 (2020), pp. 311-326.**EF4.**Extension complexity of stable set polytopes of bipartite graphs. With M. Aprile, S. Fiorini, T. Huynh, and M. Macchia. Proceedings of**WG 2017**.**EF3.**Extended formulations, non-negative factorizations, and randomized communication protocols. With S. Fiorini, R. Grappe, and H.R. Tiwary.**Mathematical Programming**, 153-1 (2015), pp. 75-94. An extended abstract has appeared in the proceedings of**ISCO 2012**.**EF2.**Extended Formulations for Packing and Partitioning Orbitopes. With V. Kaibel.**Mathematics of Operations Research**, Vol. 34, No. 3 (2009), pp. 686--697.**EF1.**__Stable sets in claw-free graphs: a journey through algorithms and polytopes__. With G. Oriolo, G. Stauffer, and P. Ventura. In A. Ridha Mahjoub, editor,*Progress in Combinatorial Optimization*, Ed. Wiley-ISTE (2011), pp. 41--80.

Matching problems

In matching problems we want to pair agents as to respect certain feasibility condition and / or maximize given objective functons. Matching problems lie at the intersection of operations research, computer science, and economics, and have historically played a fundamental role in each of those areas. They appear in applications such as job placement, school choice, machine learning, etc. My research in this area has mainly followed three strands.

Edmonds' maximum (weighted) matching problem is one of the pillars of discrete optimization. This problem can be equivalently be formulated as a maximum (weighted) independent set problem in an auxiliary graph (''line graph''). Researchers have investigated superclasses of line graphs where the (weighted) stable set problem can be solved efficiently. My work here as focused on the class of claw-free graphs. Stable sets in claw-free graphs have been studied since the 70s. Those graphs have applications in problems arising in wireless networks, scheduling, and machine learning. For the maximum weighted stable set problem in claw-free graphs, we gave (the) fast(est) combinatorial algorithms (**MP2, MP3**), as well the first non-trivial geometric algorithm (**MP4**). See also **MP1**.

Unlike ''classical'' matching problems, in matching markets arising, e.g., in school choice, agents have preferences of their possible partners, which typically makes the set of feasible matching and/or the objective function more complex. Here, my research has mostly focused on questions such as: can we efficiently obtain certain matchings of probably good quality? If this is not the case, can we define new concepts in matching markets, leading to algorithmically tractable problems? Much of my work here deals with extensions of the classical concept of stability, introduced by Gale and Shapley in 1962. I have studied popular matchings (**MP5, MP6, MP8**), legal assignments (**MP7**), matchings with blocking costs (**MP9**), and problems where preferences of agents are described by choice functions (**MP11**). Some of those techniques rely on the relationship between the distributive lattice of stable matchings and an associated poset via Birkhoff's representation theorem. This relationship is investigated in a more general setting in **MP11**. I have also investigated real-world applications of those matching markets to school choice (and drawbacks thereof), especially in the presence of bias (**MP10**) and with the goal of incentivizing the admission of disadvantaged students (**MP12**).

The problem of matching drivers to rides in modern ride-sharing platforms isoften modelled as an online matching problem in a bipartite graph, where one side of the market is known in advance (typically, the drivers), while the other comes in an online fashion. Because of the scale of real-world instances, in practice simple algorithms are often used to solve such matching problems. In **MP13**, we studied in which settings we can expect the simplest algorithm of all, i.e., greedy, to perform well, as a function of the distributions of the locations of servers and drivers.

My current work in this area is supported by an NSF CAREER award.

**MP13**. The Power of Greedy for Online Minimum Cost Matching on the Line . With E. Balkanski and N. Perivier.**MP12**. Discovering Opportunities in New York City's Discovery Program: an Analysis of Affirmative Action Mechanisms. With Swati Gupta and Xuan Zhang.**MP11**. Affinely representable lattices, stable matchings, and choice functions. With Xuan Zhang. Accepted for publication in**Mathematical Programming**. An extended abstract has appeared in the proceedings of**IPCO 2021**.**MP10.**Reducing the Feeder Effect in Public School Admissions: A Bias-aware Analysis for Targeted Interventions. . With S. Gupta and Xuan Zhang.**MP9.**(Un)stable matchings with blocking costs. With I. Mourtos, M. Samaris, and J. Sethuraman.**Operations Research Letters**49 (2021), pp. 655-662.**MP8.**Understanding popular matchings via stable matchings . With A. Cseh, T. Kavitha, and V. Powers.**Siam Journal on Discrete Mathematics**36.1 (2022), pp. 188-213.**MP7.**Legal Assignment and fast EADAM with consent via classical theory of stable matchings. With Xuan Zhang. Accepted for publication in**Operations Research**.**MP6.**Quasi-popular matchings, optimality, and extended formulations. With T. Kavitha.**Mathematics of Operations Research**, 47(1), pp. 427-457. An extended abstract has appeared in the proceedings of**SODA 2020**.**MP5.**Popular matchings and limits to tractability. With T. Kavitha, V. Powers, and Xingyu Zhang. Proceedings of**SODA 2019**. A journal version is under submission.**MP4.**Separation algorithm and extended formulations for the stable set polytope in claw-free graphs. With G. Oriolo and G. Stauffer. Accepted for publication in**Mathematical Programming**. An extended abstract has appeared in the proceedings of**SODA 2012**.**MP3.**Solving the weighted stable set problem in claw-free graphs via decomposition. With G. Oriolo and G. Stauffer.**Journal of the ACM**, 61-4:20 (2014).**MP2.**An algorithmic decomposition of claw-free graphs leading to an O(n^3)-algorithm for the weighted stable set problem. With G. Oriolo and G. Stauffer. Proceedings of**SODA 2011**.**MP1.**__Stable sets in claw-free graphs: a journey through algorithms and polytopes__. With G. Oriolo, G. Stauffer, and P. Ventura. In A. Ridha Mahjoub, editor,*Progress in Combinatorial Optimization*, Ed. Wiley-ISTE (2011), pp. 41--80.

Knapsack and other combinatorial optimization problems

Many problems in Discrete Optimization can be formulated in a combinatorial way as to problem of choosing a set of maximum profit from a finite family of feasible sets. In this area, I have investigated fast algorithms, hardness, and hardness of approximation for graph optmization problems such as maximum stable (independent) set (**KP3**), coloring (**KP2**), Traveling Salesman Problem (**KP9**), and for invariant-preserving reductions (**KP1**). Those problems model applications arising, eg, in allocation of scarce resources such as bandwith, classes,....

I have moreover been very interested in knapsack problems. In the classical knapsack problem we want to select a set of objects as to maximize a linear objective function, subject to the constraint that the total weight of the selected objects does not exceed a given capacity. (Extensions of) Knapsack are widely used to model research allocation and financial planning problems. Combinatorial algorithms for knapsack are very well-studied. However, less is known on geometric approaches, both for knapsack and for its minimization counterpart, called *minimum knapsack*. Some questions on geometric approaches to these problems are studied in **KP4, KP6, KP7**.

In order to model real-world scenarios, several extensions of knapsack have been introduced. One such generalization assumes that the capacity of the knapsack increases over time (as to model a growth in the budget for investments, of the avaialable resources,...). This class of extensions goes under the name of *incremental knapsack problems*. In **KP5, KP8 ** we study algorithms for certain incremental knapsack problems, and their connections with problems in scheduling.
For more problems in combinatorial optimization such as matching and stable set problems that generalize matching, see this section.

**KP9.**The simultaneous-semi random model for TSP. With E. Balkanski and M. Kubik. Proceedings of**IPCO 2022**. A journal version is under submission.**KP8.**Approximation algorithms for the generalized incremental knapsack problem. With D. Segev and L. Zhang. Accepted for publication in**Mathematical Programming**.**KP7.**Pitch, extension complexity, and covering problems. With D. Bienstock and Xuan Zhang. Accepted for publication in**Operations Research Letters**.**KP6.**On inequalities with bounded coefficients and pitch for the Min Knapsack polytope. With D. Bienstock, I. Malinovic, M. Mastrolilli, O. Svensson and M. Zuckerberg. Accepted for publication in**Discrete Optimization**. An extended abstract has appeared in the proceedings of**ISCO 2018**.**KP5.**A PTAS for the Time-Invariant Incremental Knapsack problem. With I. Malinovic. Proceedings of**ISCO 2018**.**KP4.**On the existence of compact epsilon-approximation for the knapsack polytope in the original space. With L. Sanità.**Operations Research Letters**, 43-3 (2015), pp. 339-342.**KP3.**Solving the stable set problem in terms of the odd cycle packing number. With A. Bock, C. Moldenhauer, and A. Ruiz-Vargas. Proceedings of**FSTTCS 2014**.**KP2.**On coloring problems with local constraints. With F. Bonomo and G. Oriolo.**Discrete Mathematics**, 32:12-13 (2012).**KP1.**A fast algorithm to remove proper and homogeneous pairs of cliques (while preserving some graph invariants). With G. Oriolo and C. Snels.**Operations Research Letters**, Vol. 39, Issue 3 (2011).

Cutting planes for IPs

Integer Programming (IP) aims at maximizing a linear function over the set of integer points that satisfy a finite set of linear constraints. It is used to model many problems arising in production planning, logistics, and many more settings. In general, IPs are very hard to solve, hence the study of fast general or problem-specific algorithms for their solutions is a crucial area of research.

In order to obtain an approximation to the value of the optimal solution to an IP, a classical approach relaxes the integrality constraints, and solves the (much easier) resulting linear program. However, the solution produced by this technique may be very far away from the optimum integer solution. We want therefore to improve the formulation of the problem by adding additional inequalities called *cutting planes* (or *cuts*).

Which cutting planes allow us to obtain a (much) better approximation to the optimal integer solution? Which moreover lead to a formulation that can be easily solved? In **CP1, CP2, CP4**, we investigate properties of cutting planes that are valid for *any* IP, that go under the name of *Chvatal-Gomory* and *Split* cuts. In **CP3, CP6, CP7** we investigate families of cutting planes that are valid for knapsack problems. In **CP5** we investigate how Machine Learning techniques can be used to guide the selection of the best cutting planes.

**CP7.**Pitch, extension complexity, and covering problems. With D. Bienstock and Xuan Zhang.**Operations Research Letters**49 (2021), pp. 357-364.**CP6.**On inequalities with bounded coefficients and pitch for the Min Knapsack polytope. With D. Bienstock, I. Malinovic, M. Mastrolilli, O. Svensson and M. Zuckerberg. Accepted for publication in**Discrete Optimization**. An extended abstract has appeared in the proceedings of**ISCO 2018**.**CP5.**Reinforcement learning for integer programming: learning to cut. With Y. Tang and S. Agrawal. Proceedings of**ICML 2020**.**CP4.**Reverse Split rank. With M. Conforti, A. Del Pia, and M. Di Summa.**Mathematical Programming**, 154-1 (2015), pp. 273-303. An extended abstract has appeared in the proceedings of**IPCO 2014**.**CP3.**On the existence of compact epsilon-approximation for the knapsack polytope in the original space. With L. Sanità.**Operations Research Letters**, 43-3 (2015), pp. 339-342.**CP2.**Reverse Chvatal-Gomory rank. With M. Conforti, A. Del Pia, and M. Di Summa.**SIAM Journal on Discrete Mathematics**, 29-1 (2015), pp. 166-181. An extended abstract has appeared in the proceedings of**IPCO 2013**.**CP1.**On the convergence of the affine hull of the Chvatal-Gomory closures. With G. Averkov, M. Conforti, A. Del Pia, and M. Di Summa.**SIAM Journal on Discrete Mathematics**, 27-3 (2013).

Discrete Optimization ↔ Machine Learning

Typically, researchers in machine learning have looked at continuous optimization for techniques to solve their problems. However, in the last years, there has been a surge of research at the intersection of machine learning and discrete optimization. On one hand, can discrete optimization techniques solve problems arising in machine learning? On the other hand, can machine learning be used to solve complex discrete optimization problem faster?

My research here has focused on showing how certain impossibility results in machine learning can be transferred to results of a similar flavour in optimization (**ML2**), as well as in showing how machine learning can be embedded in integer programming solvers, as to increase their performance (**ML1**).

**ML2.**New limits of treewidth-based tractability in optimization. With G. Munoz and S. Pokutta. Accepted for publication in**Mathematical Programming**.**ML1.**Reinforcement learning for integer programming: learning to cut. With Y. Tang and S. Agrawal. Proceedings of**ICML 2020**.

Miscellanea on polytopes

I have further worked on other geometric problems, mostly on polytopes. These include: an investigation of an intriguing yet very common class of polytopes called *2-level*, with connections to statistic and the celerated *log-rank conjecture* in theoretical computer science: see **MI2, MI3**; algorithms for finding certain substructures in polytopes, with connections to submodular functions and largest subdeterminants of matrices: see **MI1, MI4**.

**MI4.**__Slack matrices, k-products, and 2-level polytopes.__. With M. Aprile, M. Conforti, S. Fiorini, T. Huynh, and M.Macchia. Accepted for publication in**Discrete Applied Mathematics**. An extended abstract has appeared in the proceedings of**CTW 2020**.**MI3.**Enumeration of 2-level polytopes. With A. Bohn, S. Fiorini, V. Fisikopoulos, M. Macchia, and K. Pashkovich.**Mathematical Programming Computation**, 11-1 (2019), pp. 173-210. An extended abstract has appeared in the proceedings of**ESA 2015**.**MI2.**On 2-level polytopes arising in combinatorial settings. With M. Aprile and A. Cevallos.**SIAM Journal on Discrete Mathematics**, 32-3 (2018), pp. 1857-1886. An extended abstract has appeared in the proceedings of**ISCO 2016**.**MI1.**On largest volume simplices and sub-determinants. With M. Di Summa, F. Eisenbrand, and C. Moldenhauer. Proceedings of**SODA 2015**.