Search

SCOPUS: ar.j; International audience; This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly NP -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.

Intra-domain routing protocols are based on shortest path first (SPF) routing, where shortest paths arecalculated between each pair of nodes (routers) using pre-assigned link weights, also referred to as linkmetric. These link weights can be modified by network administrators in accordance with the routingpolicies of the network operator. The operator’s objective is usually to minimize traffic congestion orminimize total routing cost subject to the traffic demands and the protocol constraints. However,determining a link weights combination that best suits the network operator’s requirements is a difficulttask.This paper provides a survey of meta-heuristic approaches to traffic engineering, focusing on local searchapproaches and extensions to the basic problem taking into account changing demands and robustnessissues with respect to network failures., FLWIN, info:eu-repo/semantics/published

SCOPUS: cp.j; International audience; no abstract

Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bi-layer networks, comparing with Knippel's previous results.

Similarity and diversity among individuals of the same species are expressed in small DNA variations called Single Nucleotide Polymorphism. The knowledge of SNP phase gives rise to the haplotyping problem that in the parsimonious version states to infer the minimum number of haplotypes from a given set of genotype data. ILP technique represents a good resolution strategy for this interesting combinatorial problem whose main limit lies in its NP-hardness. In this paper we present a new polynomial model for the haplotyping inference by parsimony problem characterized by the original use of a maximum formulation jointly with a good heuristic solution. This approach showed to be a robust basic model that can be used as starting point for more sophisticated ILP techniques like branch and cut and polyhedral studies.

Open Shortest Path First (OSPF) is one of the most commonly used intra-domain internet routing protocol. Traffic flow is routed along shortest paths, splitting flow evenly at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to the physical lengths of the links, but often the main goal is to avoid congestion, i.e. overloading of links, and the standard heuristic recommended by Cisco (a major router vendor) is to make the weight of a link inversely proportional to its capacity. We study the problem of optimizing OSPF weights for a given a set of projected demands so as to avoid congestion. We show this problem is NP-hard, even for approximation, and propose a local search heuristic to solve it. We also provide worst-case results about the performance of OSPF routing vs. an optimal multi-commodity flow routing. Our numerical experiments compare the results obtained with our local search heuristic to the optimal multi-commodity flow routing, as well as simple and commonly used heuristics for setting the weights. Experiments were done with a proposed next-generation AT&T WorldNet backbone as well as synthetic internetworks.

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

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 Halldorsson 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.

The combined network design and (distributed)traffic routing problem can be formulated as a large-scale multi-period mixed integer optimization problem. This problem com-bines network design decisions and routing decisions, with time-dependent demands. A compact formulation for this problem,based on the aggregation of flows by destination, was proposedin [1]. They observed that the resolution on realistic instancesbecomes intractable and unscalable with state-of-the-art solversdue to the weak linear programming bound provided by theformulation. In this paper, we consider an extended formulationwhere flows are decomposed by origin-destination pairs, whilekeeping the requirement of destination-based routing. The qualityof the extended formulation and the computational time neededto solve it are evaluated on a representative set of networktopologies and traffic demands, and compared to results obtainedwith the base formulation of [1]. The extended formulation canthen be considered for more efficient resolution methods involvingdecomposition and cutting planes approaches., info:eu-repo/semantics/published

The capacitated Fixed-Charge Network Design (FCND) problem deals with the simultaneous optimization of capacity installation and routing of traffic, where a fixed cost is paid for opening a link and a linear routing cost is paid for sending traffic flow on a link. The routing decision must be performed such that flows remain bounded by the installed capacities. This problem appears as a particular case of the combined network design and traffic flow routing problem with time-dependent demands as developed in this paper. This general problem can be formulated as a multi-period mixed integer optimization problem. A compact formulation based on the aggregation of flows by destination and an extended formulation, where flows are decomposed by origin-destination pairs while keeping the requirement of destination-based routing, have been proposed in [1] and [2], respectively. As these computational improvements enable to progressively overcome the limit of solving such problem when the network size and number of periods increases, we propose an extended model that accounts for different patterns of failures affecting installed arcs over time. The latter lead to consider time-variable link maintenance cost function as part of our generalized formulation. We also analyze the quality of the results for the proposed formulation with different link maintenance cost functions with the objective to derive the best arc replacement strategy.

Language of publication: en; International audience; no abstract

We consider networks in which a cost is associated with each arc or edge and a transition cost is associated with each node. This last cost is related to the presence of two technologies on the network and is incurred only when a flow enters and leaves the corresponding node on arcs of different types. The problem we consider consists in finding two node disjoint paths with minimum total cost. We show that it is strongly NP-complete. Then we propose two heuristics, study their worst case behavior, provide a lower bounding procedure based on Lagrangean relaxation, and finally embed those elements in a branch and bound procedure.

We investigate the Robust Deviation Balanced Minimum Evolution Problem (RDBMEP), a combinatorial optimization problem that arises in computational biology when the evolutionary distances from taxa are uncertain and varying inside intervals. By exploiting some fundamental properties of the objective function, we present a mixed integer programming model to exactly solve instances of the RDBMEP and discuss the biological impact of uncertainty on the solutions to the problem. Our results give perspective on the mathematics of the RDBMEP and suggest new directions to tackle phylogeny estimation problems affected by uncertainty. (c) 2013 Elsevier B.V. All rights reserved.

SCOPUS: ar.j; International audience; Throughout the last decade, extensive deployment of popular intra-domain routing protocols such as open shortest path first (OSPF) and intermediate system–intermediate system (IS-IS), has drawn an ever increasing attention to internet traffic engineering. This paper reviews optimization techniques that have been deployed for managing intra-domain routing in networks operated with shortest path routing protocols, and the state-of-the-art research that has been carried out in this direction.

This paper is devoted to pricing optimization problems which can be modeled as bilevel programs. We present the main concepts, models and solution methods for this class of optimization problems.

The desire for configuring well-managed open shortest path first (OSPF) routes to handle the communication needs in the contemporary business world with larger networks and changing service requirements has opened the way to use traffic engineering tools with the OSPF protocol. Moreover, anticipating possible shifts in expected traffic demands while using network resources efficiently has started to gain more attention. We take these two crucial issues into consideration and study the weight setting problem for OSPF routing problem with polyhedral demands. Our motivation is to optimize the link weight metric such that the minimum cost routing uses shortest paths with equal cost multipath splitting and the routing decisions are robust to possible fluctuations in demands. In addition to a compact mixed integer programming model, we provide an algorithmic approach with two variations to tackle the problem. We present several test results for these two strategies and discuss whether we could make our weight-managed OSPF comparable to unconstrained routing under polyhedral demand uncertainty. © 2012 Wiley Periodicals, Inc. NETWORKS, 2012 © 2012 Wiley Periodicals, Inc.

We investigate the Parsimonious Loss of Heterozygosity Problem (PLOHP) , i.e., the problem of partitioning suspected polymorphisms of a set of individuals into the minimum number of deletion areas. We generalize the work of Halldorsson et al. ' by showing how one can incorporate prior knowledge about the location of deletion; we prove the general $\mathcal{NP}$ -hardness of the problem and we provide a state-of-the-art mixed integer programming formulation and a number of possible strengthening valid inequalities able to exactly solve practical instances of the PLHOP containing up to 9.000 individuals and 3000 SNPs within 12 hours compute time.

In this paper we present two algorithms for a machine allocation problem occurring in manufacturing systems. For the two algorithms presented we prove worst-case performance ratios of 2 and 3/2, respectively. The machine allocation problem we consider is a general convex resource allocation problem, which makes the algorithms applicable to a variety of resource allocation problems. Numerical results are presented for two real-life manufacturing systems.

SCOPUS: cp.k; International audience; We consider the problem of designing a network for hazardous material transportation where the government can decide which roads have to be forbidden to hazmats and the carriers choose the routes on the network. We assume that the government is interested in minimizing the overall risk of the shipments whereas the carriers minimize the route costs. In spite of the rich literature on hazmat transportation and of the relevance of this network design problem, it has received little attention and only quite recently. In this work we prove that the version of the hazmat transport network design problem where a subset of arcs can be forbidden is NP-hard even when a single commodity has to be shipped. We propose a bilevel integer programming formulation that guarantees solution stability and we derive a (single-level) mixed integer linear programming formulation that can be solved in reasonable time with a state-of-the-art solver. © 2011 Springer-Verlag.

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 © 2011 Wiley Periodicals, Inc.

Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework.

SCOPUS: cp.k; International audience; We present two complete integer programming formulations for the ring spur assignment problem. This problem arises in the design of next generation telecommunications networks. We analyse and compare the formulations in terms of compactness, the resulting LP bound and results from a branch and cut implementation. We present our conclusions with computational results. © 2011 Springer-Verlag.

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 © 2011 Wiley Periodicals, Inc.

SCOPUS: ar.j; International audience; We show how we can linearize individual probabilistic linear constraints with binary variables when all coefficients are independently distributed according to either N(μi,λμi), for some λ>0 and μi>0, or Γ(ki,θ) for some θ>0 and ki>0. The constraint can also be linearized when the coefficients are independent and identically distributed and either positive or strictly stable random variables. © 2010 Elsevier B.V. All rights reserved.

In this study, we establish a parallel between two classes of pricing problems that have attracted the attention of researchers in marketing, theoretical computer science and operations research, each community addressing issues from its own vantage point. More precisely, we contrast the problems of pricing a network or a product line, in order to achieve maximum revenue, given that customers maximize their individual utility. Throughout the article, we focus on problems that can be formulated as mixed-integer programs.

International audience; We consider two (0, 1)-linear programming formulations of the graph (vertex-) coloring problem, in which variables are associated with stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in which constraints express that two stable sets cannot have a common vertex, and large stable sets are preferred in the objective function. We identify facets with small coefficients for the polytopes associated with both formulations. We show by computational experiments that both formulations are about equally efficient when used in a branch-and-price algorithm. Next we propose some preprocessing, and show that it can substantially speed up the algorithm, if it is applied at each node of the enumeration tree. Finally we describe a cutting plane procedure for the set covering formulation, which often reduces the size of the enumeration tree.

Language of publication: en; International audience; no abstract

T = (V, E) is a tree with nonnegative weights associated with each of its vertices. A fleet of vehicles of capacity Q is located at the depot represented by vertex v1. The Capacitated Vehicle Routing Problem on Trees (TCVRP) consists of determining vehicle collection routes starting and ending at the depot such that: the weight associated with any given vertex is collected by exactly one vehicle; the sum of all weights collected by a vehicle does not exceed Q; a linear combination of the number of vehicles and of the total distance traveled by these vehicles is minimized. The TCVRP is shown to be NP-hard. This paper presents lower bounds for the TCVRP based on the solutions of associated bin packing problems. We develop a linear time heuristic (upper bound) procedure and present a bound on its worst case performance. These lower and upper bounds are then embedded in an enumerative algorithm. Numerical results follow.

Consider the problem of maximizing the toll revenue collected on a multi-commodity transportation network. This fits a bilevel framework where a leader sets tolls, while users respond by selecting cheapest paths to their destination. We propose novel formulations of the problem, together with valid inequalities yielding improved algorithms.

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.

The simple plant location problem with order, a generalization of the well-known simple plant location problem where preferences for the customers are considered, is studied here. Some valid inequalities are introduced as well as a basic preprocessing analysis. A computational study shows the efficiency of this approach.

Link weight optimization is shown to be a key issue in engineering of IGPs using shortest path first routing. The IGP weight optimization problem seeks a weight array resulting an optimal load distribution in the network based on the topology information and a traffic demand matrix. Several solution methods for various kinds of this problem have been proposed in the literature. However, the interaction of IGP with BGP is generally neglected in these studies. In reality, the optimized weights may not perform as well as expected, since updated link weights can cause shifts in the traffic demand matrix by hot-potato routing in the decision process of BGP. Hot-potato routing occurs when BGP decides the egress router for a destination prefix according to the IGP lengths. This paper mainly investigates the possible degradation of an IGP weight optimization tool due to hot-potato routing under a worst-case example and some experiments which are carried out by using an open source traffic engineering toolbox. Furthermore, it proposes an approach based on robust optimization to overcome the negative effect of hot-potato routing and analyzes its performance

The concentrator location problem is to choose a subset of a given terminal set to install concentrators and to assign each remaining terminal node to a concentrator to minimize the cost of installation and assignment. The concentrators may have capacity constraints. We study the polyhedral properties of concentrator location problems with different capacity structures. We develop a branch and cut algorithm and present computational results.

The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. The aim of this paper is to investigate polyhedral properties of these problems and to develop a branch and cut algorithm based on these results.

The Plant-Cycle Location Problem (PCLP) is defined on a graph G=(I∪J, E), where I is the set of customers and J is the set of plants. Each customer must be served by one plant, and the plant must be opened to serve customers. The number of customers that a plant can serve is limited. There is a cost of opening a plant, and of serving a customer from an open plant. All customers served by a plant are in a cycle containing the plant, and there is a routing cost associated to each edge of the cycle. The PCLP consists in determining which plants to open, the assignment of customers to plants, and the cycles containing each open plant and its customers, minimizing the total cost. It is an NP-hard optimization problem arising in routing and telecommunications. In this article, the PCLP is formulated as an integer linear program, a branch-and-cut algorithm is developed, and computational results on real-world data and randomly generated instances are presented. The proposed approach is able to find optimal solutions of random instances with up to 100 customers and 100 potential plants, and of instances on real-world data with up to 120 customers and 16 potential plants.

We study the problem of designing at minimum cost a two-connected network such that each edge belongs to a cycle using at most K edges. This problem is a particular case of the two-connected networks with bounded meshes problem studied by Fortz, Labbe and Maffioli (Operations Research, vol. 48, no. 6, pp. 866–877, 2000). In this paper, we compute a lower bound on the number of edges in a feasible solution, we show that the problem is strongly NP-complete for any fixed K, and we derive a new class of facet defining inequalities. Numerical results obtained with a branch-and-cut algorithm using these inequalities show their effectiveness for solving the problem.

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.

We study the polyhedron associated with a network design problem which consists in determining at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “ring”) does not exceed a given length K.¶We present here a new formulation of the problem and derive facet results for different classes of valid inequalities. We study the separation problems associated to these inequalities and their integration in a Branch-and-Cut algorithm, and provide extensive computational results., SCOPUS: ar.j, info:eu-repo/semantics/published

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.

Language of publication: en; International audience; no abstract

The Uncapacitated Facility Location Problem with Client Matching (LCM) is an extension of the Uncapacitated Facility Location Problem (UFLP), where two clients allocated to a facility can be matched. As in the UFLP, facilities can be opened at any of m predefined locations with given fixed costs, and n clients have to be allocated to the open facilities. In classical location models, the allocation cost is the distance between a client and an open facility. In the LCM, the allocation cost is either the cost of a return trip between the facility and the client, or the length of a tour containing the facility and two clients. The similarities of the LCM with the classical UFLP and the matching problem are exploited to derive valid inequalities, optimality cuts, and polyhedral results. A greedy heuristic and a branch-and-cut algorithm are developed, and several separation procedures are described. Computational experiments confirm the efficiency of the proposed approach.

Open shortest path first (OSPF) is the most commonly used intra-domain Internet routing protocol. Traffic flow is routed along shortest paths, splitting flow at nodes where several outgoing links are on shortest paths to the destination. The weights of the links, and thereby the shortest path routes, can be changed by the network operator. The weights could be set proportional to their physical distances, but often the main goal is to avoid congestion, i.e., overloading of links, and the standard heuristic recommended by Cisco is to make the weight of a link inversely proportional to its capacity. Our starting point was a proposed AT&T WorldNet backbone with demands projected from previous measurements. The desire was to optimize the weight setting based on the projected demands. We showed that optimizing the weight settings for a given set of demands is NP-hard, so we resorted to a local search heuristic. Surprisingly it turned out that for the proposed AT&T WorldNet backbone, we found weight settings that performed within a few percent from that of the optimal general routing where the flow for each demand is optimally distributed over all paths between source and destination. This contrasts the common belief that OSPF routing leads to congestion and it shows that for the network and demand matrix studied we cannot get a substantially better load balancing by switching to the proposed more flexible multi-protocol label switching (MPLS) technologies. Our techniques were also tested on synthetic internetworks, based on a model of Zegura et al., (1996), for which we did not always get quite as close to the optimal general routing.

The optimal setting of taxes or subsidies on goods and services can be naturally modelled as a bilinear bilevel program. We analyze this class of hierarchical problems both from the theoretical and algorithmical points of view, devoting special attention to the problem of setting profit-maximizing tolls on a transportation network.

This paper is devoted to some of the most important discrete location models. The Uncapacitated Facility Location Problem is first considered. Its properties, the most efficient exact method and some heuristics are presented. Then, extensions and related models proposed recently are reviewed.

Traditional network location theory is concerned with the optimal location of facilities which can be considered as single points (emergency medical service stations, switching centers in communication networks, bus stops, mail boxes, etc.) However, in many real problems the facility to be located is too large to be modeled as a point. Examples of such problems include the location of pipelines and high speed train lines, the design of emergency routes, newspaper delivery routes, subway lines, etc. We will refer to this kind of facilities as extensive facilities or structures, and they may have the shape of a path, a tree, a cycle or a more general subgraph.

We study the problem of designing at minimum cost a two-connected network such that the shortest cycle to which each edge belongs (a “mesh”) does not exceed a given length K. This problem arises in the design of fiber optics based backbone telecommunication networks. To keep closer to reality, we assume the triangle inequality holds. A Branch-and-Cut approach to this problem is presented for which we introduce several families of valid inequalities and discuss the corresponding separation algorithms. Since the size of the problems solvable to optimality by this approach is too small, we also develop some heuristics.The computational performances of these exact and approximate methods are then thoroughly assessed both on randomly generated instances as well as instances suggested by real applications.

In this note we give a short and easy proof of the equivalence of Hakimi's one-median problem and the k-server-facility-loss median problem as discussed by Chiu and Larson in Computer and Operation Research. The proof makes only use of a stochastic monotonicity result for birth and death processes and the insensitivity of the M/G/k/k loss model.

The continuous radius of a network N is the minimum for all points of N (i.e., vertices or points on edges) of the maximum distance from x to any other point y of N.Any point of N remote from any other point of a distance not exceeding the continuous radius is a continuous center. The continuous center set of N is the union of all continuous centers.Properties of the continuous center set are studied and an algorithm is given to determine it, which requires O(m2log m) time and O(m) space in the worst case, m being the number of edges of N.

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.

We examine the feasibility polyhedron of the uncapacitated hub location problem (UHL) with multiple allocation, which has applications in the fields of air passenger and cargo transportation, telecommunication and postal delivery services. In particular we determine the dimension and derive some classes of facets for this polyhedron. We develop a general rule about lifting facets from the uncapacitated facility location problem to UHL. Using this lifting procedure we derive a new class of facets for UHL which dominates the inequalities in the original formulation. Thus we obtain a new formulation of the UHL whose constraints are all facet-defining.