Liste des articles, rangés par catégories

Applications

[AP2] Design and dimensioning of hydrogen transmission pipeline networks.
[DW12] A Steiner tree approach to efficient object detection.
[FM6] Exact route-length formulas and a storage location assignment heuristic for picker-to-parts warehouses.
[SE12] MIP models for connected facility location: A theoretical and computational study.
[SK5] Multiechelon Lot Sizing: New Complexities and Inequalities.
[SK6] Solving Real-Life Locomotive-Scheduling Problems.
[CA11] Branch Flow Model: Relaxations and Convexification: Part I.
[CB3] A heuristic solution procedure for the dynamic lot sizing problem with remanufacturing and product recovery.
[CB5] An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges.
[CB23] Lot sizing with carbon emission constraints.
[CB34] Non-cyclic train timetabling and comparability graphs. (ATTENTION : un rapport de recherche associé à cet article et contenant plusieurs preuves est également à lire !)
[CB51] Polynomially solvable personnel rostering problems.

Graphes et complexité

[DW5] Upgrading min–max spanning tree problem under various cost functions.
[DW9] An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph.
[DW11] P=NP.
[DW13] LCA Queries in Directed Acyclic Graphs.
[DW14] « Non-Identity-Check » is QMA-Complete.
[FM1] Perfect Digraphs.
[FM4] A tight bound on approximating arbitrary metrics by tree metrics.
[OH1] Complexity results for identifying codes in planar graphs.
[OH2] Minimum sizes of identifying codes in graphs differing by one vertex.
[CP1] Critical Independent Sets and König–Egerváry Graphs.
[CP2] A note on the computational complexity of graph vertex partition.
[CP3] A fast algorithm for equitable coloring.
[CP5] The NP-Completeness of Some Edge-Partition Problems.
[CP7] Multigraph realizations of degree sequences: Maximization is easy, minimization is hard.
[CP8] On finding cycle bases and fundamental cycle bases with a shortest maximal cycle.
[CP9] On the complexity of some subgraph problems.
[CP10a] A note on a conjecture on maximum matching in almost regular graphs et [CP10b] On maximum matchings in almost regular graphs. (Les deux articles sont à lire.)
[CP11] The Next-to-Shortest Path Problem on Directed Graphs with Positive Edge Weights.
[CP12] Steinberg’s Conjecture is false.
[CP13] Matching Cutsets in Graphs.
[CP14] Decomposing graphs under degree constraints.
[CB38] On the complexity of the identifiable subgraph problem.

Optimisation robuste/multicritère ou stochastique

[SK2] Cutting Planes for Multistage Stochastic Integer Programs.
[CA1] Bicriteria path problem minimizing the cost and minimizing the number of labels.
[CA5] Exact solution of the robust knapsack problem.
[CA10] A label-setting algorithm for finding a quickest path.
[CB28] A linear programming approach for linear programs with probabilistic constraints.

Heuristiques

[SE13] Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps.
[CA6] Lower bounds and heuristic algorithms for the k_i-partitioning problem.
[CB1] The asymmetric bottleneck traveling salesman problem: Algorithms, complexity and empirical analysis.

Ordonnancement

[SK3] The Effects of Multitasking on Operations Scheduling.
[SK4] Server scheduling on parallel dedicated machines with fixed job sequences.
[CB13] A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times.
[CB40] From preemptive to non-preemptive speed-scaling scheduling.

Programmation mathématique

[AL2] A new exact discrete linear reformulation of the quadratic assignment problem.
[AP1] An exact algorithm for the maximum leaf spanning tree problem.
[ML1] The value function of an integer program.
[SE8] Chvatal Closures for Mixed Integer Programming Problems.
[SE10] « Facet » separation with one linear program.
[SE11] A Recursive Procedure to Generate all Cuts for 0-1 Mixed Integer Programs.
[SE14] On the Complexity of Separating Cutting Planes for the Knapsack Polytope.
[ZA1] Mixed integer programming formulations for clustering problems related to structural balance.
[ZA3] Improved compact formulations for a wide class of graph partitioning problems in sparse graphs.
[ZA4] Min–max–min robust combinatorial optimization.
[CA2] Bilevel programming and the separation problem.
[CA3] A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support.
[CA4] A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming.
[CA7] Solving Large Steiner Triple Covering Problems.
[CA8] A polyhedral study of the asymmetric travelling salesman problem with time windows.
[CA9] Strengthening Chvatal-Gomory cuts and Gomory fractional cuts.
[CB37] Well-solvable cases of the QAP with block-structured matrices.

Applications

[AP2] Jean André, Stéphane Auray, Jean Brac, Daniel De Wolf, Guy Maisonnier, Mohamed-Mahmoud Ould-Sidi, Antoine Simonnet. Design and dimensioning of hydrogen transmission pipeline networks. European Journal of Operational Research 229 (2013) 239-251.
Cet article considère le problème de la conception optimale d'un réseau de transmission d'hydrogène combinant la recherche d’une topologie du réseau la moins coûteuse et la déterminations de diamètres optimaux pour les pipelines déployés. Tout d’abord, une formulation du problème via un programme mathématique non linéaire est présentée. Puis, les auteurs proposent une résolution approchée du problème via une heuristique de recherche locale. Des expérimentations numériques sont effectuées sur des instances réelles liées au développement de futurs réseaux de canalisations d'hydrogène en France aux niveaux local, régional et national. Les résultats obtenus sont comparés avec ceux émanant d’une heuristique de recherche tabou.
Mots-clés : application (transport d'hydrogène), dimensionnement de réseau, modélisation, recherche locale, résultats numériques

[DW12] Olga Russakovsky, Andrew Y. Ng. A Steiner tree approach to efficient object detection. IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2010, pages 1070-1077.
We propose an approach to speeding up object detection, with an emphasis on settings where multiple object classes are being detected. Our method uses a segmentation algorithm to select a small number of image regions on which to run a classifier. Compared to the classical sliding window approach, this results in a significantly smaller number of rectangles examined, and thus significantly faster object detection. Further, in the multiple object class setting, we show that the computational cost of proposing candidate regions can be amortized across objects classes, resulting in an additional speedup. At the heart of our approach is a reduction to a directed Steiner tree optimization problem, which we solve approximately in order to select the segmentation algorithm parameters. The solution gives a small set of segmentation strategies that can be shared across object classes. Compared to the sliding window approach, our method results in two orders of magnitude fewer regions considered, and significant (10-15×) running time speedups on challenging object detection datasets (LabelMe and StreetScenes) while maintaining comparable detection accuracy.
Mots-clés : application (détection d'objets), arbres de Steiner orientés, résultats numériques

[FM6] Arjan S. Dijkstra, Kees Jan Roodbergen. Exact route-length formulas and a storage location assignment heuristic for picker-to-parts warehouses. Transportation Research Part E 102 (2017) 38-59.
Order picking is one of the most time-critical processes in warehouses. We focus on the combined effects of routing methods and storage location assignment on process performance. We present exact formulas for the average route length under any storage location assignment for four common routing methods. Properties of optimal solutions are derived that strongly reduce the solution space. Furthermore, we provide a dynamic programming approach that determines storage location assignments, using the route length formulas and optimality properties. Experiments underline the importance of the introduced procedures by revealing storage assignment patterns that have not been described in literature before.
Mots-clés : application (gestion d'entrepôts), stockage et routage optimaux, programmation dynamique, résultats numériques

[SE12] Stefan Gollowitzer, Ivana Ljubic. MIP models for connected facility location: A theoretical and computational study. Computers & Operations Research 38 (2011) 435-449.
This article comprises the first theoretical and computational study on mixed integer programming (MIP) models for the connected facility location problem (ConFL). ConFL combines facility location and Steiner trees: given a set of customers, a set of potential facility locations and some inter-connection nodes, ConFL searches for the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The costs needed for building the Steiner tree, facility opening costs and the assignment costs need to be minimized. We model ConFL using seven compact and three mixed integer programming formulations of exponential size. We also show how to transform ConFL into the Steiner arborescence problem. A full hierarchy between the models is provided. For two exponential size models we develop a branch-and-cut algorithm. An extensive computational study is based on two benchmark sets of randomly generated instances with up to 1300 nodes and 115,000 edges. We empirically compare the presented models with respect to the quality of obtained bounds and the corresponding running time. We report optimal values for all but 16 instances for which the obtained gaps are below 0.6%.
Mots-clés : application (facility location), Steiner trees; mixed integer programming models, LP relaxations, numerical experiments

[SK5] Ming Zhao, Minjiao Zhang. Multiechelon Lot Sizing: New Complexities and Inequalities. Operations Research 68 (2020).
We study a multiechelon lot-sizing problem for a serial supply chain that consists of a production level and several transportation levels, where the demands can exist in the production echelon as well as in any transportation echelons. With the presence of stationary production capacity and general cost functions, our model integrates production, inventory, and transportation decisions and generalizes existing literature on many multiechelon lot-sizing models. First, we answer an open question in the literature by showing that multiechelon lot-sizing with intermediate demands (MLS) is NP-hard. Second, we develop polynomial-time algorithms for both uncapacitated and capacitated MLS with a fixed number of echelons. The run times of our algorithms improve on those of many known algorithms for different MLS models. Third, we present families of valid inequalities for MLS that generalize known inequalities. For the uncapacitated case, we develop a polynomial-time separation algorithm and efficient separation heuristics. Finally, we demonstrate the effectiveness of a branch-and-cut algorithm using proposed inequalities to solve large multi-item MLS problems.
Mots-clés : application (lot-sizing/dimensionnement de lots), programmation dynamique, flots dans les réseaux, algorithmes polynomiaux, inégalités valides

[SK6] Ravindra K. Ahuja, Jian Liu, James B. Orlin, Dushyant Sharma, Larry A. Shughart. Solving Real-Life Locomotive-Scheduling Problems. Transportation Science 39 (2005) 503-517.
In the locomotive-scheduling problem (or the locomotive-assignment problem), we must assign a consist (a set of locomotives) to each train in a preplanned train schedule so as to provide each train with sufficient locomotive power to pull the train from its origin to its destination. Locomotive-scheduling problems are among the most important problems in railroad scheduling. In this paper, we report the results of a study on the locomotive-scheduling problem as it is faced by CSX Transportation, a major U.S. railroad company. We consider the planning version of the locomotive-scheduling model (LSM) in which multiple types of locomotives exist, and we need to decide which set of locomotives should be assigned to each train. We present an integrated model that determines: the set of active and deadheaded locomotives for each train; the light-traveling locomotives from power sources to power sinks; and train-to-train connections (for which we specify which inbound trains and outbound trains can directly connect). An important feature of our model is that we explicitly consider consist bustings and consistency. A consist is said to be busted when a set of locomotives coming on an inbound train is broken into subsets to be reassigned to two or more outbound trains. A solution is consistent over a week if a train receives the same locomotive assignment each day that it runs. We will provide a mixed-integer programming (MIP) formulation of the locomotive-assignment problem. However, a MIP of this size cannot be solved to optimality or near optimality in acceptable running times using commercially available software. Using problem decomposition, integer programming, and very large-scale neighborhood search, we have developed a solution technique to solve this problem within 30 minutes of computation time on a Pentium III computer. Our solution obtained a potential savings of over 400 locomotives over the solution obtained by the in-house software developed by CSX.
Mots-clés : application (ordonnancement pour le trafic ferroviaire), PLNE, optimisation dans les réseaux/graphes

[CA11] M. Farivar, S. H. Low. Branch Flow Model: Relaxations and Convexification: Part I. IEEE TRANSACTIONS ON POWER SYSTEMS 28 (2013) 2565-2572.
We propose a branch flow model for the analysis and optimization of mesh as well as radial networks. The model leads to a new approach to solving optimal power flow (OPF) that consists of two relaxation steps. The first step eliminates the voltage and current angles and the second step approximates the resulting problem by a conic program that can be solved efficiently. For radial networks, we prove that both relaxation steps are always exact, provided there are no upper bounds on loads. For mesh networks, the conic relaxation is always exact but the angle relaxation may not be exact, and we provide a simple way to determine if a relaxed solution is globally optimal. We propose convexification of mesh networks using phase shifters so that OPF for the convexified network can always be solved efficiently for an optimal solution. We prove that convexification requires phase shifters only outside a spanning tree of the network and their placement depends only on network topology, not on power flows, generation, loads, or operating constraints. Part I introduces our branch flow model, explains the two relaxation steps, and proves the conditions for exact relaxation. Part II describes convexification of mesh networks, and presents simulation results.
Mots-clés : application (power system management), convex relaxation, load flow control, optimal power flow

[CB3] M. Fazle Baki, Ben A.Chaouch, Walid Abdul-Kader. A heuristic solution procedure for the dynamic lot sizing problem with remanufacturing and product recovery. Computers & Operations Research 43 (2014) 225–236.
Here we discuss the lot sizing problem of product returns and remanufacturing. Let us consider a forecast of demands and product returns over a finite planning horizon — the problem is to determine an optimal production plan. This consists of either manufacturing new products or remanufacturing returned units, and in this way meets both demands at minimum costs. The costs of course are the fixed set-up expenses associated with manufacturing and/or remanufacturing lots and also the inventory holding costs of stocks kept on hand. In addition to showing that a general instance of this problem is NP-Hard, we develop an alternative mixed-integer model formulation for this problem and contrast it to the formulation commonly used in the literature. We show that when integrality constraints are relaxed, our formulation obtains better bounds. Our formulation incorporates the fact that every optimal solution can be decomposed into a series of well-structured blocks with distinct patterns in the way in which set-ups for manufacturing and remanufacturing occur. We then construct a dynamic programming based heuristic that exploits the block structure of the optimal solution. We also propose some improvement schemes as well. Finally, our numerical testing shows that the heuristic performs very well as intended.
Mots-clés : application (lot-sizing), NP-complétude, PLNE, heuristique, programmation dynamique, résultats numériques

[CB5] André Rossi, Alok Singh, Marc Sevaux. An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges. Computers & Operations Research 39 (2012) 3166–3176.
This paper addresses the problem of target coverage for wireless sensor networks, where the sensing range of sensors can vary, thereby saving energy when only close targets need to be monitored. Two versions of this problem are addressed. In the first version, sensing ranges are supposed to be continuously adjustable (up to the maximum sensing range). In the second version, sensing ranges have to be chosen among a set of predefined values common to all sensors. An exact approach based on a column generation algorithm is proposed for solving these problems. The use of a genetic algorithm within the column generation scheme significantly decreases computation time, which results in an efficient exact approach.
Mots-clés : application (durée de vie optimale d'un réseau de capteurs), PLNE, Dantzig–Wolfe decomposition, algorithme génétique, résultats numériques

[CB23] Nabil Absi, Stéphane Dauzère-Pérès, Safia Kedad-Sidhoum, Bernard Penz, Christophe Rapine. Lot sizing with carbon emission constraints. European Journal of Operational Research 227 (2013) 55–61.
This paper introduces new environmental constraints, namely carbon emission constraints, in multi-sourcing lot-sizing problems. These constraints aim at limiting the carbon emission per unit of product supplied with different modes. A mode corresponds to the combination of a production facility and a transportation mode and is characterized by its economical costs and its unitary carbon emission. Four types of constraints are proposed and analyzed in the single-item uncapacitated lot-sizing problem. The periodic case is shown to be polynomially solvable, while the cumulative, global and rolling cases are NP-hard. Perspectives to extend this work are discussed.
Mots-clés : application (green lot-sizing/dimensionnement de lots écologique), PLNE, programmation dynamique, NP-complétude

[CB34] Valentina Cacchiani, Alberto Caprara, Paolo Toth. Non-cyclic train timetabling and comparability graphs. Operations Research Letters 38 (2010) 179-184.
We consider the customary formulation of non-cyclic train timetabling, calling for a maximum-profit collection of compatible paths in a suitable graph. The associated ILP models look for a maximum-weight clique in a (n exponentially-large) compatibility graph. By taking a close look at the structure of this graph, we analyze the existing ILP models, propose some new stronger ones, all having the essential property that both the separation and the column generation can be carried out efficiently, and report the computational results on highly-congested instances.
Mots-clés : application (planification ferroviaire), PLNE, graphes, NP-complétude, programmation dynamique, résultats numériques.
ATTENTION : un rapport de recherche associé à cet article et contenant plusieurs preuves est également à lire !

[CB51] P. Smet, P. Brucker, P. De Causmaecker, G. Vanden Berghe. Polynomially solvable personnel rostering problems. European Journal of Operational Research 249 (2016) 67–75.
Personnel rostering is a personnel scheduling problem in which shifts are assigned to employees, subject to complex organisational and contractual time-related constraints. Academic advances in this domain mainly focus on solving specific variants of this problem using intricate exact or (meta)heuristic algorithms, while little attention has been devoted to studying the underlying structure of the problems. The general assumption is that these problems, even in their most simplified form, are NP-hard. However, such claims are rarely supported with a proof for the problem under study. The present paper refutes this assumption by presenting minimum cost network flow formulations for several personnel rostering problems. Additionally, these problems are situated among the existing academic literature to obtain insights into what makes personnel rostering hard.
Mots-clés : application (roulements de personnel), algorithme polynomial, algorithme pseudo-polynomial, flot à coût minimum

Graphes et complexité

[DW5] A.R. Sepasian, E. Monabbatis. Upgrading min–max spanning tree problem under various cost functions. Theoretical Computer Science 704 (2017) 87-91.
This paper addresses upgrading min–max spanning tree problem (MMST). Given a graph G = (V, E), the aim of this problem is to modify edge weights under certain limits and given budget so that the MMST with respect to perturbed graph improves as much as possible. We present a complexity result for general non-decreasing cost functions. In special case, it is shown that the problem under linear and sum-type Hamming cost function can be solved in O(|E|²) and O(|E| log|E| log|V|) time, respectively.
Mots-clés : location problems, upgrading problems, min–max spanning tree, polynomial-time algorithms

[DW9] P. G. Lehot. An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph. Journal of the ACM 21 (1974) 569–575.
Given a graph H with E edges and N nodes, a graph G is sought such that H is the line graph of G, if G exists. The algorithm does this within the order of E steps, in fact in E + O(N) steps. This algorithm is optimal in its complexity.
Mots-clés : line graph, root graph of a line graph, Hamiltonian cycle, Hamiltonian-Eulerian duality, node-edge transformation, polynomial-time algorithms

[DW11] S. Bringsjord, J. Taylor. P=NP. arXiv (manuscrit non publié), 2004.
Cet article prétend apporter la preuve que P=NP.
Mots-clés : théorie de la complexité, P versus NP, preuve fausse
ATTENTION : l'objectif ici sera de comprendre et d'évaluer les arguments utilisés dans cette preuve, pour être ensuite en mesure d'expliquer où se trouve(nt) la ou les erreur(s).

[DW13] Miroslaw Kowaluk, Andrzej Lingas. LCA Queries in Directed Acyclic Graphs. International Conference on Automata, Languages and Programming (ICALP) 2005, Lecture Notes in Computer Science (LNCS) 3580.
We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on n vertices and m edges. The first method is surprisingly natural and solves the all-pairs LCA problem for the input dag on n vertices and m edges in time O(nm). As a corollary, we obtain an O(n²)-time algorithm for finding genealogical distances considerably improving the previously known O(n^2.575) time-bound for this problem. The second method relies on a novel reduction of the all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time O(n^2+1/(4-ω)), where ω = 2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known O(n^(ω+3)/2) time-bound for the general all-pairs LCA problem in dags.
Mots-clés : lowest common ancestors, directed acyclic graph, polynomial-time algorithms

[DW14] Dominik Janzing, Pawel Wocjan, Thomas Beth. « Non-Identity-Check » is QMA-Complete. International Journal of Quantum Information 3 (2005) 463–473.
We describe a computational problem that is complete for the complexity class QMA, a quantum generalization of NP. It arises as a natural question in quantum computing and quantum physics. « Non-identity-check » is the following decision problem: given a classical description of a quantum circuit (a sequence of elementary gates), determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is « non-equivalence check »: given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that non-equivalence check is also in QMA and hence QMA-complete.
Mots-clés : informatique quantique, théorie de la complexité

[FM1] S. D. Andres, W. Hochstättler. Perfect Digraphs. Journal of Graph Theory 79 (2015) 21–29.
The clique number of a digraph D is the size of the largest bidirectionally complete subdigraph of D. D is perfect if, for any induced subdigraph H of D, the dichromatic number of H defined by Neumann-Lara (The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), 265–270) equals the clique number of H. Using the Strong Perfect Graph Theorem (M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51–229) we give a characterization of perfect digraphs by a set of forbidden induced subdigraphs. Modifying a recent proof of Bang-Jensen et al. (Finding an induced subdivision of a digraph, Theoret. Comput. Sci. 443 (2012), 10–24) we show that the recognition of perfect digraphs is co-NP-complete. It turns out that perfect digraphs are exactly the complements of clique-acyclic superorientations of perfect graphs. Thus, we obtain as a corollary that complements of perfect digraphs have a kernel, using a result of Boros and Gurvich (Perfect graphs are kernel solvable, Discrete Math. 159 (1996), 35–55). Finally, we prove that it is NP-complete to decide whether a perfect digraph has a kernel.
Mots-clés : dichromatic number, perfect graph, perfect digraph, Berge graph, clique number, clique-acyclic superorientation, (co-)NP-completeness

[FM4] J. Fakcharoenphol, S. Rao, K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences 69 (2004) 485–497.
In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log(n)). This improves upon the result of Bartal who gave a bound of O(log(n)log(log(n))). Moreover, our result is existentially tight; there exist metric spaces where any tree embedding must have distortion Ω(log(n))-distortion. This problem lies at the heart of numerous approximation and online algorithms including ones for group Steiner tree, metric labeling, buy-at-bulk network design and metrical task system. Our result improves the performance guarantees for all of these problems.
Mots-clés : metrics, embeddings, tree metrics, approximation

[OH1] D. Auger, I. Charon, O. Hudry, A. Lobstein. Complexity results for identifying codes in planar graphs. International Transactions in Operational Research 17(6) (2010) 691–710.
Let G be a simple, undirected, connected graph with vertex set V(G) and C be a subset of V(G) whose elements are called codewords. For v in V(G) and r ≥ 1, let us denote by I^C_r(v) the set of codewords c of C such that d(v, c) ≤ r, where the distance d(v, c) is defined as the length of a shortest path between v and c. More generally, for a subset A of V(G), we define I^C_r(A), which is the set of codewords whose minimum distance to an element of A is at most r. If r and l are positive integers, C is said to be an (r, ≤l)-identifying code if one has I^C_r(A) ≠ I^C_r(A') whenever A and A' are distinct subsets of V(G) with at most l elements. We consider the problem of finding the minimum size of an (r, ≤l)-identifying code in a given graph. It is already known that this problem is NP-hard in the class of all graphs when l = 1 and r = 1. We show that it is also NP-hard in the class of planar graphs with maximum degree at most three for all (r, l) with r = 1 and l = 1 or 2. This shows, in particular, that the problem of computing the minimum size of an (r, ≤2)-identifying code in a given graph is NP-hard.
Mots-clés : théorie des graphes, codes identifiants, graphes planaires, complexité, NP-complétude, NP-difficulté

[OH2] I. Charon, I. Honkala, O. Hudry, A. Lobstein. Minimum sizes of identifying codes in graphs differing by one vertex. Cryptography and Communications 5(2) (2013) 119-136.
Let G be a simple, undirected graph with vertex set V. For v in V and r ≥ 1, we denote by B_G,r(v) the ball of radius r and centre v. A subset C of V is said to be an r-identifying code in G if the sets B_G,r(v) ∩ C, for v in V, are all nonempty and distinct. A graph G admitting an r-identifying code is called r-twin-free, and in this case the size of a smallest r-identifying code in G is denoted by γ_r(G). We study the following structural problem: let G be an r-twin-free graph, and G* be a graph obtained from G by adding or deleting a vertex. If G* is still r-twin-free, we compare the behaviours of γ_r(G) and γ_r(G*), establishing results on their possible differences and ratios.
Mots-clés : théorie des graphes, graphes sans jumeaux, graphes identifiables, codes identifiants

[CP1] Vadim E. Levit, Eugen Mandrescu. Critical Independent Sets and König–Egerváry Graphs. Graphs and Combinatorics 28 (2012) 243-250.
A set S of vertices is independent or stable in a graph G, and we write S is in Ind(G), if no two vertices from S are adjacent, and α(G) is the cardinality of an independent set of maximum size, while core(G) denotes the intersection of all maximum independent sets. G is called a König–Egerváry graph if its order equals α(G) + μ(G), where μ(G) denotes the size of a maximum matching. The number def(G) = |V(G)| - 2μ(G) is the deficiency of G. The number d(G) = max{|S|-|N(S)| : S is in Ind(G)} is the critical difference of G. An independent set A is critical if |A|-|N(A)| = d(G), where N(S) is the neighborhood of S, and α_c(G) denotes the maximum size of a critical independent set. Larson (Eur J Comb 32:294–300, 2011) demonstrated that G is a König–Egerváry graph if and only if there exists a maximum independent set that is also critical, i.e., α_c(G) = α(G). In this paper we prove that: (i) d(G) = |core(G)| - |N(core(G))| = α(G) - μ(G) = def(G) holds for every König–Egerváry graph G; (ii) G is a König–Egerváry graph if and only if each maximum independent set of G is critical.
Mots-clés : théorie structurelle des graphes, ensembles stables, graphes de König–Egerváry

[CP2] Yuanqiu Huanga,Yuming Chu. A note on the computational complexity of graph vertex partition. Discrete Applied Mathematics 155 (2007) 405–409.
A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59–73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such that G-S is a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such that G-S is a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.
Mots-clés : algorithmique de graphes, ensembles stables, arbres

[CP3] H. A. Kierstead, A. V. Kostochka, M. Mydlarz, E. Szemerédi. A fast algorithm for equitable coloring. Combinatorica 30 (2010) 217-224.
A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most one. The celebrated Hajnal-Szemerédi Theorem states: For every positive integer r, every graph with maximum degree at most r has an equitable coloring with r+1 colors. We show that this coloring can be obtained in O(r n²) time, where n is the number of vertices.
Mots-clés : algorithmique de graphes, coloration équitable

[CP5] Ian Holyer. The NP-Completeness of Some Edge-Partition Problems. SIAM Journal on Computing 10 (1981) 713-717.
We show that for each fixed n ≥ 3 it is NP-complete to determine whether an arbitrary graph can be edge-partitioned into subgraphs isomorphic to the complete graph with n vertices. The NP-completeness of a number of other edge-partition problems follows immediately.
Mots-clés : partitionnement des arêtes d'un graphe, NP-complétude

[CP7] H. Huletta, T. G. Willa, G. J. Woeginger. Multigraph realizations of degree sequences: Maximization is easy, minimization is hard. Operations Research Letters 36 (2008) 594–596.
The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.
Mots-clés : séquence de degrés dans un multigraphe, NP-complétude

[CP8] G. Galbiati. On finding cycle bases and fundamental cycle bases with a shortest maximal cycle. Information Processing Letters 88 (2003) 155–159.
An undirected biconnected graph G with nonnegative integer lengths on the edges is given. The problem we consider is that of finding a cycle basis B of G such that the length of the longest cycle included in B is the smallest among all cycle bases of G. We first observe that Horton’s algorithm [SIAM J. Comput. 16 (2) (1987) 358–366] provides a fast solution of the problem that extends the one given by Chickering et al. [Inform. Process. Lett. 54 (1995) 55–58] for uniform graphs. On the other hand we show that, if the basis is required to be fundamental, then the problem is NP-hard and cannot be approximated within 2-ε, for all ε > 0, even with uniform lengths, unless P = NP. This problem remains NP-hard even restricted to the class of complete graphs; in this case it cannot be approximated within 13/11-ε, for all ε > 0, unless P = NP; it is instead approximable within 2 in general, and within 3/2 if the triangle inequality holds.
Mots-clés : bases de cycles dans un graphe, algorithmique de graphes, NP-complétude, inapproximabilité

[CP9] A. Scozzari, F. Tardella. On the complexity of some subgraph problems. Discrete Applied Mathematics 157 (2009) 3531–3539.
We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(n log(n))) time algorithm for such problems in graphs with vertex degree bounded by 3.
Mots-clés : détection de sous-graphes particuliers dans un graphe, NP-complétude, algorithmique de graphes

[CP10a] C. Picouleau. A note on a conjecture on maximum matching in almost regular graphs. Discrete Mathematics 310 (2010) 3646–3647.
Mkrtchyan, Petrosyan, and Vardanyan made the following conjecture: Every graph G with Δ(G) - δ(G) ≤ 1 has a maximum matching whose unsaturated vertices do not have a common neighbor. We disprove this conjecture.
[CP10b] P. Petrosyan. On maximum matchings in almost regular graphs. Discrete Mathematics 318 (2014) 58–61.
In 2010, Mkrtchyan, Petrosyan, and Vardanyan proved that every graph G with 2 ≤ δ(G) ≤ Δ(G) ≤ 3 contains a maximum matching M such that no two vertices uncovered by M share a neighbor, where Δ(G) and δ(G) denote the maximum and minimum degrees of vertices in G, respectively. In the same paper they suggested the following conjecture: every graph G with Δ(G) - δ(G) ≤ 1 contains a maximum matching M such that no two vertices uncovered by M share a neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample G with Δ(G) = 5 and δ(G) = 4. In this note, we show that the conjecture is false for graphs G with Δ(G)-δ(G) = 1 and Δ(G) ≥ 4, and for r-regular graphs when r ≥ 7.
Mots-clés : couplages maximums, graphes presque réguliers

[CP11] Bang Ye Wu, Hung-Lung Wang. The Next-to-Shortest Path Problem on Directed Graphs with Positive Edge Weights. Networks (2015).
Given an edge-weighted graph G and two distinct vertices s and t of G, the next-to-shortest path problem asks for a path from s to t of minimum length among all paths from s to t except the shortest ones. In this article, we consider the version where G is directed and all edge weights are positive. Some properties of the requested path are derived when G is an arbitrary digraph. In addition, if G is planar, an O(n³)-time algorithm is proposed, where n is the number of vertices of G.
Mots-clés : algorithme de graphe polynomial, graphe orienté valué, plus court chemin, second plus court chemin

[CP12] Vincent Cohen-Addad, Michael Hebdige, Daniel Král’, Zhentao Li, Esteban Salgado. Steinberg’s Conjecture is false. Journal of Combinatorial Theory, Series B 122 (2017) 452–456.
Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. We disprove this conjecture.
Mots-clés : théorie des graphes, graphes planaires, coloration de graphes, contre-exemple, conjecture de Steinberg

[CP13] Augustine M. Moshi. Matching Cutsets in Graphs. Journal of Graph Theory 13 (1989) 227-536.
Let G = (V, E) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of F are incident with the same point, and G-F has more components than G. Chvatal proved that it is NP-complete to recognize graphs with a matching cutset even if the input is restricted to graphs with maximum degree 4. We prove the following: (a) Every connected graph with maximum degree ≤ 3 and on more than 7 points has a matching cutset. (In particular, there are precisely two connected cubic graphs without a matching cutset). (b) Line graphs with a matching cutset can be recognized in O(|E|) time. (c) Graphs without a chordless circuit of length 5 or more that have a matching cutset can be recognized in O(|V||E|³) time.
Mots-clés : théorie des graphes, algorithmique de graphes, couplages, coupes

[CP14] Michael Stiebitz. Decomposing graphs under degree constraints. Journal of Graph Theory 23 (1996) 321-324.
If s and t are non-negative integers, and if G is a graph with minimum degrees s+t+1, then the vertex set of G can be partitioned into two sets which induce subgraphs of minimum degree at least s and t, respectively.
Mots-clés : théorie des graphes, partitionnement de graphes, degrés

[CB38] M. Kaminski, M. Milanic. On the complexity of the identifiable subgraph problem. Discrete Applied Mathematics 182 (2015) 25–33.
A bipartite graph G = (L, R; E) with at least one edge is said to be identifiable if for every vertex v in L, the subgraph induced by its non-neighbors has a matching of cardinality |L|-1. This definition arises in the context of low-rank matrix factorization and is motivated by signal processing applications. An l-subgraph of a bipartite graph G = (L, R; E) is an induced subgraph of G obtained by deleting from it some vertices in L together with all their neighbors. The Identifiable Subgraph problem is the problem of determining whether a given bipartite graph G = (L, R; E) contains an identifiable l-subgraph. While the problem of finding a smallest set J included in L that induces an identifiable l-subgraph of G is NP-hard and also APX-hard, the complexity of the identifiable subgraph problem is still open. In this paper, we introduce and study the k-bounded Identifiable Subgraph problem. This is the variant of the Identifiable Subgraph problem in which the input bipartite graphs G = (L, R; E) are restricted to have the maximum degree of vertices in R bounded by k. We show that for k = 3, the k-bounded Identifiable Subgraph problem is as hard as the general case, while it becomes solvable in linear time for k = 2. Our proof is based on the notion of strongly cyclic graphs, that is, multigraphs with at least one edge such that for every vertex v, no connected component of the graph obtained by deleting v is a tree. We show that a bipartite graph G = (L, R; E) with maximum degree of vertices in R bounded by 2 is a no instance to the Identifiable Subgraph problem if and only if a multigraph naturally associated to it does not contain any strongly cyclic subgraph, and characterize such graphs in terms of finitely many minimal forbidden topological minors.
Mots-clés : problème du sous-graphe identifiable, couplages, mineurs topologiques, algorithmes polynomiaux, complexité

Optimisation robuste/multicritère ou stochastique

[SK2] Y. Guan, S. Ahmed, G.L. Nemhauser. Cutting Planes for Multistage Stochastic Integer Programs. Operations Research 57 (2009) 287-298.
This paper addresses the problem of finding cutting planes for multistage stochastic integer programs. We give a general method for generating cutting planes for multistage stochastic integer programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem and for stochastic lot-sizing problems. We give computational results, which show that these new inequalities are very effective in a branch-and-cut algorithm.
Mots-clés : optimisation stochastique, PLNE, inégalités valides, branch and cut, résultats numériques

[CA1] M. Pascoal, M. E. Captivo, J. Climaco, A. Laranjeira. Bicriteria path problem minimizing the cost and minimizing the number of labels. 4OR-Q J Oper Res 11 (2013) 275–294.
We address a bicriterion path problem where each arc is assigned with a cost value and a label (such as a color). The first criterion intends to minimize the total cost of the path (the summation of its arc costs), while the second intends to get the solution with a minimal number of different labels. Since these criteria, in general, are conflicting criteria we develop an algorithm to generate the set of non-dominated paths. Computational experiments are presented and results are discussed.
Mots-clés : optimisation multi-critère, plus courts chemins étiquetés dans un graphe, frontière de Pareto, arbres de recherche, algorithmique de graphes, résultats numériques

[CA5] M. Monaci, U. Pferschy, P. Serafini. Exact solution of the robust knapsack problem. Computers & Operations Research 40 (2013) 2625–2631.
We consider an uncertain variant of the knapsack problem in which the weight of the items is not exactly known in advance, but belongs to a given interval, and an upper bound is imposed on the number of items whose weight differs from the expected one. For this problem, we provide a dynamic programming algorithm and present techniques aimed at reducing its space and time complexities. Finally, we computationally compare the performances of the proposed algorithm with those of different exact algorithms presented so far in the literature for robust optimization problems.
Mots-clés : optimisation robuste, sac-à-dos, programmation dynamique, résultats numériques

[CA10] C.-K. Park, S. Lee, S. Park. A label-setting algorithm for finding a quickest path. Computers & Operations Research 31 (2004) 2405-2418.
The quickest path problem is to find a path to send a given amount of data from the source to the destination with minimum transmission time. To find the quickest path, existing algorithms enumerate non-dominated paths with distinct capacity, and then determine a quickest path by comparing their transmission time. In this paper, we propose a label-setting algorithm for finding a quickest path by transforming a network to another network where an important property holds that each subpath of a quickest path is also a quickest path. The proposed algorithm avoids enumerating non-dominated paths whose transmission time is greater than the minimum transmission time. Although the computational complexity of the proposed algorithm is the same as that of existing algorithms, experimental results show that our algorithm is efficient when a network has two or more non-dominated paths.
Mots-clés : quickest path, dominated and non-dominated paths, label-setting algorithm, polynomial-time graph algorithm, numerical experiments

[CB28] Daniel Reich. A linear programming approach for linear programs with probabilistic constraints. European Journal of Operational Research 230 (2013) 487–494.
We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.
Mots-clés : programmes linéaires avec contraintes en probabilité, PLNE, heuristique, résultats numériques

Heuristiques

[SE13] Björn Geissler, Antonio Morsi, Lars Schewe, Martin Schmidt. Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps. SIAM Journal on Optimization 27 (2017) 1611-1636.
Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only a few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. Moreover, we propose a novel penalty framework that encompasses this alternating direction method, which allows us to refrain from random perturbations that are applied in standard versions of feasibility pumps in case of failure. We present a convergence theory for the new penalty based alternating direction method and compare the new variant of the feasibility pump with existing versions in an extensive numerical study for mixed-integer linear and nonlinear problems.
Mots-clés : heuristics, feasibility pumps, mixed-integer linear programming, non-linear programming, numerical results

[CA6] Mauro Dell’Amico, Manuel Iori, Silvano Martello, Michele Monaci. Lower bounds and heuristic algorithms for the k_i-partitioning problem. European Journal of Operational Research 171 (2006) 725–742.
We consider the problem of partitioning a set of positive integers values into a given number of subsets, each having an associated cardinality limit, so that the maximum sum of values in a subset is minimized, and the number of values in each subset does not exceed the corresponding limit. The problem is related to scheduling and bin packing problems. We give combinatorial lower bounds, reduction criteria, constructive heuristics, a scatter search approach, and a lower bound based on column generation. The outcome of extensive computational experiments is presented.
Mots-clés : partitionnement de graphes, heuristique, bornes inférieures, PLNE, génération de colonnes, résultats numériques

[CB1] John LaRusic, Abraham P. Punnen. The asymmetric bottleneck traveling salesman problem: Algorithms, complexity and empirical analysis. Computers & Operations Research 43 (2014) 20–35.
We consider the asymmetric bottleneck traveling salesman problem on a complete directed graph on n nodes. Various lower bound algorithms are proposed and the relative strengths of each of these bounds are examined using theoretical and experimental analysis. A polynomial time n/2-approximation algorithm is presented when the edge-weights satisfy the triangle inequality. We also present a very efficient heuristic algorithm that produced provably optimal solutions for 270 out of 331 benchmark test instances. Our algorithms are applicable to the maxmin version of the problem, known as the maximum scatter TSP. Extensive experimental results on these instances are also given.
Mots-clés : TSP, approximation, heuristique, bornes inférieures, résultats numériques

Ordonnancement

[SK3] N. Hall, J. Leung, C.-L. Li. The Effects of Multitasking on Operations Scheduling. Production and Operations Management 24 (2015) 1248–1265.
Cet article revisite les résultats fondamentaux en théorie de l'ordonnancement sous l'angle de l'ordonnancement multi-tâche. Des algorithmes polynomiaux ainsi que des résultats de complexité sont proposés pour différents critères d'optimisation.
Mots-clés : ordonnancement, multi-tâches, complexité, algorithmes polynomiaux

[SK4] T.C.E. Cheng, S. A. Kravchenko, B.M.T. Lin. Server scheduling on parallel dedicated machines with fixed job sequences. Naval Research Logistics 66 (2019) 321–332.
L'article traite de problèmes d'ordonnancement de tâches à machines parallèles dédiées. Les tâches doivent être chargées sur un serveur avant d'être traitées par une machine. La séquence de tâches à exécuter sur chaque machine est fixée. L'objectif est de minimiser la date de fin de l'ordonnancement. Un algorithme de programmation dynamique polynomial est proposé pour le problème à deux machines. Pour un plus grand nombre (arbitraire) de machines, le problème est prouvé NP-difficile. Deux heuristiques sont proposées pour des variantes du problème général.
Mots-clés : ordonnancement à machines parallèles, séquence fixée, serveur de tâches, programmation dynamique, NP-difficulté, heuristiques, résultats numériques

[CB13] C. Rapine, N. Brauner. A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times. Discrete Optimization 10 (2013) 241-250.
We consider the problem of scheduling independent jobs on a single resource under a special unavailability constraint: a set of forbidden instants is given, where no job is allowed to start or complete. We show that a schedule without idle time always exists if the number of forbidden instants is less than the number of distinct processing times appearing in the instance. We derive quite a fast algorithm to find such a schedule, based on an hybridization between a list algorithm and local exchange. As a corollary minimizing the makespan for a fixed number of forbidden instants is polynomial.
Mots-clés : ordonnancement, NP-complétude, algorithmique discrète

[CB40] E. Bampis, A. Kononov, D. Letsios, G. Lucarelli, I. Nemparis. From preemptive to non-preemptive speed-scaling scheduling. Discrete Applied Mathematics 181 (2015) 11–20.
We are given a set of jobs, each one specified by its release date, its deadline and its processing volume (work), and a single (or a set of) speed-scalable processor(s). We adopt the standard model in speed-scaling in which if a processor runs at speed s^α then the energy consumption is sa units of energy per time unit, where α > 1 is a small constant. Our goal is to find a schedule respecting the release dates and the deadlines of the jobs so that the total energy consumption to be minimized. While most previous works have studied the preemptive case of the problem, where a job may be interrupted and resumed later, we focus on the non-preemptive case where once a job starts its execution, it has to continue until its completion without any interruption. As the preemptive case is known to be polynomially solvable for both the single-processor and the multiprocessor case, we explore the idea of transforming an optimal preemptive schedule to a non-preemptive one. We prove that the preemptive optimal solution does not preserve enough of the structure of the non-preemptive optimal solution, and more precisely that the ratio between the energy consumption of an optimal non-preemptive schedule and the energy consumption of an optimal preemptive schedule can be very large even for the single-processor case. Then, we focus on some interesting families of instances: (i) equal-work jobs on a singleprocessor, and (ii) agreeable instances in the multiprocessor case. In both cases, we propose constant factor approximation algorithms. In the latter case, our algorithm improves the best known algorithm of the literature. Finally, we propose a (non-constant factor) approximation algorithm for general instances in the multiprocessor case.
Mots-clés : ordonnancement avec consommation d'énergie, algorithmes approchés polynomiaux

Programmation mathématique

[AL2] A. Nyberg, T. Westerlund. A new exact discrete linear reformulation of the quadratic assignment problem. European Journal of Operational Research 220 (2012): 314–319.
The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.
Mots-clés : problème d'affectation quadratique, reformulation linéaire discrète, programmation en variables mixtes, résultats numériques

[AP1] T. Fujie. An exact algorithm for the maximum leaf spanning tree problem. Computers & Operations Research 30 (2003): 1931–1944.
Given a connected graph, the Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree whose number of leaves (degree-one vertices) is maximum. We propose a branch-and-bound algorithm for MLSTP, in which an upper bound is obtained by solving a minimum spanning tree problem. We report computational results for randomly generated graphs and grid graphs with up to 100 vertices.
Mots-clés : branch and bound, spanning trees, integer programming, numerical experiments

[ML1] C. E. Blair, R. G. Jeroslow. The value function of an integer program. Mathematical Programming 23 (1982) 237–273.
Cet article traite de la fonction valeur d'un programme linéaire en nombres entiers, c'est-à-dire la valeur optimale comme fonction du membre de droite des contraintes. Les auteurs identifient à quelle classe de fonctions cette fonction valeur appartient. C'est un premier pas vers une théorie de la dualité pour la programmation linéaire en nombres entiers.
Mots-clés : fonction valeur, programmation linéaire en nombres entiers, fonctions de Gomory
ATTENTION : cet article est long et nécessitera de bien identifier et sélectionner les parties à aborder dans le temps imparti.

[SE8] W. Cook, R. Kannan, A. Schrijver. Chvatal Closures for Mixed Integer Programming Problems. Mathematical Programming 47 (1990) 155-174.
Chvatal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedron P and integral vector w, if max{wx / x is in P, wx integer} = t, then wx ≤ t is valid for all integral vectors in P. We consider the variant of this step where the requirement that wx be integer may be replaced by the requirement that w'x be integer for some other integral vector w'. The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedron P, the set of vectors that satisfy every cutting plane for P with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvatal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.
Mots-clés : linear integer programming, valid inequalities, recursive procedure

[SE10] Michele Conforti, Laurence A. Wolsey. « Facet » separation with one linear program. Mathematical Programming (Series A) 178 (2019) 361-380.
Given polyhedron P and and a point x*, the separation problem for polyhedra asks to certify that x* is in P and, if not, to determine an inequality that is satisfied by P and violated by x*. This problem is repeatedly solved in cutting plane methods for Integer Programming and the quality of the violated inequality is an essential feature in the performance of such methods. In this paper we address the problem of finding efficiently an inequality that is violated by x* and either defines an improper face or a facet of P. We show that, by solving a single linear program, one almost surely obtains such an improper face or facet.
Mots-clés : PLNE, problèmes de séparation, formulations étendues, plans coupants

[SE11] George L. Nemhauser, Laurence A. Wolsey. A Recursive Procedure to Generate all Cuts for 0-1 Mixed Integer Programs. Mathematical Programming 46 (1990) 379-390.
We study several ways of obtaining valid inequalities for mixed integer programs. We show how inequalities obtained from a disjunctive argument can be represented by superadditive functions and we show how the superadditive inequalities relate to Gomory's mixed integer cuts. We also show how all valid inequalities for mixed 0-1 programs can be generated recursively from a simple subclass of the disjunctive inequalities.
Mots-clés : PLNE, variables 0-1, inégalités valides, plans coupants, inégalités disjonctives, fonctions superadditives

[SE14] Alberto Del Pia, Jeff Linderoth, Haoran Zhu. On the Complexity of Separating Cutting Planes for the Knapsack Polytope. Mathematical Programming, Series B (2023).
We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, (1,k)-configuration inequalities, and weight inequalities are all NP-complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can be solved in polynomial time.
Mots-clés : PLNE, problème de séparation, sac à dos, plans coupants, polytope, théorie de la complexité

[ZA1] R. Figueiredo, G. Moura. Mixed integer programming formulations for clustering problems related to structural balance. Social Networks 35 (2013) 639-651.
In this work, we study graph clustering problems associated with structural balance. One of these problems is known in computer science literature as the correlation-clustering (CC) problem and another (RCC) can be viewed as its relaxed version. The solution of CC and RCC problems has been previously used in the literature as tools for the evaluation of structural balance in a social network. Our aim is to solve these problems to optimality. We describe integer linear programming formulations for these problems which includes the first mathematical formulation for the RCC problem. We also discuss alternative models for the relaxed structural balance and the solution of clustering problems associated with these new models. Numerical experiments are carried out with each formulation on a set of benchmark instances available in the literature.
Mots-clés : programmation linéaire entière, partitionnement de graphes signés, équilibre structurel, réseaux sociaux, résultats numériques

[ZA2] V. Kaibel, M. Peinhardt, M. E. Pfetsch. Orbitopal fixing. Discrete Optimization 8 (2011) 595-610.
The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the order of the subsets of the partition is irrelevant, since this kind of symmetry unnecessarily blows up the search tree. We present a general tool, called orbitopal fixing, for enhancing the capabilities of branch-and-cut algorithms in solving such symmetric integer programming models. We devise a linear time algorithm that, applied at each node of the search tree, removes redundant parts of the tree produced by the above mentioned symmetry. The method relies on certain polyhedra, called orbitopes, which have been introduced in [14]. It does, however, not explicitly add inequalities to the model. Instead, it uses certain fixing rules for variables. We demonstrate the computational power of orbitopal fixing at the example of a graph partitioning problem.
Mots-clés : programmation linéaire entière, partitionnement de graphes, traitement des symétries, branch and cut, résultats numériques

[ZA3] D.P. Nguyen, M. Minoux, V.H. Nguyen, T.H. Nguyen, R. Sirdey. Improved compact formulations for a wide class of graph partitioning problems in sparse graphs. Discrete Optimization 25 (2017) 175-188.
Given an undirected connected graph G = (V, E) where |V| = n and |E| = m, we consider a wide class of graph partitioning problems, which includes as special cases several versions classically considered in the literature. These problems are to find a partition of the nodes in V into clusters satisfying several generic constraints (of set function type) on the clusters, in order to minimize the number (or the total weight) of the edges whose end-nodes do not belong to the same cluster. Partitions of V are often modeled by using compact integer programming formulations containing O(n³) triangle inequalities. The latter is the same whatever the sparsity of graph G could be, i.e. its size does not depend on m. In this paper, we show that one can reduce the size of the integer programming formulation to O(nm) triangle inequalities. Moreover, it is shown that, when the additional constraints on the clusters satisfy some monotonicity property, the strength of the linear programming relaxation is preserved by this reduction. We present numerical experiments on two important special cases arising from applications to show the benefit in terms of computational efficiency of using the reduced formulation.
Mots-clés : programmation entière, partitionnement de graphes, inégalités triangulaires, résultats numériques

[ZA4] Christoph Buchheim, Jannis Kurtz. Min–max–min robust combinatorial optimization. Math. Program., Ser. A 163 (2017) 1-23.
The idea of k-adaptability in two-stage robust optimization is to calculate a fixed number k of second-stage policies here-and-now. After the actual scenario is revealed, the best of these policies is selected. This idea leads to a min–max–min problem. In this paper, we consider the case where no first stage variables exist and propose to use this approach to solve combinatorial optimization problems with uncertainty in the objective function. We investigate the complexity of this special case for convex uncertainty sets. We first show that the min–max–min problem is as easy as the underlying certain problem if k is greater than the number of variables and if we can optimize a linear function over the uncertainty set in polynomial time. We also provide an exact and practical oracle-based algorithm to solve the latter problem for any underlying combinatorial problem. On the other hand, we prove that the min–max–min problem is NP-hard for every fixed number k, even when the uncertainty set is a polyhedron, given by an inner description. For the case that k is smaller or equal to the number of variables, we finally propose a fast heuristic algorithm and evaluate its performance.
Mots-clés : robust optimization, k-adaptability, NP-hardness, heuristics, numerical experiments

[CA2] A. Lodi, T. K. Ralphs, G. J. Woeginger. Bilevel programming and the separation problem. Mathematical Programming, Series A (2013).
In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program. In some cases, this bilevel program can be easily reformulated as a simple single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no such polynomial-size single-level reformulation exists unless the polynomial hierarchy collapses to its first level (an event considered extremely unlikely in computational complexity theory). We illustrate our insights by considering the separation problem for two well-known classes of valid inequalities.
Mots-clés : programmation biniveau, problème de séparation, programmation linéaire, hiérarchie polynomiale

[CA3] J. Luedtke. A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support. Mathematical Programming, Series A (2013).
We present a new approach for exactly solving chance-constrained mathematical programs having discrete distributions with finite support and random polyhedral constraints. Such problems have been notoriously difficult to solve due to nonconvexity of the feasible region, and most available methods are only able to find provably good solutions in certain very special cases. Our approach uses both decomposition, to enable processing subproblems corresponding to one possible outcome at a time, and integer programming techniques, to combine the results of these subproblems to yield strong valid inequalities. Computational results on a chance-constrained formulation of a resource planning problem inspired by a call center staffing application indicate the approach works significantly better than both an existing mixed-integer programming formulation and a simple decomposition approach that does not use strong valid inequalities. We also demonstrate how the approach can be used to efficiently solve for a sequence of risk levels, as would be done when solving for the efficient frontier of risk and cost.
Mots-clés : programmes mathématiques avec contraintes en probabilité, PLNE, inégalités valides, Branch-and-Cut, résultats numériques

[CA4] D. C. Tozoni, P. J. de Rezende, C. C. de Souza. A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming. Optimization Online (2013).
In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, an ILP based algorithm is proposed to optimally solve the Art Gallery Problem (AGP), one of the most intensely studied problems in Computational Geometry. The basic idea of our method is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. Our algorithm was implemented and tested on almost three thousand instances and attained optimal solutions for the vast majority of them, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively and efficiently as the one described here. Evidence of its robustness is presented through tests done on a number of classes of polygons of various sizes with and without holes.
Mots-clés : problèmes de géométrie algorithmique, PLNE, bornes inférieures, résultats numériques

[CA7] James Ostrowski, Jeff Linderoth, Fabrizio Rossi, Stefano Smriglio. Solving Large Steiner Triple Covering Problems. Optimization Online (2009).
Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to small set covering instances that provide a computational challenge for integer programming techniques. One major source of difficulty for instances of this family is their highly symmetric structure, which impairs the performance of most branch-and-bound algorithms. The largest instance in the family that has been solved corresponds to a Steiner Tripe System of order 81. We present optimal solutions to the set covering problems associated with systems of orders 135 and 243. The solutions are obtained by a tailored implementation of constraint orbital branching, a method for branching on general disjunctions designed to exploit symmetry in integer programs.
Mots-clés : PLNE, branchements (séparation), élimination de solutions, résultats numériques

[CA8] N. Ascheuer, M. Fischetti, M. Grötschel. A polyhedral study of the asymmetric travelling salesman problem with time windows. Networks 36(2) (2000) 69-79.
The asymmetric traveling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper, we present a formulation of the problem involving only 0/1 variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time-window restrictions are modeled using "infeasible path elimination" constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric traveling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, PTW, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of PTW is a strongly NP-complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for PTW. Computational experiments on the new formulation are reported in a companion paper, where we show that it outperforms alternative formulations on some classes of problem instances.
Mots-clés : asymmetric traveling salesman problem, time windows, polyhedral theory, valid inequalities

[CA9] A. N. Letchford, A. Lodi. Strengthening Chvatal-Gomory cuts and Gomory fractional cuts. Operations Research Letters 30 (2002) 74-82.
Chvatal–Gomory and Gomory fractional cuts are well-known cutting planes for pure integer programming problems. Various methods for strengthening them are known, for example based on subadditive functions or disjunctive techniques. We present a new and surprisingly simple strengthening procedure, discuss its properties, and present some computational results.
Mots-clés : integer programming, cutting planes, valid inequalities, numerical experiments

[CB37] E. Çela, V. G. Deineko, G. J. Woeginger. Well-solvable cases of the QAP with block-structured matrices. Discrete Applied Mathematics 186 (2015) 56–65.
We investigate special cases of the quadratic assignment problem (QAP) where one of the two underlying matrices carries a simple block structure. For the special case where the second underlying matrix is a monotone anti-Monge matrix, we derive a polynomial time result for a certain class of cut problems. For the special case where the second underlying matrix is a product matrix, we identify two sets of conditions on the block structure that make this QAP polynomially solvable and NP-hard, respectively.
Mots-clés : problème d'affectation quadratique, variables 0-1, algorithmes polynomiaux, complexité, condition de Monge