Seminars

It is a notorious open question whether integer programs (IPs), with an integer constraint matrix M whose subdeterminants are all bounded by a constant in absolute value, can be solved in polynomial time. We give an overview on recent progress towards this question and the rich combinatorial structures hidden within. Further, we show how to solve such IPs if the constraint matrix fulfills certain further structural conditions. This talk is based on the following papers: Aprile, M., Fiorini, S., Joret, G., Kober, S., Seweryn, M. T., Weltge, S., & Yuditsky, Y. Integer programs with nearly totally unimodular matrices: the cographic case. [SODA 2025] Fiorini, S., Kober, S., Seweryn, M. T., Shantanam, A., & Yuditsky, Y. Face covers and rooted minors in bounded genus graphs. [preprint 2025] Kober, S. Totally ?-Modular IPs with Two Non-zeros in Most Rows. [IPCO 2025]

Modern networked systems are no longer confined to centralized infrastructures, but span a continuum from cloud data centers to edge nodes and individual end devices. In this setting, optimally placing and orchestrating virtualized services becomes a critical and complex optimization problem. In this talk, I present a set of recent contributions addressing this class of problems, characterized by: (a) hard decisions on service placement and orchestration of modular applications, (b) scarce and heterogeneous resources, and (c) multi-layer network graphs. I highlight key challenges arising in this context, formulate the underlying combinatorial optimization problems, present solution approaches based on mixed integer programming and decomposition methods, and outline directions for future research.

The k-Edge-Connected Subgraph problem and the k-Connectivity Augmentation problem are among the most basic Network Design problems and, consequently, have been heavily studied. Due to their approximation hardness, the gold standard in terms of approximation guarantee are strong constant factors. Interestingly, this approximation hardness does not carry over to planar graphs. In particular, the 2-Edge-Connected Subgraph problem admits a PTAS on planar graphs. However, the used techniques are very different from the celebrated Baker’s framework, which is a standard way to design PTASs for planar graphs. The main obstacle of using Baker’s technique in its classical form is that it requires a certain locality of the problem. However, k-edge/vertex-connectivity are global properties. We present a novel, and arguably clean, way to extend Baker’s framework to deal with larger connectivity requirements. Based on this, we obtain a PTAS for the k-Edge-Connected Subgraph problem and its vertex analog, even with costs, as long as the max-to-min cost ratio is bounded by a constant. Moreover, together with further insights, we obtain a PTAS for the k-Connectivity Augmentation problem in the same cost setting. We complement this with an NP-hardness result for planar augmentation, showing that all our results are essentially tight. This is joint work with Vera Traub and Rico Zenklusen.

The Quantum Approximate Optimization Algorithm (QAOA) has recently been proposed as a heuristic framework for solving combinatorial optimization problems through a hybrid classical–quantum optimization procedure. The algorithm alternates parameterized quantum transformations with a classical optimization step that adjusts the circuit parameters in order to increase the probability of sampling high-quality solutions. A key factor influencing the performance of QAOA is the choice of the initial state. In standard implementations, the algorithm starts from a uniform superposition over all candidate solutions, which does not exploit structural information about the original optimization problem and may lead to inefficient parameter optimization and lower-quality solutions. In this talk, we propose a warm-start strategy based on continuous optimization, using the Difference-of-Convex Algorithm (DCA). The idea is to exploit a continuous relaxation of the original optimization problem in order to construct an informed initialization that biases the search toward promising regions of the solution space. We illustrate the approach on instances of the Max-Cut problem and show that this strategy can significantly improve the approximation ratios obtained by QAOA. This is a joint work with HA Huy Phuc Nguyen et TA Anh Son.

Positive spanning sets (PSSs), that span a given space through nonnegative linear combinations, have been successfully employed to design and analyze derivative-free optimization algorithms. Although linear algebra is a natural framework for studying PSSs, polyhedral geometry can provide additional insights on the structure of PSSs. In this talk, I will first introduce the concept of positive spanning sets, together with its use in derivative-free optimization. I will then focus on the specific case of polyhedral constrained problems, and explain how to generate positive spanning sets that conform to the geometry of those constraints. Finally, I will turn to a perhaps unexpected construction of PSSs of smallest cardinality through polytopes, and discuss several associated open questions. This talk is based on joint works with Denis Cornaz, Sébastien Kerleau and Lindon Roberts.

Given an hypergraph on a set of n ordered vertices, we define an independent set X to be feasible, if X is a possible outcome for a player in a sequential picking game, against a greedy adversary, where no hyperedge can be contained in the union of both outcomes. We prove that testing feasibility is NP-complete, even if the hypergraph is a graph, but it becomes polynomial (in n) for matroid hypergraphs, that is, when the hyperedges are the circuits of some matroid (in which independence can be tested with an oracle). We prove also that optimizing a linear function over feasible sets is NP-hard for graphs and matroid hypergraphs, even for graphic matroids, but it becomes polynomial for laminar matroids.

Betweenness centrality (BC), introduced in 1977, is a fundamental measure of node importance in networks, widely used in fields ranging from sociology to computer science. BC quantifies the extent to which a node lies on shortest paths between pairs of nodes, making its computation closely tied to the enumeration of these paths. In this work, we investigate the computational complexity of determining BC for all nodes in a graph, highlighting the challenges associated with exhaustive shortest-path counting. We further examine extensions of BC to dynamic graphs, where edges carry temporal information and optimal paths are determined not only by topology but also by timing constraints (i.e., fastest paths). We explore the hardness of computing BC under such dynamic conditions and discuss how temporal dependencies complicate classical shortest-path approaches. Our study aims to unify understanding of BC computation across static and temporal graph models and to identify open problems in efficiently counting relevant paths in these settings.

This presentation addresses linear Chance-Constrained Stochastic Problems (CCSPs) with finite support. We begin by motivating the study of CCSPs through illustrative examples and providing intuition regarding the concept of feasibility in this context. Subsequently, we discuss the computational challenges inherent to these problems, specifically the nonconvex structure of the feasible region and the limitations of the standard big-M reformulation. These challenges necessitate the use of branch-and-cut approaches. To this end, we review existing families of valid inequalities, such as quantile inequalities and mixing inequalities. This background sets the stage for the primary contribution of this work: a new class of valid inequalities termed multi-disjunctive inequalities. We construct these inequalities by exploiting a disjunctive property inherent to the mathematical formulation of CCSPs. Theoretical analysis reveals that the closure of these multi-disjunctive inequalities constitutes a proper subset of the closure generated by previously proposed families. We perform numerical experiments within a pure cutting-plane framework to compare the closures obtained by enumerating all violated valid inequalities. The results demonstrate that multi-disjunctive inequalities significantly strengthen the continuous relaxation of the considered CCSPs compared to existing quantile and mixing-set inequalities. Furthermore, we evaluate the performance of these inequalities embedded within a branch-and-cut framework. Our results indicate that the proposed approach significantly outperforms existing methods on both standard literature instances and newly generated instances designed to be computationally challenging.

I will go over some recent results on Frank-Wolfe methods, presenting the core aspects of the algorithms and highlight properties of the algorithms that make them relevant for convex quadratic optimization, despite the first-order access to the objective. In particular, we will go over the active set identification property some Frank-Wolfe variants enjoy and a use of linear system or linear optimization solvers to accelerate convergence and reach finite-time guarantees. I will then present one application to sparse flow decomposition for RNA-seq data analysis.

In this talk, we study problems that involve partitioning the vertices of an undirected graph into a given number of pairwise disjoint sets such that each set induces a connected subgraph. We first propose valid inequalities, which extend and generalize the ones in the literature, and report on computational experiments demonstrating their use (joint work with P. Moura and R. Leus). Then, we extend this problem to also compute a spanning tree for each set of the partition such that the weight of the heaviest tree is minimized. We investigate the complexity of this problem and present formulations and solution methods, which we compare with an experimental study (joint work with M. Davari and P. Moura). Finally, we consider a practical problem encountered in power system restoration, which involves partitioning a power network into connected subnetworks, one for each black start generator, such that the restoration time is minimized. We propose a solution method that uses a new formulation and properties of optimal solutions and report computational results (joint work with H. Çal?k and D. Van Hertem).

The aircraft routing problem is one of the most relevant problems of operations research applied to aircraft management. It involves assigning flights to aircraft while ensuring regular visits to maintenance bases. This work examines two aspects of the problem. First, we explore the relationship between periodic instances, where flights are the same every day, and periodic solutions. The literature has implicitly assumed without discussion that instances necessitate periodic solutions, and even periodic solutions in a stronger form, where every two airplanes perform either the exact same cyclic sequence of flights, or completely disjoint cyclic sequences. However, enforcing such periodicity may eliminate feasible solutions. We prove that, when regular maintenance is required at most every four days, there always exist periodic solutions of this form. Second, we consider the computational hardness of the problem. Even if many papers in this area refer to the NP-hardness of the aircraft routing problem, such a result is only available in the literature for periodic instances. We establish its NP-hardness for a non-periodic version. Polynomiality of a special but natural case is also established. Joint work with Axel Parmentier and Nour ElHouda Tellache

We propose a new polyhedral approach for combinatorial optimization problems. Rather than working on the convex hull of the feasible set, we focus on a polytope that excludes the uninteresting feasible solutions dominated in a local neighborhood. In this work, the idea is applied to the linear Knapsack problem and the quadratic MaxCut problem with a theoretical study that demonstrates dominance inequalities and facets. The outstanding effectiveness of the proposed inequalities is numerically shown on the MaxCut instances from the BiqBin library.

In this work we study the problem of scheduling quantum applications (i.e. quantum circuits) on shared quantum chips. Quantum computers are constrained by limited qubit connectivity and noisy operations, which makes the scheduling of quantum circuits on physical hardware a critical step for efficient execution. In this work, we model the scheduling problem as a tiling problem, under a set of assumptions that capture the main architectural restrictions of quantum chips. To address this problem, we propose an integer linear programming (ILP) formulation and present preliminary computational results.

Classification trees are models that provide highly interpretable classifiers but generally do not perform as well as neural networks. To obtain classifiers that are both interpretable and performant, we consider the problem of computing an optimal classification tree for a given data set. To address this problem, we first define new mathematical formulations in the form of mixed integer linear programs (MILP) and demonstrate that they are stronger and more efficient than state-of-the-art MILPs. To handle larger datasets, we then define iterative algorithms based on a data partition that is refined throughout the iterations.

We present some old and new results on arbitrary families of parametric polyhedra. First, if the constraint matrix is fixed, in the literature there are structural results for the integer hull and the finiteness of cutting plane closures for varying r.h.s. For instance, recently, Becu et al. proved in "Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data" that the GMI closure of this family is finitely generated, in the sense that there exists a finite list of aggregation weights defining the GMI cuts that give the GMI closure for any polyhedra in the family. We extend this result for other cutting plane closures. Second, if the family of parametric polyhedra is arbitrary but all polyhedra in the family have the same integer hull, they define the same MIP, and we can leverage this information to understand and solve MIPs better. These families have been used to understand theoretical properties of the rank of cutting planes and to obtain better formulations. We present an application of these same-integer-hull families to formulations for the Asymmetric Traveling Salesman Problem.

Capacitated fixed-charge network design problems and generalizations, such as service network design problems, have a wide range of applications but are known to be very difficult to solve. Many exact and heuristic algorithms to solve these problems rely on column-and-row generation (CRG), which frequently suffer from primal degeneracy. We present a set of dual inequalities, equivalent to a simple primal relaxation, that speed up CRG algorithms for generalized capacitated fixed charge network design problems. We investigate the impact of the dual inequalities theoretically as well as experimentally. For practical applications, the presented technique is simple to implement, has no additional computational cost and can accelerate CRG by orders of magnitude, depending on the problem size and structure.

This work investigates a decision support system for planning a consolidation-based distribution system in a city where inbound freight arrives in containers at an intermodal terminal. Since this facility lacks storage and transdock capabilities, containers must be transferred to satellite facilities to be unpacked and reloaded onto smaller vehicles. The problem is approached from the perspective of an urban mobility manager, who must select the satellite facilities and vehicles, define their routes, and determine the commodity flows to final destinations, while optimizing transportation resources. The problem is formulated as a Mixed-Integer Linear Programming model. To address realistically sized instances, a metaheuristic based on two Adaptive Large Neighborhood Searches (ALNSs) is proposed: the outer ALNS selects satellites and vehicles, and assigns containers to satellites; the inner ALNS handles routing and allocation decisions on the second echelon. These procedures are run iteratively. The metaheuristic is used to conduct an extensive experimental campaign using data from the city of Cagliari (Italy) to evaluate the distribution system.

Quantum computation is a new paradigm that is increasingly being exploited today for designing methods to solve optimization problems. Although its application to numerical instances is limited, among other reasons due to the lack of quantum RAM, theoretical advantages are emerging compared to classical approaches for several classes of problems. In this talk, we provide insights into what makes quantum algorithms powerful for optimization and illustrate it with a new bounded-error quantum-classical algorithm. Specifically, this algorithm combines the generalization of Grover Search with dynamic programming to polynomially reduce the worst-case time complexity of NP-hard minimization problems satisfying certain properties. We exemplify it on several scheduling problems.

Temporal graphs model interactions evolving over time, with different representations depending on how time is taken into account: several models coexist, notably the point model and the interval model. Although these two models are often considered equivalent in discrete time, switching from one to the other can have major implications in terms of computational complexity. In this talk, I'll describe how we proved fundamental complexity discrepancies between these two models for classical problems such as computing the fastest time path (minimizing the total travel time) and the shortest time path (minimizing the number of edges). I will also explain how, while the computation of the fastest time path can be solved in quasi-linear time in the point model, it requires quadratic time in the interval model under standard complexity assumptions. However, a quasi-linear time algorithm exists in the interval model with zero path times. Interestingly, we found no such discrepancy for the global temporal connectivity problem, for which we proved a valid quadratic lower bound in both models, corresponding to the known upper bounds. These results shed new light on the computational limits of temporal graphs and the impact of the choice of time representation. This is joint work with Filippo Brunelli, Feodor F. Dragan, Guillaume Ducoffe, Michel Habib, Allen Ibiapina and Laurent Viennot.

Bi-objective combinatorial optimization (BOCO) arises in many real-world scenarios where a decision-maker (DM) must simultaneously optimize two conflicting objectives. BOCO poses significant challenges due to the discrete nature of the decision space and the inherent trade-offs between the objectives. Existing methods for BOCO can be broadly categorized into a posteriori methods, which explore the Pareto front comprehensively, and a priori methods, for which DM's preferences are defined beforehand and incorporated in the optimization phase. While a posteriori methods offer a variety of trade-off solutions, a priori methods are often preferred in practice due to their computational efficiency and compatibility with the decision-making process. Cooperative game theory and multi-objective optimization intersect in finding acceptable solutions amidst conflicting goals. The concepts in bargaining games are well-suited for solving multi-objective optimization problems because both involve resolving trade-offs among competing interests (players or objectives). In convex multi-player bargaining problems, the Nash Bargaining Solution (NBS), a fundamental concept introduced by Nash, offers a powerful framework for balancing multiple objectives by ensuring fairness and mutual benefit for the parties involved. Although the concept has been generalized for non-convex bargaining problems, there has been limited application of the NBS in multi-objective optimization, particularly in BOCO. Motivated by this gap, in this research, we aim to consider the NBS as a criterion for selecting preferred solutions within the Pareto front of BOCO. In multi-player bargaining problems, the NBS maximizes the product of the players' gains over their disagreement outcomes. In the BOCO context, the NBS maximizes the product of the objectives relative to a reference point, which can be chosen as the Nadir point. Notice that the Nadir point is obtained by computing each objective with the optimal decision vector of the other objective. Along with Utopia point, which is the (unfeasible) point where both objectives take maximum values, they are crucial for understanding the trade-offs between two objectives and guiding the decision-making process. For our purpose, we consider a more general version of the NBS in BOCO by incorporating the DM's point of view. Specifically, we introduce the generalized NBS (rho-NBS) where rho > 0 is a parameter reflecting the DM's priority to the first objective compared to the second one. Thus, the rho-NBS maximizes the product of the power rho of the first objective and the second objective relative to the Nadir point. It is important to note that the problem of maximizing the product of two functions, even when they are linear with binary variables, is NP-hard. In this research, we focus on identifying the rho-NBS within the set of supported efficient solutions instead of the whole Pareto front. These supported efficient solutions are located on the convex hull of the Pareto front and offer valuable insights into its structure in BOCO. We first introduce the rho-NBS concept for BOCO. Then, we develop a binary search algorithm to identify the rho-NBS within the set of supported efficient solutions. To the best of our knowledge, this is the first application of the Nash bargaining game to multi-objective combinatorial optimization, where an efficient algorithm has been developed. Finally, we apply our theory and algorithm to the Bi-Objective Assignment Problem (BOAP), a specific example of BOCO.

Real-world industrial applications frequently confront the task of decision-making under uncertainty. The classical paradigm for these complex problems is to use both machine learning (ML) and combinatorial optimization (CO) in a sequential and independent manner. ML learns uncertain quantities based on historical data, which are then used used as an input for a specific CO problem. Decision-focused learning is a recent paradigm, which directly trains the ML model to make predictions that lead to good decisions. This is achieved by integrating a CO layer in a ML pipeline, which raises several theoretical and practical challenges. In this talk, we aim at providing a comprehensive introduction to decision-focused learning. We will first introduce the main challenges raised by hybrid ML/CO pipelines, the theory of Fenchel-Young losses for surrogate differentiation, and the main applications of decision-focused learning. As a second objective, we will present our ongoing works that aim at developing efficient algorithms based on the Bregman geometry to address the minimization of the empirical regret in complex stochastic optimization problems.

We present an algorithm for triobjective nonlinear integer programs that combines the eps-constrained method with available oracles for biobjective integer programs. We prove that our method is able to detect the nondominated set within a finite number of iterations. Specific strategies to avoid the detection of weakly nondominated points are devised. The method is then used to determine the nondominated solutions of triobjective 0-1 models, built to design nutritionally adequate and healthy diet plans, minimizing their environmental impact. The diet plans refer to menus for school cafeterias and we consider the carbon, water and nitrogen footprints as conflicting objectives to be minimized. Energy and nutrient contents are constrained in suitable ranges suggested by the dietary recommendation of health authorities. Results obtained on two models and on real world data are reported and discussed. Coauthors: Luca Benvenuti, Alberto De Santis, Daniele Patria

In traditional stochastic programming, decisions are made based on known probabilities or distributions of uncertain parameters. However, in real-world scenarios, decision-makers often have opportunities to gather additional information about these uncertainties through a process known as probing. Probing allows for observation of certain random variables, which can provide valuable insights into the behavior of related uncertainties. However, probing is not free—it involves a cost that must be taken into account in the decision-making process. This cost could represent financial expenditure, time, or resource allocation necessary to gather data or perform exploratory actions. Thus, probing involves taking actions or gathering data to learn more about the uncertain variables before making the final decision. In two-stage stochastic programs, this can mean performing certain preliminary actions (probing decisions) that help to reveal more information about future states (first and second-stage decisions). We investigate a probing-enhanced stochastic programming approach for the two-stage stochastic multi-item capacitated lot-sizing problem, which is a classic inventory management problem where decisions are made in two stages to minimize costs while considering uncertain future demand. Two-stage problems, except for very simple models, are generally intractable to solve exactly. Even with complete knowledge of the demand distribution, explicitly integrating the second-stage costs is computationally prohibitive. A common approach to address this complexity is the Sample Average Approximation (SAA) method, which approximates the expectation by sampling from the original distribution to create a finite set of scenarios. Then we adopt a non-anticipative formulation that enables us to ensure that decisions are consistent with the information available at the time of decision-making. The critical aspect of this approach is that the enforcement of non-anticipativity conditions depends on the decisions themselves. Thus, the resulting model includes a vast number of conditional non-anticipativity constraints, proportional to the square of the number of scenarios. This leads to a mixed-integer linear programming (MILP) formulation characterized by a large number of big-M constraints, which can be challenging to solve efficiently. We propose a decomposition approach to solve the resulting non-anticipative formulation, exploiting the structure of the problem by breaking it into smaller, more manageable sub-problems that can be solved efficiently, providing a more practical and scalable solution approach. Preliminary computational results demonstrate that the proposed decomposition algorithm significantly outperforms the other approaches in terms of both solution quality and computation time, achieving improvements by several orders of magnitude. Joint work with Céline Gicquel, Safia Kedad-Sidhoum and Bernardo Pagnoncelli.

Due to the complexity of real-world planning processes addressed by major transportation companies, decisions are often made considering subsequent problems at the strategic, tactical, and operational planning phases. However, these problems still prove to be individually very challenging. This talk will present two examples of tactical transportation problems motivated by industrial applications: the Train Timetabling Problem (TTP) and the Service Network Scheduling Problem (SNSP). The TTP aims at scheduling a set of trains, months to years before actual operations, at every station of their path through a given railway network while respecting safety headways. The SNSP determines the number of vehicles and their departure times on each arc of a middle-mile network while minimizing the sum of vehicle and late commodity delivery costs. For these two problems, the consideration of capacity and uncertainty in travel times are discussed. We present models and solution approaches including MILP formulations, Tabu search, Constraint Programming techniques, and a Progressive Hedging metaheuristic.

Last-mile delivery is regarded as an essential, yet challenging problem in city logistics. One of the most common initiatives, implemented to streamline and support last-mile activities, are satellite depots. These intermediate logistics facilities are used by companies in urban areas to decouple last-mile activities from the rest of the distribution chain. Establishing a business model that considers different stakeholders' interests and balances the economic and operational dimensions, is still a challenge. In this seminar, we will introduce a novel problem that broadly covers such setting, where the delivery to customers is managed through satellite depots and the interplay and the hierarchical relation between the problem agents are modeled in a bi-level framework. Two mathematical models and an exact solution approach, properly customized for our problem, will be presented, and extensive computational experiments on benchmark instances and a real case study discussed. Finally, we will shed light on future research directions on how the proposed approach can be extended for other relevant problem classes.

In a previous work, we introduced “alphabet reduction pairs of arrays” (ARPAs), a family of combinatorial designs, to transport differential approximation results for k-CSPs over an alphabet of size p ? k to k-CSPs over an alphabet ?q of size q > p. ARPAs on ?q consist of two arrays of q columns satisfying the following conditions: the first array must contain a certain word composed of all symbols of ?q; no row of the second array can involve more than p different symbols of ?q; the two arrays must coincide on any subset of k columns. In the context of approximation, the target word in the first array represents an optimal solution that the second array allows us to associate with assignments involving at most p different values. Thus, we want to maximize the frequency of this particular word, and refer to ARPAs that achieve this as “optimal”. To study optimal ARPAs, we consider a seemingly simpler family of combinatorial designs, called “Cover Pairs of Arrays” (CPAs), which can be viewed as a Boolean interpretation of ARPAs. The two arrays of a CPA still share the same number q of columns, and must match on any k of them; but they take Boolean entries, the second array is restricted to words with at most p ones, and we want to maximize the frequency of the word of q ones in the first array. Using combinatorics and linear programming, we establish the equivalence between ARPAs and CPAs in terms of maximizing the frequency of the target word. In addition, we provide optimal constructions for the case where k ? {1, 2, p}. These results establish the optimality of ARPAs given in previous work for the case where p = k, and highlight the relevance of CPAs for the approximability of k CSPs. They also raise new questions about ARPAs, which we will discuss along with other questions about related combinatorial designs that allow refining our knowledge of how well k-CSP-q reduces to k-CSP-p. Joint work with Jean-François Culus.

When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships (also known as non-interleaving picking sequences): given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). With these rules, agents who come earlier in the sequence have a larger choice of items. However, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. In this presentation, we use a model parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that an optimal sequence can be computed exactly in polynomial time or approximated by resorting to sampling. Joint work with Sylvain Bouveret, Jérôme Lang, and Guillaume Méroué.

Two-stage stochastic programs (TSSP ) are a classic model where a decision must be made before the realization of a random event, allowing recourse actions to be performed after observing the random values. For example, many classic optimization problems, like network flows or facility location problems, became TSSP if we consider, for example, a random demand. Benders decomposition is one of the most applied methods to solve TSSP with a large number of scenarios. The main idea behind the Benders decomposition is to solve a large problem by replacing the values of the second-stage subproblems with individual variables, and progressively forcing those variables to reach the optimal value of the subproblems, dynamically inserting additional valid constraints, known as Benders cuts. Most traditional implementations add a cut for each scenario (multi-cut) or a single-cut that includes all scenarios. In this paper we present a novel Benders adaptive-cuts method, where the Benders cuts are aggregated according to a partition of the scenarios, which is dynamically refined using the LP-dual information of the subproblems. This scenario aggregation/disaggregation is based on the Generalized Adaptive Partitioning Method (GAPM). We formalize this hybridization of Benders decomposition and the GAPM, by providing sufficient conditions under which an optimal solution of the deterministic equivalent can be obtained in a finite number of iterations. Our new method can be interpreted as a compromise between the Benders single-cuts and multi-cuts methods, drawing on the advantages of both sides, by rendering the initial iterations faster (as for the single-cuts Benders) and ensuring the overall faster convergence (as for the multi-cuts Benders). Computational experiments on three TSSPs validate these statements, showing that the new method outperforms the other implementations of Benders method, as well as other standard methods for solving TSSPs, in particular when the number of scenarios is very large. Joint work with Ivana Ljubic (ESSEC Business School).

In the Kidney Exchange Problem (KEP), we consider a pool of altruistic donors and incompatible patient-donor pairs. Kidney exchanges can be modelled in a directed weighted graph as circuits starting and ending in an incompatible pair or as paths starting at an altruistic donor. The weights on the arcs represent the medical benefit which measures the quality of the associated transplantation. For medical reasons, circuits and paths are of limited length and are associated with a medical benefit to perform the transplants. The aim of the KEP is to determine a set of disjoint kidney exchanges of maximal medical benefit or maximal cardinality (all weights equal to one). In this work, we consider two types of uncertainty in the KEP which stem from the estimation of the medical benefit (weights of the arcs) and from the failure of a transplantation (existence of the arcs). Both uncertainty are modelled via uncertainty sets with constant budget. The robust approach entails finding the best KEP solution in the worst-case scenario within the uncertainty set. We modelled the robust counter-part by means of a max-min formulation which is defined on exponentially-many variables associated with the circuits and paths. We propose different exact approaches to solve it: either based on the result of Bertsimas and Sim or on a reformulation to a single-level problem. In both cases, the core algorithm is based on a Branch-Price-and-Cut approach where the exponentially-many variables are dynamically generated. The computational experiments prove the efficiency of our approach.

Column generation is used alongside Dantzig-Wolfe Decomposition, especially for linear programs having a decomposable pricing step requiring to solve numerous independent pricing subproblems. We propose a filtering method to detect which pricing subproblems may have improving columns, and only those subproblems are solved during pricing. This filtering is done by providing light, computable bounds using dual information from previous iterations of the column generation. The experiments show a significant impact on different combinatorial optimization problems.

Abstract: Starting from the general proposal of Grzybowski et al. that defines the concept of separation of two finite point sets X and Y by means of a convex set S, we consider the case where S is the minimum volume ellipsoid that intersects the convex combinations of all pairs of points in X and Y. According to this separation rule it is possible to consider an ellipsoid S which contains one class and leave out the other one, or an ellipsoid that does not contain neither of the two classes but still separates them. These two cases can be used to define two binary classifiers whose fitting problems relies on the solution of different Semi-definite programs. In this seminar I will introduce both ellipsoidal binary classifiers together with the corresponding semi-definite programming and some algorithmic approaches to solve it more efficiently. Some numerical experiments will be also presented.

One of the key properties of convex problems is that every stationary point is a global optimum, and nonlinear programming algorithms that converge to local optima are thus guaranteed to find the global optimum. However, some nonconvex problems possess the same property. This observation has motivated research into generalizations of convexity. This talk proposes a new generalization which we refer to as optima-invexity: the property that only one connected set of optimal solutions exists. We state conditions for optima-invexity of unconstrained problems and discuss structures that are promising for practical use, and outline algorithmic applications of these structures.

After a general presentation of the company Califrais and of research problems arising in food supply chain, we will focus on a recent work on online inventory problems. These are decision problems where at each time period the manager has to make a replenishment decision based on partial historical information in order to meet demands and minimize costs. To solve such problems, we build upon recent works in online learning and control, use insights from inventory theory and propose a new algorithm called GAPSI. This algorithm follows a new feature-enhanced base-stock policy and deals with the troublesome question of non-differentiability which occurs in inventory problems. Our method is illustrated in the context of a complex and novel inventory system involving multiple products, lost sales, perishability, warehouse-capacity constraints and lead times. Extensive numerical simulations are conducted to demonstrate the good performances of our algorithm on real-world data.

The Binary Boolean Optimization (BPO) problem aims at finding the maximal value that a rational polynomial P(x) can take when x is supposed to be a vector with 0 and 1 values. This non-linear optimization problem has recently received renewed attention. Current techniques for solving it either involve to solve a linear relaxation of the problem or use dedicated algorithm exploiting some structure in the way monomials are interacting with one another, allowing one to skip large parts of the search space compared to the brute force approach. In this talk, we present and explore the consequences of an interesting connection between BPO instances and another well studied problem on Boolean functions: the Algebraic Model Counting (AMC) problem. Given a Boolean function f on variables X and a weight on each of its variable, the AMC problem aims at finding the sum of the weights of every satisfying assignments of f. This problem can encode a lot of different tasks by simply changing the underlying algebraic structure where the sum and products are made. This way, we show how one can reformulate BPO instances as an AMC problem on an algebraic structure known as the (max,+)-semiring. The consequences of this connection are manyfold. In particular, we are able to recover every known results on the tractablability of BPO problem from this connection and the existing literature on the complexity of AMC. More importantly, this connection allows us to discover new tractable classes for BPO and is flexible enough so that we can find tractable instances of the slight variations of BPO such as BPO with cardinality constraints or pseudo-Boolean BPO, two problems for which few tractability results where known. More importantly, this approach yields practical results: by running a modified version of d4, a tool originally made for knowledge compilation, so that it performs AMC on the (max,+)-semiring instead, we show that our approach is competitive with the existing ones on hard instances. This talk will cover a gentle presentation of the BPO problem and its connection with AMC. We will then give a quick overview on existing techniques for solving AMC that are based on Knowledge Compilation and how this approach is fruitful for solving extensions of the BPO problem. We will conclude by a presentation of the way d4 works and of our practical results.

The linear ordering problem consists in finding a linear order < on a finite set A so as to minimize the sum of costs associated with pairs of elements a,b for which a < b. The problem is NP-hard and APX-hard. We introduce algorithms for solving the problem *partially* by deciding efficiently for some pairs (a,b) whether a