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, EF12 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 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.

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 / von Neumann-Morgenstern assignments (MP7, MP14), matchings with blocking costs (MP9), problems where preferences of agents are described by choice functions (MP11), and stable matchings in two-stage settings (MP16). Some of those algorithms rely on and / or extend more general mathematical techniques, such as posets associated to sets of matchings and Birkhoff's representation theorem (see MP11, MP16), or pivoting procedures like Scarf's algorithm (see MP15). I have also investigated real-world applications of the theory of stable matchings and matching markets more generally 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.

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), total matching (KP10), 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.

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.

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).

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; pivoting algorithms, see MI5.