Mixed-integer mathematical programs are ubiquitous in Operations Research and related fields. However, there is still very little known about what can be expressed by compact mixed-integer programs with few integer variables. We provide a general framework for lifting inapproximability results for linear extended formulations to the mixed-integer setting, and obtain almost tight lower bounds on the number of integer variables needed to describe a variety of classical combinatorial optimization problems. Among the implications we obtain, we show that any mixed-integer extended formulation of sub-exponential size for the matching polytope, cut polytope, or dominant of the odd-cut polytope, needs Omega(n/log n) many integer variables, where n is the number of vertices of the underlying graph. Moreover, we can show that these bounds are optimal up to a logarithmic factor. Our results build upon a new decomposition technique that, for any convex set C, allows for approximating any mixed-integer description of C by the intersection of C with the union of a small number of affine subspaces. ---------- preference for talk format ---------- 5) only want to give a 30-minute talk. ------------------------------------------------

Integer programming problems that arise in combinatorial optimization often involve nonnegative or bounded decision variables. Using information about bounds on variables, one can generate, possibly stronger cuts valid for all integer feasible solutions. In this paper, we consider a natural extension of Chvatal-Gomory inequalities, which are obtained by strengthening Chvatal-Gomory inequalities based on bound constraints on some variables. These strengthened Chvatal-Gomory inequalities can also be viewed as cutting-planes from "wide split disjunctions", introduced by Bonami, Lodi, Tramontani, and Wiese recently. We prove that the closure of a rational polyhedron obtained after applying the generalized Chvatal-Gomory inequalities is also a rational polyhedron. Our technique is motivated by a result of Dunkel and Schulz, but it is very different from techniques to prove polyhedrality of Chvatal-Gomory closures and split closures. This is joint work with Sanjeeb Dash and Oktay Gunluk. I am okay to give either a 15-min talk or 30-min talk.

A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a number of inequalities that is polynomial in the number of inequalities that describe the two polytopes, then the number of additional variables is at least linear in the dimension of the polytopes. We then show that this result essentially carries over if one wants to approximate the convex hull of the union of two polytopes and also in the more restrictive setting of lift-and-project.

Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set S\cap P, where S is a closed set, and P is a polyhedron. Given an oracle that provides the distance from a point to S we construct a pure cutting plane algorithm; if the initial relaxation is a polytope, the algorithm is shown to converge. Cuts are generated from convex forbidden zones, or S-free sets derived from the oracle. We also consider the special case of polynomial optimization. Polynomial optimization may be represented using a symmetric matrix of variables, and in this lifted representation we can let S be the set of matrices that are real, symmetric outer products. Accordingly, we develop a theory of outer-product-free sets. All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify two families of such sets. These families can be used to generate intersection cuts that can separate any infeasible extreme point of a linear programming relaxation in polynomial time. Moreover, in the special case of polynomial optimization, we derive strengthened oracle-based intersection cuts that can also ensure separation in polynomial time.

The stochastic shortest path problem is an extension of the shortest path problem where destination nodes are now uncertain (not to be confused with uncertain arc length). It is also known as undiscounted infinite horizon Markov Decision Process. In this talk, we will discuss our recent contribution to the problem through the use of polyhedral analysis: we show in particular that the flow decomposition property holds for stochastic paths and this allows to revisit, generalise and simplify the existing proofs and algorithms for the problem. We will also discuss the interest of the corresponding problem for modelling stochastic problems with MIP formulations. --- I attach the slides I prepared last year for Aussois (but did not get the chance to present). I will add discussion about the use of SSP within MIP formulations

It is known (or assumed) that for constant capacity single node flow sets the corresponding flow cover inequalities suffice to describe the convex hull of solutions. Here we show that under certain conditions the result extends to paths, in the sense that only flow cover inequalities for the original or certain aggregated constraints need to be added. The resulting sets can be interpreted as variants of the classical Wagner-Whitin lot-sizing model in which the capacity constraints and the storage bounds (and not the demands) drive the model. Ok for Monday. 2) prefer a 30-minute talk over a 15-minute talk, but willing to do either;

Danial Davarnia and Gerard Cornuejols recently studied a class of quadratic stochastic programs where the distribution of random variables has unknown parameters. A traditional approach is to estimate the parameters using a maximum likelihood estimator (MLE) and to use this as input in the optimization problem. For the unconstrained case, we show that an estimator that “shrinks” the MLE towards an arbitrary vector yields a uniformly better risk than the MLE. In contrast, when there are constraints, we show that the MLE is admissible.

We bound the proximity of optimal solutions of integer programs and their mixed-integer and linear relaxations. Our proofs provide connections to extremal combinatorics and number theory. This extends a classic result of Cook, Gerards, Schrijver, and Tardos. This work was done in collaboration with Robert Weismantel and Stefan Weltge. I prefer a 30-minute talk.

We study the support of discrete optimization problems in standard form associated with an integral constraint matrix A. For such a system there always exists an integer optimal solution whose support is independent of the objective function. It is bounded by a function in m and the maximum absolute entry of A. (prefer a 15-minute talk over a 30-minute talk, but willing to do either)

One well-known application of Körner's graph entropy is in the context of sorting under partial information: Given a partial order P compatible with the linear order we are looking for, the problem is to make as few comparisons of the form "is x < y?" as possible to identify the linear order. In the early 1990's, Kahn and Kim showed that if G denotes the incomparability graph of P and H(G) denotes its entropy, the quantity |G|*H(G) approximates to within a constant factor the so-called information-theoretic lower bound (ITLB) for the problem in the decision tree model, the logarithm of the number of linear extensions of P. Building on this and the fact that H(G) can be approximated to any fixed precision in polynomial time when G is perfect, they developed a poly-time algorithm for the problem performing a number of comparisons bounded by c*ITLB for some constant c. A decade later, Yao raised the question of whether significantly better algorithms exist on quantum computers: Is there an efficient algorithm performing o(ITLB) comparisons? Conjecturing that the answer is no, Yao considered a natural quantum lower bound (QLB) in this setting and related it to graph entropy, by showing that QLB >= a*|G|*(H(G) - b) for some constants a, b > 0. To do so, he studied an "average" version of graph entropy. This almost proves his conjecture but for the pesky -b term: If the entropy H(G) is at least some constant > b, then QLB >= eps*ITLB for some eps > 0, as desired. However, the case of small entropy remains open. In this talk I will give a gentle introduction to this topic, focusing on elegant combinatorial and geometric ideas that emerged around graph entropy. I will also discuss some ongoing work on the small-entropy case of Yao's conjecture that we are pursuing together with Jean Cardinal and Jérémie Roland.

We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing phylogenetic trees. The extended formulation has only a polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Campêlo et al. (Math Progr 156:303–330, 2016). We show that all valid inequalities introduced by Campêlo et al. can be derived from the extended formulation. We also show that the natural restriction of the extended formulation provides a complete inequality description of the polytope of subtrees of a tree. The solution time using the extended formulation is much smaller than that with the conventional formulation. Moreover the extended formulation solves all the problem instances attempted in Campêlo et al. (2016) and larger sized instances at the root node of the branch-and-bound tree without branching. 3) prefer a 15-minute talk over a 30-minute talk, but willing to do either;

I will introduce 2-level polytopes and the wide open, fascinating question of their extension complexity. Then I will present the only known lower bound on the extension complexity of a 2-level polytope, more precisely the stable set polytope of some bipartite graphs coming from finite projective planes (joint work with Faenza, Fiorini, Huynh, Macchia). I prefer a 30-minute talk over a 15-minute talk, but willing to do either;

We consider the bulk-robust assignment problem in which we are given a bipartite graph, edge costs, an integer k and a list of failure (edge) sets. The goal is to find minimum-cost subset of edges such that after the removal of any failure set, the remaining subgraph still contains a matching of size k. A recent result is an approximation algorithm for the case in which failures consist of single edges. We discuss a straight-forward integer programming model, improve the tractability of its LP relaxation, present cutting planes that are very strong and discuss the associated separation problem. Preliminary computational results for solving these problems to optimality are presented. They indicate effectiveness for such structured instances, whereas the LP relaxations for instances with random failure sets are rather weak.

In the field of computational molecular design a frequently asked question is about the different states of the molecules during the whole biological process, e.g., a catalyst. If the underlying Markov process is non-reversible, i.e., forward and backward probability between two states are different, there is – to the best of our knowledge – no established method to determine a clustering of the different states of molecules, which describe the different states of the catalyst itself, that can be proven to be optimal. In this talk, we present a new, optimization-based method to exhibit cyclic behavior in these non-reversible stochastic processes. We address this task using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability which can be interpreted as the effectiveness of the catalyst. This optimization problem turned out to be very hard to solve for both commercial and non-commercial MIP solvers. In order to tackle this problem, we studied valid inequalities and were able to prove which are facet defining for the corresponding cycle-clusting polytope. An implementation of these techniques within the academic MIP solver SCIP lead to a reduction of solving time by a factor of 3.

In this paper we propose a new use of Machine Learning together with Mathematical Optimization. We investigate the question of whether a machine, trained on a large number of optimized solutions, can accurately estimate the value of the optimized solution for new instances. We focus on instances of a specific problem, namely, the offshore wind farm layout optimization problem. In this problem an offshore site is given, together with the wind statistics and the characteristics of the turbines that need to be built. The optimization wants to determine the optimal allocation of turbines to maximize the park power production, taking the mutual interference between turbines into account. Mixed Integer Programming models and other state-of-the-art optimization techniques, have been developed to solve this problem. Starting with a dataset of 2000+ optimized layouts found by the optimizer, we used supervised learning to estimate the production of new wind parks. Our results show that Machine Learning is able to well estimate the optimal value of offshore wind farm layout problems.

[this is a 15 minute short talk] Applying a Dantzig-Wolfe decomposition to a mixed-integer program (MIP) aims at exploiting an embedded model structure and can lead to significantly stronger reformulations of the MIP. Recently, automating the process and embedding it in standard MIP solvers have been proposed, with the detection of a decomposable model structure as key element. If the detected structure reflects the (usually unknown) actual structure of the MIP well, the solver may be much faster on the reformulated model than on the original. Otherwise, the solver may completely fail. We propose a supervised learning approach to decide whether or not a reformulation should be applied, and which decomposition to choose when several are possible. Preliminary experiments with a MIP solver equipped with this knowledge show a significant performance improvement on structured instances, with little deterioration on others.

Degeneracy in MIP: Mixed integer programs arising from practical applications typically feature highly degenerate solutions to their LP relaxation. Consequently, these LPs have multiple optimal solutions, often both in the primal and the dual space. This degeneracy is arguably the main reason for performance variability of LP based MIP solvers. In recent years, various authors have investigated different aspects of LP degeneracy in MIP solving. One line of research is to try to exploit degeneracy in order to improve the performance of MIP solvers or to reduce the solvers' variability. Examples are Zanette's, Fischetti's, and Balas' work on using the lexicographic simplex for Gomory cuts, the "pump reduce" step in CPLEX, or the "degenerate reduced cost fixing" implemented in the SAS/OR solver. Most recently, Bajgiran, Cire, and Rousseau presented a more systematic way to pick dual optimal LP solutions in order to improve reduced cost fixing. This talk provides a survey of some of these approaches and explains how Gurobi is exploiting LP degeneracy. Computational results assess the practical impact of the various techniques. **************************************************** The Aussois Shortest Path Problem: The ASSP means to find the shortest path from the bar to ones bedroom. Due to the layout of the conference building, this is a challenging task for human beings. The underlying graph is connected and does not contain negative cycles, which means that the problem is in theory easy to solve by a polynomial algorithm. Nevertheless, the problem remained unsolved for 22 years. The main issue, as in most practical applications, is the lack of data. The slide deck at hand provides a first step to tackle the problem by providing a graph with edge lengths that models the building. As usual, the data are certainly incomplete and error-prone. Moreover, it comes (as always in real-world applications) in a completely unusable format, in this case a pdf file derived from a Powerpoint presentation. We hope to encourage research for this important problem so that we can see some interesting results on the topic in upcoming Aussois workshops.

We evaluate computationally the new normalization of Conforti and Wolsey in the context of Benders decomposition. The implementation is based on a development version of CPLEX. (have no preference and can accommodate both formats)

One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well-known McCormick relaxation for a bilinear product of two variables x and y over a box-constrained domain. The starting point of this talk is the fact that these may be far from tight if the feasible region and its convexification projected in the x-y-space is a strict subset of the box. We develop an algorithm that solves a sequence of linear programs in order to compute globally valid inequalities on x and y in a similar fashion as optimization-based bound tightening. These valid inequalities allow us to exploit polyhedral results from the literature in order to tighten the classical McCormick relaxation. As a consequence we obtain a convexification procedure that can exploit objective cutoff information during branch-and-bound. We use the MINLP solver SCIP to analyze the impact of the tighter relaxations on instances of the MINLPLib2. This is joint work with Benjamin Müller and Felipe Serrano.

We consider two variants of stochastic graph covering problems. First, we consider a covering problem on a random graph, where the probability distribution of whether an arc appears in the graph is given. Our goal is to identify a subset of vertices in this graph so that the expected number of total vertices “covered” (i.e., are reachable from these selected vertices) in the random graph is maximized. Second, we consider a chance-constrained set covering problem, where the probability of satisfying the chance constraint can be computed exactly via an oracle. For both classes of problems, we give delayed constraint generation algorithms. We show that the submodularity of the coverage function can be exploited to enhance the performance of the algorithms. We report our computational results with the proposed methods. This is joint work with Hao-Hsiang Wu.

We consider Lagrangian dual decision rules for multi-stage stochastic integer programming problems. We investigate techniques for using these decision rules to obtain bounds on the optimal solution and a primal policy, and compare the strength of the relaxation from different techniques. Preliminary numerical results will be presented. This is joint work with Merve Bodur.

Any proper coloring of a Kneser graph with a minimum number of colors contains an almost-complete bipartite subgraph with all colors on each side. (An almost-complete bipartite graph is a complete bipartite graph minus a perfect matching.) This is a theorem due to Chen (2012), which solved a conjecture about the circular chromatic number of Kneser graphs. We prove that such a "colorful" subgraph still exists for the generalized Kneser graphs (obtained from any hypergraph), and for their categorical products, when they match a certain topological lower bound for the chromatic number (Dol’nikov’s bound). This result has some consequences for the circular chromatic number and Hedetniemi’s conjecture. Joint work with Meysam Alishahi and Hossein Hajiabolhassan.

Abstract: We consider situations in which resources of limited capacity are commonly used by several participants. Such situations occur, for example, in scheduling, where jobs need to be assigned to machines, in routing, where traffic needs to be sent between certain origin-destination pairs through a network, or in broadcasting, where messages are sent along spanning trees in some undirected graph. Throughout the talk, we will investigate the impact of changes in the input parameters, like resource capacity or demand, towards optimal solutions and equilibria. As it turns out, as long as the underlying feasibility region forms a polymatroid and the cost function satisfies certain convexity conditions, things behave nicely: small changes of the input parameter ensure that new optimal solution can be optained by only a few changes. We use these proximity results to prove the existence of equilibria in associated congestion games. (Joint work with Tobias Harks and Max Klimm.)

We present an algorithm that computes a Boolean circuit for an \aop~(i.e., a formula of type $t_0 \land (t_1 \lor (t_2 \land ( \dots t_{m-1}) \dots )$ or $t_0 \lor (t_1 \land (t_2 \lor ( \dots t_{m-1}) \dots )$) with given arrival times for the input signals. Our objective function is delay, a generalization of depth. The maximum delay of the circuit we compute is $\log_2 W + \log_2 \log_2 m + \log_2 \log_2 \log_2 m + 5$, where $\lceil \log_2 W \rceil$ is a lower bound on the delay of any circuit depending on inputs $t_0, \dotsc, t_{m-1}$ with prescribed arrival times. Since the carry bit computation in adders reduces to evaluating \aop s, up to a small additive constant, an adder with the same delay can be constructed. Our method yields the fastest circuits both for \aop s and adders in terms of delay known so far.

Minimizing the sum of weighted completion times on m identical parallel machines is one of the most important classical scheduling problems. For the stochastic variant where processing times of jobs are random variables, in 1999, Möhring, Schulz, and Uetz presented the first and still best known approximation result, achieving, for arbitrarily many machines, performance guarantee 1 + ½ (1+Delta), where Delta is an upper bound on the squared coefficient of variation of the processing times. We prove performance guarantees 1 + ½ (sqrt(2) - 1) (1+Delta) for arbitrary Delta and 1 + 1/6 (1+Delta) for Delta >= 1 for the same underlying algorithm—the Weighted Shortest Expected Processing Time (WSEPT) rule. For the special case of deterministic scheduling (i.e. Delta = 0), our bound matches the tight performance ratio ½ (1+sqrt(2)) of this algorithm (WSPT rule) by Kawaguchi and Kyan from 1986.

The central question underlying the talk is as follows: How does the complexity of linear integer optimization problems translate into functions depending on the number of variables, the number of rows, the infinity norm of the constraint matrix or the maximal absolute value of the square submatrices of the constraint matrix? In this context, the following functions are of major interest: The running time function, the proximity function, the row-number function, the sparsity function and the integer Caratheodory number.

Chvatal-Gomory (CG) cuts and the Bienstock-Zuckerberg hierarchy capture useful linear programs that the standard bounded degree Lasserre/Sum-of-Squares (SOS) hierarchy fails to capture. In this paper we present a novel polynomial time SOS hierarchy for 0/1 problems with a custom subspace of high degree polynomials (not the standard subspace of low-degree polynomials). We show that the new SOS hierarchy recovers the Bienstock-Zuckerberg hierarchy. Our result implies a linear program that reproduces the Bienstock-Zuckerberg hierarchy as a polynomial sized, efficiently constructible extended formulation that satisfies all constant pitch inequalities. The construction is also very simple, and it is fully defined by giving the supporting polynomials (one paragraph). Moreover, for a class of polytopes (e.g. set covering and packing problems) it optimizes, up to an arbitrarily small error, over the polytope resulting from any constant rounds of CG cuts. Arguably, this is the first example where different basis functions can be useful in asymmetric situations to obtain a hierarchy of relaxations.

It is well known that SDP problems are solvable in polynomial time by interior point methods (IPMs). However, if the number of constraints m in an SDP is of order O(n^2), when the unknown positive semidefinite matrix is n × n, interior point methods become impractical both in terms of the time and the amount of memory required at each iteration. As a matter of fact, in order to compute the search direction, IPMs need to form the m × m positive definite Schur complement matrix M and find its Cholesky factorization. On the other hand, first-order methods typically require much less computation effort per iteration, as they do not form or factorize these large dense matrices.Furthermore, some first-order methods are able to take advantage of problem structure such as sparsity. Hence, they are often more suitable, and sometimes the only practical choice for solving large scale SDPs. Most existing first-order methods for SDP are based on the augmented Lagrangian method. Alternating direction augmented Lagrangian (ADAL) methods usually perform a projection onto the cone of semidefinite matrices at each iteration. With the aim of improving the convergence rate of ADAL methods, we propose to update the dual variables before the projection step. Numerical results are shown, giving some insights on the benefits of the approach.

The idea of min-max-min robustness is to calculate k different solutions of a linear combinatorial problem such that these solutions are worst-case optimal if we consider the respectively best of the calculated solutions in each scenario. This idea can be modeled as a min-max-min problem and extends the classical min-max approach. We adapt the idea of min-max-min robustness to quadratic combinatorial problems and apply it to single-allocation hub location problems with uncertain weights.

We consider optimizing the scheduling of the scientific program of a large conference such as the International Symposium in Mathematical Programming (ISMP). In this example, there are about 520 sessions (with 3 or 4 talks in each). In each time slot 40 sessions take place in parallel. The first issue is to avoid to schedule in parallel sessions that are destined to a same public. To measure the latter, we record referees’ and attendees’ input to define both hard and soft conflict constraints between sessions. The second measure of the quality of the program is the extend to which the scientific interest is evenly spread over the week: the goal is to avoid having all the high-profile talks into some time slots and none in other time slots. This goal is modeled as a min max of the interest measure for a time slot. Both goals are driving the optimization in the same direction of a well balance program. We propose a MIP model whose solution scales up to our instance. We hope to take advantage of the Aussois workshop attendance to get feedback on our model and approach. Option 4) only want to give a 15-minute talk

There has been a surge of research activity in machine learning in the past decade. Consequently, there has been a growing interest in mathematically rigorous analysis to strengthen the foundations of this area. A surprisingly large number of applications seem to report empirically observed phenomena that suggest that there are some universal mathematical theorems underpinning the recent successes reported. However, for many (most?) of the interesting phenomena, such theoretical foundations have been elusive. Moreover, wherever such results have been obtained, it has been through the lens of continuous (convex and non-convex) optimization. We will try to make the case that techniques from discrete geometry and optimization are ideally placed to tackle some of the unsolved puzzles in this area, and perhaps provide competing methods even in some applications that have traditionally relied on continuous optimization techniques. The emphasis of the talk will be on open problems in machine learning that can be framed in the language of discrete geometry and optimization. The talk will be based on recent work with Raman Arora, Poorya Mianjy and Anirbit Mukherjee.

The goal of a kidney exchange program (KEP) is to maximize number of transplants within a pool of incompatible patient-donor pairs by exchanging donors. A KEP can be modeled as a maximum matching problem in a graph. A KEP between incompatible patient-donor pools of several hospitals, regions or countries has the potential to increase the number of transplants. These entities aim is to maximize the transplant benefit for their patients, which can lead to strategic behaviors. We modeled this situation as a non-cooperative game and characterized the game solutions (equilibria) when the entities objective function is the number of their patients receiving a kidney. Recently, we started to analyze the impact in the game solutions when transplant information quality is introduced. The motivation comes from machine learning models that can provide accurate ways for predicting graft survival times. We will present our preliminary results in this setting. 4) only want to give a 15-minute talk;

We consider solution graphs of combinatorial problems that arise from certain natural adjacency relations on the solution sets. Such graphs are typically too large to be stored explicitly. After a brief overview of what is known about the complexity of the st-reachability problem on such graphs, our focus will be solution graphs that can be characterized in terms of common independent sets of matroids. We will showcase the following recent dichotomy result: For common independent sets of at most two matroids, the corresponding st-reachability problem can be solved in polynomial time, while for three or more matroids the problem is PSPACE-complete.

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain a Randomized NC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope. This is joint work with Jakub Tarnawski.

Various procedures have been developed to strengthen convex relaxations of sets of integer points. On the one hand, there exist several general-purpose methods that strengthen relaxations without specific knowledge of the set S of feasible integer points, such as popular linear programming or semi-definite programming hierarchies. On the other hand, many methods have been designed for obtaining strengthened relaxations for very specific sets S that arise in combinatorial optimization. We propose a new efficient method that interpolates between these two approaches. Our procedure strengthens any convex set containing a subset S of 0/1-points by exploiting certain additional information about S. Namely, the required extra information will be in the form of a Boolean formula defining the target set S. The aim of this work is to analyze various aspects regarding the strength of our procedure. As one result, interpreting an iterated application of our procedure as a hierarchy, our findings simplify, improve, and extend previous results by Bienstock and Zuckerberg on covering problems. This is joint work with Samuel Fiorini and Tony Huynh.

In this work, we present a method to compute the distance between a pair of two-dimensional histograms by solving an uncapacitated minimum cost flow on a reduced network. Recent works have shown the benefits of measuring Wasserstein distances of order one between histograms by solving a classical transportation problem on (very large) complete bipartite graphs. These bipartite graphs have a partition associated to each of the two histograms: the underlying intuition is to “transport” at minimum cost the overall weight of the first histogram into the second one. The height of each bin of the first histogram gives an amount of supply of a node of the first partition, while the height of each bin of the second histogram represents an amount of demand. Between each pair of nodes is given a cost equal to the distance between the corresponding pair of bins. Unfortunately, the size of the bipartite graphs that arise in real applications is too large to be efficiently solved by state-of-the-art algorithms. Precisely, for N supply bins and N demand bins, the complete bipartite graph has N^2 edges. The main contribution of our work is to approximate the original transportation problem by an uncapacitated min cost flow problem on a reduced network of size O(N), instead of the original O(N^2). More precisely, when the distance among the bins is measured with the 1-norm or the infinity-norm, our approach provides an optimal solution. When the distance between bins is measured with the 2-norm: (i) we derive a quantitative estimate on the error between optimal and approximate solution; (ii) given the error, we construct a reduced network of size O(N); (iii) if we search for an exact solution, we provide a reduced network with around half the size of the complete bipartite graph. We numerically show the benefits of our approach by computing the distances on a set of grey scale images used as benchmarks in the literature. On smaller instances, we compare the results obtained by our network flow approach with the exact solutions obtained by using a commercial LP solver on the original transportation problems. Finally, we show how our approach scales with the size of the images. [prefer a 15-minute talk over a 30-minute talk, but willing to do either;]

It is a well-known fact that if in the primal Lovász theta number formulation the cone of positive semidefinite matrices is replaced by the cone of completely-positive matrices, then one obtains exactly the independence number. In this talk I will show how this can be extended to infinite graphs over compact spaces and discuss how this result can be used in practice to improve some parameters in extremal geometry. (Joint work with Evan DeCorte and Frank Vallentin.)

Compacting orthogonal drawings is a challenging task. Usually algorithms try to compute drawings with small area or total edge length while preserving the underlying orthogonal shape. We suggest a moderate relaxation of the orthogonal compaction problem, namely the one-dimensional monotone flexible edge compaction problem with fixed vertex star geometry. We further show that this problem can be solved in polynomial time using a network flow model. An experimental evaluation shows that by allowing additional bends we were able to reduce the total edge length and the drawing area. 3) prefer a 15-minute talk over a 30-minute talk, but willing to do either;

The current best exact algorithms for the Capacitated Arc Routing Problem are based on the combination of cut and column generation. This work presents a deep theoretical investigation of the formulations behind those algorithms, classifying them and pointing similarities and differences, advantages and disadvantages. In particular, we discuss which families of cuts and branching strategies are suitable for each alternative and their pricing complexities. That analysis is used for justifying key decisions on constructing a powerful new branch-cut-and-price algorithm. The computational experiments show that the resulting algorithm is indeed very effective and can solve almost all open instances from the classical benchmark sets. 2) prefer a 30-minute talk over a 15-minute talk, but willing to do either;

A polyhedron is box-integer if its intersection with any integer box is an integer polyhedron. We introduce principally box-integer polyhedra: they are the polyhedra whose dilatations are box-integer as soon as they are integer. We will present several characterizations of principally box-integer polyhedra, which involve matrices and strong integrality properties of linear sytems. Eventually, we will discuss connexions with combinatorial optimization problems, and more precisely about box-total dual integrality. This is a joint work with Patrick Chervet (Lycée Olympe de Gouges) and Louis-Hadrien Robert (Universität Hamburg).

We study the two player zero-sum Stackelberg game in which the leader removes at most k nodes from a network, in order to minimize the size of the maximum clique determined by the follower. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases, or surveillance of communication networks. We design an exact solution framework based on a Bilevel Integer Linear Programming model. Thanks to the study of the polytope of the corresponding single-level reformulation, we derive a branch-and-cut algorithm and enhance it by tight combinatorial lower and upper bounds, which also allow for a drastic reduction of the size of the input network. Our model is based on an exponential family of Clique Interdiction Cuts whose separation requires solving the maximum clique problem. We derive an effective separation procedure based on a newly developed algorithm that is tailored for finding maximum cliques in interdicted networks. We assess the applicability and the limits of our solution framework on publicly available instances, including large-scale social networks with up to hundreds thousands nodes and three million edges. Most of these instances are solved to provable optimality within short computing times. Our implementation (which is also publicly available) allows to analyze the resilience of (social) networks with respect to node-interdiction attacks, i.e., the evolution of the size of the maximum clique in function of the interdiction budget k. 1) have no preference and can accommodate both formats;

We want to find a dynamic equilibrium in a network with multiple sources and multiple sinks by using flows over time. It is possible to construct these Nash flows by computing, so-called, thin flows with resetting, which describe the network status for an interval of flow particles via a static flow. Finally, we show how to satisfy given demand rates on each sink by using a super sink construction.

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics. Specifically, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. For those instances, we then solve Local-Connectivity ATSP, a problem known to be equivalent (in terms of constant-factor approximation) to the asymmetric traveling salesman problem. This is joint work with Ola Svensson and László Végh.

Within state-of-the-art solvers such as IBM-CPLEX the ability to solve both convex and nonconvex Mixed-Integer Quadratic Programming (MIQP) problems to proven optimality goes back few years, yet presents unclear aspects. We are interested in understanding whether for solving an MIQP it is favorable to linearize its quadratic part or not. Our approach exploits machine learning techniques to learn a classifier that predicts, for a given instance, the most suitable resolution method within CPLEX's framework. We aim as well at gaining methodological insights about the instances' features leading this discrimination. We examine a new dataset and discuss different scenarios to integrate learning and optimization. By defining novel measures, we interpret and evaluate learning results from the optimization point of view.

In previous work, we analytically developed the idea of using volume as a measure for comparing relaxations in the context of spatial branch-and-bound. Specifically, for trilinear monomials, we analytically compared the three possible `double-McCormick relaxations' with the tight convex-hull relaxation. Here, again using volume as a measure, we establish simple rules for determining the optimal branching variable and optimal branching point for the convex-hull relaxation of trilinear monomials. Additionally, we compare our results with current software practice.

A standard way to handle symmetries in binary programs is to add inequalities that cut off solutions that are lexicographically not maximal in their orbits w.r.t. the corresponding symmetry group. To allow for a general analysis of such inequalities, we consider symretopes, which are the convex hull of all binary vectors that are lexicographically maximal in their orbits. Thus, adding inequalities of an IP formulation for symretopes to a binary program removes all the symmetry of the program. Related knapsack polytopes are so-called symresacks that are based on one permutation. In this talk, we investigate these two kinds of polytopes. If the problem contains certain set packing, partitioning, and covering constraints, we show that strong symmetry handling inequalities for symresacks can be derived. In particular, a complete description can be obtained for special permutations. For so-called orbitopes, i.e., special symretopes in which symmetries act by permuting the columns of a 0/1-matrix, further polyhedral results can be proven. We then show how these results behave in practice. The corresponding extensive numerical results investigate the effectiveness of the combination of these approaches. I prefer option 5) only want to give a 30-minute talk.

The assortment of products carried by a store has a crucial impact on its success. However, finding the right mix of products to attract a large portion of the customers is a challenging task. Several mathematical models have been proposed to optimize assortments. In particular, rank-based choice models have been acknowledged for representing well high-dimensional product substitution effects, and therefore reflect customer preferences in a reasonably realistic manner. In this work, we extend the concept of (strictly) fully-ranked choice models to models with partial ranking that additionally allow for indifference among subsets of products, i.e., on which the customer does not have a strict preference. We show that partially-ranked choice models are theoretically equivalent to fully-ranked choice models, but a partially-ranked preference sequence would require a factorial number of fully-ranked sequences to represent the same buying behavior. We then show how partially-ranked choice models can be learned efficiently from historical transaction and assortment data. The embedded column generation procedure involves subproblems that can be efficiently solved by using a growing decision tree that represents partially-ranked preferences, enabling us to learn preferences and optimize assortments for thousands of products. Computational experiments on artificially generated data and case studies on real industrial retail data suggest a significant potential to increase profits when performing data-driven assortment optimization and provide useful insights on customer segmentations to the decision makers, in our real case, the store managers. When comparing to existing algorithms, our method increases by one order of magnitude the scale of problems that can be learned by non-parametric choice models. (joint work with Sanjay Jena and Hugo Palmer)