We consider mixed-integer linear quantile minimization problems that yield large-scale problems that are very hard to solve for real-world instances. We motivate the study of this problem class by two important real-world problems: a maintenance planning problem for electricity networks and a quantile-based variant of the classic portfolio optimization problem. For these problems, we develop valid inequalities and present an overlapping alternating direction method. Moreover, we discuss an adaptive scenario clustering method for which we prove that it terminates after a finite number of iterations with a global optimal solution. We study the computational impact of all presented techniques and finally show that their combination leads to an overall method that can solve the maintenance planning problem on large-scale real-world instances provided by the ROADEF/EURO challenge 2020 1 and that they also lead to significant improvements when solving a quantile-version of the classic portfolio optimization problem. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Deutsche Forschungsgemeinschaft [CRC TRR 154], Fonds De La Recherche Scientifique [PDR T0098.18], and Bundesministerium für Bildung und Forschung. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.0105 .

Support Vector Machines are models widely used in supervised classification. The classical model minimizes a compromise between the structural risk and the empirical risk. In this paper, we consider the Support Vector Machine with feature selection and we design and implement a bi-objective evolutionary algorithm for approximating the Pareto optimal frontier of the two objectives. The metaheuristic is based on the non-dominated sorting genetic algorithm and includes problem-specific knowledge. To demonstrate the efficiency of the algorithm proposed, we have carried out extensive computational experiments comparing the Pareto-frontiers given by the exact method AUGMECON2 and the metaheuristic approach respectively in a set of well known instances. In this paper, we also discuss some properties of the points in the Pareto frontier.

Abstract We show that the feasibility of a booking in the European entry‐exit gas market can be decided in polynomial time on single‐cycle networks that are passive, i.e., do not contain controllable elements. The feasibility of a booking can be characterized by solving polynomially many nonlinear potential‐based flow models for computing so‐called potential‐difference maximizing load flow scenarios. We thus analyze the structure of these models and exploit both the cyclic graph structure as well as specific properties of potential‐based flows. This enables us to solve the decision variant of the nonlinear potential‐difference maximization by reducing it to a system of polynomials of constant dimension that is independent of the cycle's size. This system of fixed dimension can be handled with tools from real algebraic geometry to derive a polynomial‐time algorithm. The characterization in terms of potential‐difference maximizing load flow scenarios then leads to a polynomial‐time algorithm for deciding the feasibility of a booking. Our theoretical results extend the existing knowledge about the complexity of deciding the feasibility of bookings from trees to single‐cycle networks.

The discrete ordered median problem (DOMP) is formulated as a set-partitioning problem using an exponential number of variables. Each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding costs. We develop a column generation approach to solve the continuous relaxation of this model. Then we apply a branch-price-and-cut algorithm to solve small- to large-sized instances of DOMP in competitive computational time.

In the so‐called network pricing problem an authority owns some arcs of the network and tolls them, while users travel between their origin and destination choosing their minimum cost path. In this article, we consider a unit toll scheme, and in particular the cases where the authority is imposing either the same toll on all of its arcs, or a toll proportional to a given parameter particular to each arc (for instance a per kilometer toll). We show that if tolls are all equal then the complexity of the problem is polynomial, whereas in case of proportional tolls it is pseudo‐polynomial, proposing ad‐hoc solution algorithms and relating these problems to the parametric shortest path problem. We then address a robust approach using an interval representation to take into consideration uncertainty on parameters. We show how to modify the algorithms for the deterministic case to solve the robust counterparts, maintaining their complexity class. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 83–93 2017

Abstract The ring spur assignment problem arises in the design of next‐generation telecommunications networks and has applications in location‐allocation problems. The aim is to identify a minimum cost set of interconnected ring spurs. We seek to connect all nodes of the network either on a set of bounded disjoint local rings or by a single spur edge connected to a node on a local ring. Local rings are interconnected by a special ring called the tertiary ring. We show that the problem is NP ‐Hard and present an Integer Programming formulation with additional valid inequalities. We implement a branch‐and‐cut algorithm and present our conclusions with computational results. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013

A loss of heterozygosity (LOH) event occurs when, by the laws of Mendelian inheritance, an individual should be heterozygote at a given site but, due to a deletion polymorphism, is not. Deletions play an important role in human disease and their detection could provide fundamental insights for the development of new diagnostics and treatments. In this paper, we investigate the parsimonious loss of heterozygosity problem (PLOHP), i.e., the problem of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas. Specifically, we generalize Halldórsson et al.'s work by providing a more general formulation of the PLOHP and by showing how one can incorporate different recombination rates and prior knowledge about the locations of deletions. Moreover, we show that the PLOHP can be formulated as a specific version of the clique partition problem in a particular class of graphs called undirected catch-point interval graphs and we prove its general $({\cal NP})$-hardness. Finally, we provide a state-of-the-art integer programming (IP) formulation and strengthening valid inequalities to exactly solve real instances of the PLOHP containing up to 9,000 individuals and 3,000 SNPs. Our results give perspectives on the mathematics of the PLOHP and suggest new directions on the development of future efficient exact solution approaches.

Aphylogeny is an unrooted binary tree that represents the evolutionary relationships of a set of n species. Phylogenies find applications in several scientific areas ranging from medical research, to drug discovery, to epidemiology, to systematics, and to population dynamics. In such applications, the available information is usually restricted to the leaves of a phylogeny and is represented by molecular data extracted from the analyzed species, such as DNA, RNA, amino acid, or codon fragments. On the contrary, the information about the phylogeny itself is generally missing and is determined by solving an optimization problem, called the phylogeny estimation problem (PEP), whose versions depend on the criterion used to select a phylogeny from among plausible alternatives. In this paper, we investigate a recent version of the PEP, called the balanced minimum evolution problem (BMEP). We present a mixed-integer linear programming model to exactly solve instances of the BMEP and develop branching rules and families of valid inequalities to further strengthen the model. Our results give perspective on the mathematics of the BMEP and suggest new directions on the development of future efficient exact approaches to solutions of the problem.

By means of a model based on a set covering formulation, it is shown how the p-median problem can be solved with just a column generation approach that is embedded in a branch-and-bound framework based on dynamic reliability branching. This method is more than competitive in terms of computational times and size of the instances that have been optimally solved. In particular, problems of a size larger than the largest ones considered in the literature up to now are solved exactly in this paper.

Abstract We investigate polyhedral properties of the following scheduling problem: given two sets of unit, indivisible jobs and revenue functions of the jobs completion times, find a one‐machine schedule maximizing the total revenue under the constraint that the schedule of each job set respects a prescribed chain‐like precedence relation. A solution to this problem is an order preserving assignment of the jobs to a set of time‐slots. We study the convex hull of the feasible assignments and provide families of facet‐defining inequalities in two cases: (i) each job must be assigned to a time‐slot and (ii) a job does not need to be assigned to any time‐slot. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Abstract In recent years, there has been an increased literature on so‐called generalized network design problems (GNDPs), such as the generalized minimum spanning tree problem and the generalized traveling salesman problem. In a GNDP, the node set of a graph is partitioned into “clusters,” and the feasible solutions must contain one node from each cluster. Up to now, the polyhedra associated with different GNDPs have been studied independently. The purpose of this article is to show that it is possible, to a certain extent, to derive polyhedral results for all GNDPs simultaneously. Along the way, we point out some interesting connections to other polyhedra, such as the quadratic semiassignment polytope and the boolean quadric polytope. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011

Haplotyping estimation from aligned single nucleotide polymorphism fragments has attracted increasing attention in recent years because of its importance in the analysis of fine-scale genetic data. Its application fields range from mapping of complex disease genes to inferring population histories, passing through designing drugs, functional genomics, and pharmacogenetics. The literature proposes several criteria for haplotyping populations, each of them characterized by biological motivations. One of the most important haplotyping criteria is parsimony, which consists of finding the minimum number of haplotypes necessary to explain a given set of genotypes. Parsimonious haplotype estimation is an 𝒩𝒫-hard problem for which the literature has proposed several integer programming (IP) models. Here, we describe a new polynomial-sized IP model based on the concept of class representatives, already used for the coloring problem. We propose valid inequalities to strengthen our model and show, through computational experiments, that our model outperforms the best IP models currently known in literature.

Abstract We consider the problem of setting revenue‐maximizing tolls on a subset of arcs of a transportation network, assuming that the users of the network are assigned to shortest paths with respect to the sum of tolls and initial costs. Our main results are concerned with a polyhedral study of the problem, i.e., the design of valid inequalities and facets for this pricing problem and some of its variants. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract A basic problem in molecular biology is to rebuild phylogenetic trees (PT) from a set of DNA or protein sequences. Among different criteria used for this purpose, the minimum evolution criterion is an optimality based criterion aiming to rebuild PT characterized by a minimal length. This problem is known to be 𝒩𝒫‐hard. We introduce in this article some mixed integer programming models, and we also study possible cuts and lower bounds for the optimal value. So far, the number of sequences that can be involved in optimal phylogenetic reconstruction is still limited to 10. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

In this paper, we present procedures to obtain facet-defining inequalities for the independence system polytope. These procedures are defined for inequalities which are not necessarily rank inequalities. We illustrate the use of these procedures by deriving strong valid inequalities for the acyclic induced subgraph, triangle free induced subgraph, bipartite induced subgraph, and knapsack polytopes. Finally, we derive a new family of facet-defining inequalities for the independence system polytope by adding a set of edges to antiwebs.

Abstract Optimality of a linear inequality in finitely many graph invariants is defined through a geometric approach. For a fixed number of graph vertices, consider all the tuples of values taken by the invariants on a selected class of graphs. Then form the polytope which is the convex hull of all these tuples. By definition, the optimal linear inequalities correspond to the facets of this polytope. They are finite in number, are logically independent, and generate precisely all the linear inequalities valid on the class of graphs. The computer system GraPHedron, developed by some of the authors, is able to produce experimental data about such inequalities for a “small” number of vertices. It greatly helps in conjecturing optimal linear inequalities, which are then hopefully proved for any number of vertices. Two examples are investigated here for the class of connected graphs. First, all the optimal linear inequalities for the stability number and the number of edges are obtained. To this aim, a problem of Ore (1962) related to the Turán Theorem (1941) is solved. Second, several optimal inequalities are established for three invariants: the maximum degree, the irregularity, and the diameter. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract We consider the problem of locating hubs and assigning terminals to hubs for a telecommunication network. The hubs are directly connected to a central node and each terminal node is directly connected to a hub node. The aim is to minimize the cost of locating hubs, assigning terminals and routing the traffic between hubs and the central node. We present two formulations and show that the constraints are facet‐defining inequalities in both cases. We test the formulations on a set of instances. Finally, we present a heuristic based on Lagrangian relaxation. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract This article deals with the Two‐edge connected Hop‐constrained Network Design Problem (or THNDP for short). Given a weighted graphG= (N,E), an integerL≥ 2, and a subset of pairs of nodesD, the problem consists of finding the minimum cost subgraph inGcontaining at least two edge‐disjoint paths of at mostLhops between all the pairs inD. First, we show that the THNDP is stronglyNP‐hard even when the demands inDare rooted at some nodesand the costs are unitary. However, if the graph is complete, we prove that the problem in this case can be solved in polynomial time. We give an integer programming formulation of the problem in the space of the design variables whenL= 2, 3. Then we study the associated polytope. In particular, we consider the case where all the pairs of nodes ofDare rooted at a nodes. We give several classes of valid inequalities along with necessary and/or sufficient conditions for these inequalities to be facet defining. We also derive separation routines for these inequalities. We finally develop a branch‐and‐cut algorithm based on these results and discuss some computational results forL= 2, 3. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(1), 116–133 2007

The p-center problem consists of choosing p facilities among a set of M possible locations and assigning N clients to them in order to minimize the maximum distance between a client and the facility to which it is allocated. We present a new integer linear programming formulation for this min-max problem with a polynomial number of variables and constraints, and show that its LP relaxation provides a lower bound tighter than the classical one. Moreover, we show that an even better lower bound LB*, obtained by keeping the integrality restrictions on a subset of the variables, can be computed in polynomial time by solving at most O(log2(NM)) linear programs, each having N rows and M columns. We also show that, when the distances satisfy triangle inequalities, LB* is at least one third of the optimal value. Finally, we use LB* in an exact solution method and report extensive computational results on test problems from the literature. For instances where the triangle inequalities are satisfied, our method outperforms the running time of other recent exact methods by an order of magnitude. Moreover, it is the first one to solve large instances of size up to N = M = 1,817.

Abstract This article presents a branch‐and‐cut algorithm for the Generalized Minimum Spanning Tree Problem (GMSTP). Given an undirected graph whose vertex set is partitioned into clusters, the GMSTP consists of determining a minimum‐cost tree including exactly one vertex per cluster. Applications of the GMSTP are encountered in telecommunications. An integer linear programming formulation is presented and new classes of valid inequalities are developed, several of which are proved to be facet‐defining. A branch‐and‐cut algorithm and a tabu search heuristic are developed. Extensive computational experiments show that instances involving up to 160 or 200 vertices can be solved to optimality, depending on whether edge costs are Euclidean or random. © 2004 Wiley Periodicals, Inc.

Abstract In the Ring Star Problem, the aim is to locate a simple cycle through a subset of vertices of a graph with the objective of minimizing the sum of two costs: a ring cost proportional to the length of the cycle and an assignment cost from the vertices not in the cycle to their closest vertex on the cycle. The problem has several applications in telecommunications network design and in rapid transit systems planning. It is an extension of the classical location–allocation problem introduced in the early 1960s, and closely related versions have been recently studied by several authors. This article formulates the problem as a mixed‐integer linear program and strengthens it with the introduction of several families of valid inequalities. These inequalities are shown to be facet‐defining and are used to develop a branch‐and‐cut algorithm. Computational results show that instances involving up to 300 vertices can be solved optimally using the proposed methodology. © 2004 Wiley Periodicals, Inc.

Abstract We consider two formulations for the uncapacitated hub location problem with single assignment (UHL), which use multicommodity flow variables. We project out the flow variables and determine some extreme rays of the projection cones. Then we investigate whether the corresponding inequalities define facets of the UHL polyhedron. We also present two families of facet defining inequalities that dominate some projection inequalities. Finally, we derive a family of valid inequalities that generalizes the facet defining inequalities and that can be separated in polynomial time. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 84–93 2004

Abstract The p‐Center problem consists of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which he or she is allocated. In this paper, we present a basic Variable Neighborhood Search and two Tabu Search heuristics for the p‐Center problem without the triangle inequality. Both proposed methods use the 1‐interchange (or vertex substitution) neighborhood structure. We show how this neighborhood can be used even more efficiently than for solving the p‐Median problem. Multistart 1‐interchange, Variable Neighborhood Search, Tabu Search, and a few early heuristics are compared on small‐ and large‐scale test problems from the literature. © 2003 Wiley Periodicals, Inc.

Abstract This article describes eight formulations for the Generalized Minimum Spanning Tree Problem (GMSTP). Relationships between the polytopes of their linear relaxations are established. It is shown that four of these polytopes are strictly included in the remaining ones. This analysis suggests which formulations should be preferred for the construction of a branch‐and‐cut algorithm and for the evaluation of heuristics. © 2002 John Wiley & Sons, Inc.

This paper analyzes a sampling method proposed by Fishman (1986) for computing the 2-terminal and global reliability of a network. It describes the sampling algorithm, and computation experiments on networks corresponding to a real situation as well as examples from the literature. A communication network is modeled by an undirected graph as a function of the set of vertices (the network nodes) and the set of edges (the links connecting pairs of vertices). Each edge is in 1 of 2 states (operational and failed). Failures are assumed to be statistically independent. A network is connected if the set of edges that are operational, forms a spanning connected subgraph (a subgraph containing at least 1 operational path between any 2 vertices). The problems of computing: (1) the 2-terminal network reliability (probability that between 2 given vertices there exists at least 1 operational path); and (2) the global network reliability (probability that the network is connected), are treated. This paper provides: (i) a detailed, clear exposition of the Fishman method, (ii) a complete description of the corresponding algorithm, (iii) its extension for computing global reliability (problem 2), and (iv) computational experiments on networks both new and in the literature. A Monte Carlo approach for these problems is fully justified by looking at their computational complexity. The exact computation of the network reliability (either 2-terminal or global) is a /spl npar/P-complete problem. If one looks for efficient algorithms, one must settle for approximations obtained by a heuristic procedure.

We begin by examining the dynamic behavior of a facility location such as a 1-median or a 1-center on a network when the parameters of the network are known functions of time. The parameters of the network include the lengths of the edges and the demands at the nodes. In our formulation, time is considered a discrete variable and it is assumed that the facility can only serve customers while it is stationary and that the demands at time t are fully satisfied before time t + 1. In particular, if x(t) denotes the location of the facility for t = 1, 2, … , the cost would be the sum of the costs of satisfying the demands at the various times plus the cost of moving the facility along its route implied by x(t). We also examine certain path (route) selection problems in dynamic networks. Recent past literature is surveyed. Various extensions including the multifacility versions of the above problems are studied. © 1999 John Wiley & Sons, Inc. Networks 34: 250–257, 1999

In this paper, network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will look at the problem of finding Pareto optimal locations and lexicographically optimal locations. It is shown that for Pareto optimal locations in undirected networks no node dominance result can be shown. Structural results as well as efficient algorithms for these multicriteria problems are developed. In the special case of a tree network, a generalization of Goldman's dominance algorithm for finding Pareto locations is presented. © 1999 John Wiley & Sons, Inc. Networks 33: 79–92, 1999

We study the two-level uncapacitated facility location (TUFL) problem. Given two types of facilities, which we call y-facilities and z-facilities, the problem is to decide which facilities of both types to open, and to which pair of y- and z-facilities each client should be assigned, in order to satisfy the demand at maximum profit. We first present two multi-commodity flow formulations of TUFL and investigate the relationship between these formulations and similar formulations of the one-level uncapacitated facility location (UFL) problem. In particular, we show that all nontrivial facets for UFL define facets for the two-level problem, and derive conditions when facets of TUFL are also facets for UFL. For both formulations of TUFL, we introduce new families of facets and valid inequalities and discuss the associated separation problems. We also characterize the extreme points of the LP-relaxation of the first formulation. While the LP-relaxation of a multi-commodity formulation provides good bounds in general, the number of variables and constraints grows rapidly with the size of the problem instance. An alternative model of TUFL is a single-commodity fixed-charge network flow problem. Rardin and Wolsey showed that by projecting a so-called multi-commodity extended formulation of fixed-charge network flow problems onto the space of flow variables used in the weaker flow formulation, a broad class of valid inequalities can be obtained. We discuss a subclass of these inequalities for TUFL that seems particularly useful for computational purposes.

We consider the problem of finding an optimal spanning tree with respect to objective functions which depend on the set of leaves of the tree. We address 18 different such problems and determine their computational complexity. Only a few of the problems examined have been given attention in the existing literature. © 1996 John Wiley & Sons, Inc.

Abstract The study of “optimally” locating on a network a single facility of a given total length in the form of a path or a tree was initiated by several authors. We extend these results to the problem of locating p (≥1) such facilities. We will consider “center”, “median”, “max eccentricity”, and “max distance sum” location type problems for p = 1 or p > 1, for general networks and for tree networks, whether a facility contains partial arcs or not, and whether a facility is path‐shaped or tree‐shaped. These cases lead to 64 problems. We will determine the algorithmic complexity of virtually all these problems. We conclude with a result that may be viewed as a generalization of the p‐Median theorem. © 1993 by John Wiley & Sons, Inc.

Given a network N(V, E) and a set of points Xp = {x1, …, xp} on N, we first present an algorithm for computing the Voronoi partition of N(V, E) into territories T(x1), …, T(xp). After describing two ways to measure the “size” of a territory, we introduce and discuss the more challenging problem of selecting Xp so that the maximum size among the resulting territories is as small as possible. For one especially natural way to measure the size of a territory, we show that this latter problem is NP-complete when p is part of the input, but that the problem can be solved in polynomial time for any fixed p. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Abstract We consider the location problem of an obnoxious facility with respect to a finite number of inhabitants, where the inhabitants have specified locations at vertices of a network N . A voting solution, called anti‐Condorcet point, is defined as a point of N such that no other point is farther from a strict majority of inhabitants. On a general network with an odd number of inhabitants, it is shown that there exists a finite set of points that contains all such solutions. An example shows that this result does not directly extend to an even number of inhabitants on a general network. In the special case of a tree network, one of the extreme vertices of a diameter is an anti‐Condorcet point, and a linear algorithm for finding it is presented. Finally, a bound on the maximum decrease of the total distance to the inhabitants is provided when an anti‐Condorcet point is preferred to a “maxisum” location.

Abstract The distance between an edge and a point of a network N is defined as the maximum distance from that point to any point on that edge. A continuous median of N is a point of N such that the sum of the distances between all edges and that point is minimum. A continuous p‐median is a set of p points of N such that the sum for all edges of the distance to the closest poit of that set is minimum. It is shown that the set of vertices and middle points of edges always contaisn a continuous p‐median. Therefore, powerful algorithms for the usual p‐median problem can be brought to bear. Moreover, algorithms requiring O(m2) operations in worst case for determining the set of all continuous and conditional continuous medians of N are obtained. A linear algorithm for the set of all continuous medians of a tree is also provided.

Abstract We prove that any continuous mapping from a network into itself has a fixed point if and only if the network is a tree‐network.