Explaining why the simplex method is fast in practice, despite it taking exponential time in the theoretical worst case, continues to be a challenge. Smoothed analysis is a paradigm for addressing this question. During my talk I will present recent progress in the smoothed complexity of the simplex method, discussing both upper and lower bounds.

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k = 0 (bipartite graphs) and for k = 1. We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching. This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky.

Cutting planes are a crucial component of state-of-the-art mixed-integer programming solvers, with the choice of which subset of cuts to add being vital for solver performance. We propose new distance-based measures to qualify the value of a cut by quantifying the extent to which it separates relevant parts of the relaxed feasible set. For this purpose, we use the analytic centers of the relaxation polytope or of its optimal face, as well as alternative optimal solutions of the linear programming relaxation. We assess the impact of the choice of distance measure on root node performance and throughout the whole branch-and-bound tree, comparing our measures against those prevalent in the literature. Finally, by a multi-output regression, we predict the relative performance of each measure, using static features readily available before the separation process. Our results indicate that analytic center-based methods help to significantly reduce the number of branch-and-bound nodes needed to explore the search space and that our multiregression approach can further improve on any individual method.

Bounding the combinatorial diameter of a polytope is a well-known and long-standing open problem. The great theoretical and practical interest in this question originates from the desire to efficiently solve linear programming. In this regard, since the ultimate goal is to optimize over polytopes, it is well worth looking at extended formulations as well. In this talk we will discuss polytope extensions having surprisingly small combinatorial diameter. Joint work with Volker Kaibel.

It is known how to find an orientation of an undirected graph that satisfies edge-connectivity contraints by the results of Nash-Williams. The situation for vertex-connectivity is more difficult. Thomassen showed how to find a 2-vertex-connected orientation, while Durand de Gevigney proved that the k-vertex-connectivity orientation problem is NP-complete for k>=3. We show that for mixed graphes already the 2-vertex-connected orientation problem is NP-complete. We also show that for hypergraphs the 1-edge-connected Steiner orientation problem is NP-complete. This follows from the surprising fact that it is NP-complete to decide whether a hypergraph contains a Steiner hypertree. This is a joint work with Florian Hörsch.

We focus on convex semi-infinite programs with an infinite number of quadratically parametrized constraints. In our setting, the lower-level problem, i.e., the problem of finding the constraint that is the most violated by a given point, is not necessarily convex. First we derive a convergence rate in O(1/k) for the Cutting Plane algorithm in the case where the objective function is strongly convex, and under a strict feasibility assumption. Second we propose a new approach to solve these semi-infinite programs, that generates a sequence of feasible solutions. Based on the Lagrangian dual of the lower-level problem, we derive a convex and tractable restriction of the semi-infinite program. We state sufficient conditions for the optimality of this restriction. If these conditions are not met, the restriction is enlarged through an Inner-Outer Approximation Algorithm, and its value converges to the value of the original semi-infinite program. This new algorithmic approach is tested on two applications (a constrained quadratic regression and a zero-sum game with cubic payoff) and compared with the classical Cutting Plane algorithm, the Mitsos algorithm and the KKT-based relaxation approach.

Von Neumann-Morgenstern (vNM) stability is a classical solution concept in game theory. We investigate its specialization to matchings. A set S of matchings of a graph G is defined to vNM stable if, for each M, M' in S, no edge of M blocks M' [internal stability] and for each matching M not in S, there is a matching M' \in S that contains an edge blocking M [external stability]. In this talk, we first extensively review popular modifications of the classical concept of stability in matching theory, and well-known algebraic properties of stable matchings. We then show how the latter can be exploited and extended to investigate structural and algorithmic questions on vNM stable sets of matchings.

In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This beautiful conjecture, if true, has implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts. This resolves an open question of Olver and Zenklusen from 2013, a work that showed thin trees exist for chains of cuts. As a byproduct, we also obtain a constant factor approximation algorithm for the laminar-constrained spanning tree problem with multiplicative violation. Based on joint work with Neil Olver.

We present a new approximation algorithm for the (metric) prize-collecting traveling salesperson problem (PCTSP). In PCTSP, opposed to the classical traveling salesperson problem (TSP), one may not include a vertex of the input graph in the returned tour at the cost of a given vertex-dependent penalty, and the objective is to balance the length of the tour and the incurred penalties for omitted vertices by minimizing the sum of the two. We present an algorithm that achieves an approximation guarantee of 1.774 with respect to the natural linear programming relaxation of the problem. This significantly reduces the gap between the approximability of classical TSP and PCTSP, beating the previously best known approximation factor of 1.915. As a key ingredient of our improvement, we present a refined decomposition technique for solutions of the LP relaxation, and show how to leverage components of that decomposition as building blocks for our tours.

Cutting planes for mixed-integer linear programs (MILPs) are typically computed in rounds by iteratively solving optimization problems, the so-called separation. Instead, we reframe the problem of finding good cutting planes as a continuous optimization problem over weights parametrizing families of valid inequalities. This problem can also be interpreted as optimizing a neural network to solve an optimization problem over subadditive functions, which we call the subadditive primal problem of the MILP. To do so, we propose a concrete two-step algorithm, and demonstrate empirical gains when optimizing generalized Gomory mixed-integer inequalities over various classes of MILPs.

Handling symmetries in optimization problems is essential for devising efficient solution methods. In this presentation, I present a general framework that captures many of the already existing symmetry handling methods (SHMs). While these SHMs are mostly discussed independently from each other, our framework allows to apply different SHMs simultaneously and thus outperforming their individual effect. Moreover, most existing SHMs only apply to binary variables. Our framework allows to easily generalize these methods to general variable types. Numerical experiments confirm that our novel framework is superior to the state-of-the-art SHMs implemented in the solver SCIP. This is joint work with Jasper van Doornmalen.

One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. While prior techniques assume covering constraints on the clients, they do not address additional constraints on the facilities, which has been extensively studied in non-colorful settings. In this talk, we present a framework to deal with various constraints on the facilities in the colorful setting. To exemplify our framework, we show how it leads, to a approximation algorithm exponential in the number of colors for Colorful Matroid Supplier with respect to a linear matroid. Joint work with Georg Anegg and Rico Zenklusen.

In the Submodular Facility Location problem (SFL) we are given a collection of n clients and m facilities in a metric space. A feasible solution consists of an assignment of each client to some facility. For each client, one has to pay the distance to the associated facility. Furthermore, for each facility f to which we assign the subset of clients S_f, one has to pay the opening cost g(S_f), where g(·) is a monotone submodular function with g(\emptyset) = 0. SFL is APX-hard since it includes the classical (metric uncapacitated) Facility Location problem (with uniform facility costs) as a special case. Svitkina and Tardos [SODA’06] gave the current-best O(log n) approximation algorithm for SFL. The same authors pose the open problem whether SFL admits a constant approximation and provide such an approximation for a very restricted special case of the problem. We make some progress towards the solution of the above open problem by presenting an O(log log n) approximation. Our approach is rather flexible and can be easily extended to generalizations and variants of SFL. In more detail, we achieve the same approximation factor for the practically relevant generalizations of SFL where the opening cost of each facility f is of the form p_f + g(S_f) or w_f · g(S_f), where p_f, w_f ? 0 are input values. We also obtain an improved approximation algorithm for the related Universal Stochastic Facility Location problem. In this problem one is given a classical (metric) facility location instance and has to a priori assign each client to some facility. Then a subset of active clients is sampled from some given distribution, and one has to pay (a posteriori) only the connection and opening costs induced by the active clients. The expected opening cost of each facility f can be modeled with a submodular function of the set of clients assigned to f.

This talk considers combinatorial properties of physical networks like water, gas, heat, and electrical networks. One common model is given by potential-based flows, for which, in general, the corresponding flows depend in a nonlinear way on potentials (e.g., pressures) and are unique. The talk will review three different topics. The first is how the fact that flows in physical networks are acyclic can be used to strengthen mixed-integer optimization formulations and to derive combinatorial models. The second concerns the recovery of the structure of the network, given only information at the entries and exits. The talk will demonstrate positive and negative results in this direction. The third deals with the robustness of physical networks against failures of connections or components. An optimal design of networks that are robust in this sense yields a three level optimization problem, which can be solved using a doubly nested Benders algorithm. Moreover, symmetry can be exploited to speed up the solution process.

We study dynamic traffic assignment with side-constraints. We first give a counter-example to a key result from the literature regarding the existence of dynamic equilibria for volume-constrained traffic models in the classical edge-delay model. Our counter-example shows that the feasible flow space need not be convex and it further reveals that classical infinite dimensional variational inequalities are not suited for the definition of side-constrained dynamic equilibria. We propose a new framework for side-constrained dynamic equilibria based on the concept of feasible ?-deviations of flow particles in space and time. Under natural assumptions, we characterize the resulting equilibria by means of quasi-variational and variational inequalities, respectively. Finally, we establish first existence results for side-constrained dynamic equilibria for the non-convex setting of volume-constraints.

In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta, Talwar and Witmer [STOC 2013] obtained a 2-approximation with polynomial running time for fixed k, and the question of whether there exists a c-approximation algorithm for a constant c independent of k, that runs in FPT time, remained open. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time.

There has been significant work recently on integer programs (IPs) min {c^Tx : Ax ≤ b, x ∈ ℤⁿ } with a constraint marix A with bounded subdeterminants. This is motivated by a well-known conjecture claiming that, for any constant positive integer Δ, Δ-modular IPs are efficiently solvable, which are IPs where the m by n constraint matrix A has full column rank and all n by n minors of A are within {-Δ, …, Δ}. Previous progress on this question, in particular for Δ = 2, relies on algorithms that solve an important special case, namely strictly Δ-modular IPs, which further restrict the n by n minors of A to be within {-Δ, 0, Δ}. Even for Δ = 2, such problems include well-known combinatorial optimization problems like the minimum odd/even cut problem. The conjecture remains open even for strictly Δ-modular IPs. Prior advances were restricted to prime Δ, which allows for employing strong number-theoretic results. In this work, we make first progress beyond the prime case by presenting techniques not relying on such strong number-theoretic prime results. In particular, our approach implies that one can check feasibility of strictly Δ-modular IPs in strongly polynomial time if Δ ≤ 4.

We consider optimal control problems for partial differential equations where the controls take binary values but vary over the time horizon, they can thus be seen as dynamic switches. The switching patterns may be subject to combinatorial constraints such as, e.g., an upper bound on the total number of switchings or a lower bound on the time between two switchings. While such combinatorial constraints are often seen as an additional complication that is treated in a heuristic postprocessing, the core of our approach is to investigate the convex hull of all feasible switching patterns in order to define a tight convex relaxation of the control problem. The convex relaxation is built by cutting planes derived from finite-dimensional projections, which can be studied by means of polyhedral combinatorics. A numerical example for the case of a bounded number of switchings shows that our approach can significantly improve the dual bounds given by the straightforward continuous relaxation, which is obtained by relaxing binarity constraints.

Combinatorial optimization (CO) layers in machine learning (ML) pipelines are a powerful tool to tackle data-driven decision tasks, but they come with two main challenges. First, the solution of a CO problem often behaves as a piecewise constant function of its objective parameters. Given that ML pipelines are typically trained using stochastic gradient descent, the absence of slope information is very detrimental. Second, standard ML losses do not work well in combinatorial settings. A growing body of research addresses these challenges through diverse methods. Unfortunately, the lack of well-maintained implementations slows down the adoption of CO layers. In this work, building upon previous works, we introduce a probabilistic perspective on CO layers, which lends itself naturally to approximate differentiation and the construction of structured losses. We recover many approaches from the literature as special cases, and we also derive new ones. Based on this unifying perspective, we present InferOpt.jl, an open-source Julia package that~1) allows turning any CO oracle with a linear objective into a differentiable layer, and~2) defines adequate losses to train pipelines containing such layers. Our library works with arbitrary optimization algorithms, and it is fully compatible with Julia's ML ecosystem. We demonstrate its abilities on several operations research applications.

Given a graph G = (V;E) and an integer k>=1, the graph H = (V; F), where F is a family of elements of E, is a k-edge-connected spanning subgraph of G if H cannot be disconnected by deleting any k-1 elements of F. The convex hull of the k-edge-connected subgraphs of a graph G forms the k-edge-connected subgraph polyhedron of G. We prove that this polyhedron is box-totally dual integral if and only if G is series-parallel. In this case, we also provide an integer box-totally dual integral system describing this polyhedron.

We consider the Uniform Cost-Distance Steiner Tree Problem in metric spaces, a generalization of the well-known Steiner tree problem. Cost-distance Steiner trees minimize the sum of the total length and the weighted path lengths from a dedicated root to the other terminals, which have a weight to penalize the path length. They are applied when the tree is intended for signal transmission, e.g. in chip design or telecommunication networks, and the signal speed through the tree has to be considered besides the total length. Constant factor approximation algorithms for the uniform cost-distance Steiner tree problem have been known since the first mentioning of the problem by Meyerson, Munagala, and Plotkin. Recently, the approximation factor was improved from 2.87 to 2.39 by Khazraei and Held. We refine their approach further and reduce the approximation factor down to 2.15. This is joint work with Yannik Kyle Dustin Spitzley.

We introduce a novel measure for quantifying the error in input predictions. The error is based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a general template which we apply to online graph problems. The measure captures errors due to absent predicted requests as well as unpredicted actual requests; hence, predicted and actual inputs can be of arbitrary size. We achieve refined performance guarantees for previously studied network design problems in the online-list model, such as Steiner tree and facility location. Further, we initiate the study of learning-augmented algorithms for online routing problems, such as the online traveling salesperson problem and the online dial-a-ride problem, where (transportation) requests arrive over time (online-time model). We provide a general algorithmic framework and we give error-dependent performance bounds that improve upon known worst-case barriers, when given accurate predictions, at the cost of slightly increased worst-case bounds when given predictions of arbitrary quality. This is joint work with Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow and Michelle Sweering

We introduce a new cooperative game theory model that we call production-distribution game to address a major open problem for operations research in forestry, raised by R{\"o}nnqvist et al. in 2015, namely, that of modelling and proposing efficient sharing principles for practical collaboration in transportation in this sector. The originality of our model lies in the fact that the value/strength of a player does not only depend on the individual cost or benefit of the goods she owns but also on her market shares (customers demand). We show that our new model is an interesting special case of a market game introduced by Shapley and Shubik in 1969. As such it exhibits the property of having a non-empty core. We prove that we can compute both the nucleolus and the Shapley value efficiently, in a nontrivial, interesting special case. We provide two algorithms to compute the nucleolus: a simple separation algorithm and a fast primal-dual one. We also show that our results can be used to tackle more general versions of the problem and we believe that our contribution paves the way towards solving the challenging open problems herein.

Flexible graph connectivity is a new network design model introduced by Adjiashvili. Algorithm design for this model has posed novel technical challenges. The talk will outline some recent advances and point out the open problems.

The Branch-and-Bound algorithm is a well-known method for solving integer linear programs. In the worst case this algorithm achieves an exponential running time, but until recently very little about was known about its behaviour on random instances. We show that for certain classes of random ILP's, the running time is only polynomial. To prove this result we solve a discrepancy problem for random matrices using Fourier analysis.

The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics. However, we maintain that this is a flawed approach because compactness and fairness are orthogonal qualities; to achieve a meaningful notion of fairness, one needs to model political and demographic considerations, using historical data. We will discuss two papers that explore and develop this perspective. In the first (joint with Wes Gurnee), we present a scalable approach to explicitly optimize for arbitrary piecewise-linear definitions of fairness; this employs a stochastic hierarchical decomposition approach to produce an exponential number of distinct district plans that can be optimized via a standard set partitioning integer programming formulation. This enables the largest-ever ensemble study of congressional districts, providing insights into the range of possible expected outcomes and the implications of this range on potential definitions of fairness. In the second paper (joint with Nikhil Garg, Wes Gurnee, and David Rothschild), we study the design of multi-member districts (MMDs) in which each district elects multiple representatives, potentially through a non-winner-takes-all voting rule (as currently proposed in H.R. 4000). We carry out large-scale analyses for the U.S. House of Representatives under MMDs with different social choice functions, under algorithmically generated maps optimized for either partisan benefit or proportionality. We find that with three-member districts using Single Transferable Vote, fairness-minded independent commissions can achieve proportional outcomes in every state (up to rounding), and this would significantly curtail the power of advantage-seeking partisans to gerrymander.

In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (weighted) completion time. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in online algorithm design. We discuss different prediction models and error measures, and we show a learning-augmented algorithmic framework with strong performance guarantees. Further, we discuss the power of speed predictions for non-clairvoyant scheduling on heterogenous machines of unknown speed.

We consider a matching problem in a bipartite graph G=(A?B,E) where each node in A is an agent having preferences in partial order over her neighbors, while nodes in B are objects with no preferences. The size of our matching is more important than node preferences; thus, we are interested in maximum matchings only. Any pair of maximum matchings in G (equivalently, perfect matchings or assignments) can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute an assignment M such that there is no better or "more popular" assignment. This is the popular assignment problem and it generalizes the well-studied popular matching problem. Popular assignments need not always exist. We show a polynomial-time algorithm that decides if the given instance admits one or not, and computes one, if so. In instances with no popular assignment, we consider the problem of finding an almost popular assignment, i.e., an assignment with minimum unpopularity margin. We show an O*(|E|^k) time algorithm for deciding if there exists an assignment with unpopularity margin at most k. Moreover, we show that this algorithm is essentially optimal by proving that the problem is W_l[1]-hard with parameter k. Our algorithms are combinatorial and based on LP duality. They search for an appropriate witness or dual certificate, and when a certificate cannot be found, we prove that the desired assignment does not exist in G. This is joint work with Telikepalli Kavitha, Tamás Király, Jannik Matuschke, and Ildikó Schlotter.

One of the most impactful tools for computer-assisted proofs in mathematics is due to Razborov, who introduced flag algebras in 2007 in order to study the limits of discrete objects in Extremal Combinatorics using concepts from First-Order Logic and Model Theory. They allow one to apply a Cauchy-Schwarz-type argument to classic problems in Turán and Ramsey theory by solving a concrete semidefinite programming formulation. In this talk we will explore both a computational counterpart that allows one to derive matching constructive bounds as well as ways of exploring symmetries in the flag algebra problem formulations in order to reduce their size. Both extend the envelope of what is attainable and we use them to obtain improved and sometimes even tight bounds on some classic problems in extremal graph theory.

In a Stackelberg Network Pricing game, one Player called the Leader controls the prices/weights of some entities (vertices or edges) of the underlying graph. The remaining weights are constant and known to the Leader. The other players, called followers, each have a subgraph on which they independently solve a (combinatorial) optimization problem given the prices defined by the Leader. The problem then asks for a pricing scheme that maximizes the Leader's revenue which corresponds to the prices of the entities contained in any of the followers' solutions. I consider the problem Stackelberg Vertex Cover (StackVC) with a single follower, i.e., the Leader controls the prices of some vertices, and the follower aims to find a vertex cover of the graph with minimum weight. Previous research has shown that StackVC is NP-hard on general bipartite graphs. To find the complexity boundary of the problem, I investigated paths – arguably the simplest types of a bipartite graphs. I propose a dynamic program with linear complexity to determine optimal prices from the Leader's perspective. With minor adaptions, this algorithm also extends to trees and forests. While the exact complexity boundary remains unknown, this remains one of very few positive results in the Stackelberg setting.

We study mixed integer nonlinear programs (MINLPs) and consider compact mixed integer linear relaxtions that reframe the nonconvexities of the program using extended formulations with binary variables. We discuss compact models in the context of MIQP and also in the context of objective functions with ratios of variables. For both cases, we develop novel relaxations that include discretizations that use an underlying gray code sequence. These models roughly fit into the framework work by Vielma and Nemhauser, but due to the specific problems, our models are more compact than their demonstrates. We show how the gray code structure results the models being "hereditarily sharp," meaning that they continue to be sharp throughout the branch and bound tree. This work comes from three recent papers with cumulative co-authors Ben Beach, Joey Huchette, Lukas Hagar, Robert Burlacu.

The Simplex method is one of the most popular algorithms for solving linear programs, but despite decades of study, it is still not known whether there exists a pivot rule that guarantees it will always reach an optimal solution with a polynomial number of pivots. In fact, a polynomial pivot rule is not even known for linear programs over 0/1 polytopes (0/1-LPs), despite the fact that the diameter of a 0/1 polytope satisfies the Hirsch bound. In this talk, I will discuss recent results in the area.

We design primal and dual bounding methods for multistage adjustable robust optimization (MSARO) problems by adapting two families of decision rules rooted in stochastic programming literature. This framework approximates the primal and dual formulations of an MSARO problem with two-stage models. We develop several solution methods for the obtained approximations. Our framework is general-purpose and does not require strong assumptions such as a temporal independent stochastic progress, and can consider integer adjustable decision variables. This is joint work with Maryam Daryalal and Ayse Nur Arslan.

We consider the bilevel knapsack problem with interdiction constraints, a fundamental bilevel integer programming problem which generalizes the 0-1 knapsack problem. In this problem, there are two knapsacks and n items. The objective is to select some items to pack into the first knapsack such that the maximum profit attainable from packing some of the remaining items into the second knapsack is minimized. Previous exact methods for solving this problem make use of mixed-integer linear programming solvers. We present a combinatorial branch-and-bound algorithm which outperforms the current state-of-the-art solution method in computational experiments by 4.5 times on average for all instances reported in the literature. Our algorithm is simple: a basic implementation takes less than 200 lines of code. More drastic performance improvements are seen for more challenging instances: on 20% of instances, our algorithm is at least 64 times faster, and we solved 53 of the 72 previously unsolved instances. Our result relies fundamentally on a new dynamic programming algorithm which computes very strong lower bounds. This dynamic program relaxes the problem from bilevel to 2n-level by ordering the items and solving an online version of the problem. The relaxation is easier to solve but approximates the original problem surprisingly well in practice. We believe that this same technique may be useful for other interdiction problems.

S-free sets are known to have a variety of applications, perhaps most notably in the generation of intersection cuts. When it comes to generating cuts using S-free sets, inclusion-wise maximal sets generate stronger cuts. In this talk we consider maximal S-free sets when S is defined by a quadratic inequality. We demonstrate that maximal quadratic-free sets can be generated using a map from an n-sphere to an m-sphere. Conversely, any such map that is also non-expansive defines a maximal S-free polyhedron. Underlying our work is a characterization of (not necessarily quadratic) maximal S-free sets, which allows us to also generate non-polyhedra maximal quadratic-free sets. This is joint work with Gonzalo Munoz and Felipe Serrano.

In this talk, we introduce an alternative model for the design and analysis of strategyproof mechanisms that is motivated by the recent surge of work in "learning-augmented algorithms". Aiming to complement the traditional approach in computer science, which analyzes the performance of algorithms based on worst-case instances, this line of work has focused on the design and analysis of algorithms that are enhanced with machine-learned predictions regarding the optimal solution. The algorithms can use the predictions as a guide to inform their decisions, and the goal is to achieve much stronger performance guarantees when these predictions are accurate (consistency), while also maintaining near-optimal worst-case guarantees, even if these predictions are very inaccurate (robustness). So far, these results have been limited to algorithms, but in this work we argue that another fertile ground for this framework is in mechanism design. We initiate the design and analysis of strategyproof mechanisms that are augmented with predictions regarding the private information of the participating agents. To exhibit the important benefits of this approach, we revisit the canonical problem of facility location with strategic agents in the two-dimensional Euclidean space. We study both the egalitarian and utilitarian social cost functions, and we propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees. This provides the designer with a menu of mechanism options to choose from, depending on her confidence regarding the prediction accuracy. Furthermore, we also prove parameterized approximation results as a function of the prediction error, showing that our mechanisms perform well even when the predictions are not fully accurate. We will conclude by discussing other exciting recent results in this new area of learning-augmented mechanism design. Joint work with Priyank Agrawal, Vasilis Gkatzelis, Tingting Ou, and Xizhi Tan

The Matroid Secretary Conjecture is a notorious open problem in online optimization. It claims the existence of a constant-competitive algorithm for the Matroid Secretary Problem (MSP). Here, the elements of a weighted matroid appear one-by-one, revealing their weight at appearance, and the task is to select elements online with the goal to get an independent set of largest possible weight. O(1)-competitive MSP algorithms have so far only been obtained for restricted matroid classes and for MSP variations, including Random-Assignment MSP (RA-MSP), where an adversary fixes a number of weights equal to the ground set size of the matroid, which then get assigned randomly to the elements of the ground set. Unfortunately, these approaches heavily rely on knowing the full matroid upfront. This is an arguably undesirable requirement, and there are good reasons to believe that an approach towards resolving the MSP Conjecture should not rely on it. Thus, both Soto [SIAM Journal on Computing 2013] and Oveis Gharan & Vondrak [Algorithmica 2013] raised as an open question whether RA-MSP admits an O(1)-competitive algorithm even without knowing the matroid upfront. In this work, we answer this question affirmatively. Joint work with Ivan Sergeev and Rico Zenklusen.

The idea of learning branching rules from data has received increasing attention recently, and promising results have been obtained by learning fast approximations of the strong branching expert. In this talk, we will discuss a different paradigm: learnint to branch from scratch via Reinforcement Learning (RL).

Intersection cuts can tighten a polyhedral outer approximation of a non-convex set. We study intersection cuts for submodular and submodular-supermodular maximization problems. We construct corresponding S-free sets and propose a cut computation algorithm. We report our good and bad experiences with intersection cuts in max cut, maximization of Boolean multilinear functions, maximization of utility functions, and D-optimal design problems. We found experimentally and thus conjecture that intersection cuts hardly improve the polyhedral outer approximations of non-monotone submodular maximization problems and problems with convex MINLP problems. So, a new measure of cut efficiency in terms of the corner polyhedral relaxation is in need. This talk is based on a joint work with Leo Liberti.

We will discuss classical ways of addressing uncertainties in bilevel optimization using stochastic or robust techniques. The sources of uncertainty in bilevel optimization can be much richer than for usual, single-level problems, since not only the problem's data can be uncertain but also the (observation of the) decisions of the two players can be subject to uncertainty. Thus, we will also discuss bilevel optimization under limited observability, the area of problems considering only near-optimal decisions, and intermediate solution concepts between the optimistic and pessimistic cases. The talk is based on the article by Yasmine Beck, Ivana Ljubi?, Martin Schmidt: A Survey on Bilevel Optimization Under Uncertainty, https://optimization-online.org/2022/06/8963/