Search

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.

In communication networks, the routing decision process (distributed and online) remains decoupled from the network design process, i.e., resource installation and allocation planning process (centralized and offline). To reconcile both processes, we ambition to design a distributed optimization technique aware of distributed nature of the routing process by decomposing the optimization problem along same dimensions as (distributed) routing decision process. For this purpose, we generalize the capacitated multi-commodity capacitated fixed charge network design (MCND) class of problems by including different types of fixed costs (installation and maintenance costs) and variable costs (routing costs) but also variable traffic demands over multiple periods. However, conventional integer programming methods can typically solve only small to medium size instances. As an alternative, we propose a Lagrangian approach for computing a lower bound by relaxing the flow conservation constraints such that the Lagrangian subproblem itself decomposes by node. Though this approach yields one subproblem per network node, solving the Lagrangian dual by means of the bundle method remains a complex computational tasks. However, the approach is more robust than any LP solvers and it always returns some solutions. Instead, we proved that CPLEX, which uses the Dual Simplex algorithm, is not able to provide a solution for large instances.

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.

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.

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.

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.

We propose algorithms for pricing a transportation network in such a way that the profit generated by the customers is maximized. We model the transportation network as a subset of the plane and take into account the fact that the customers minimize their own transportation cost. The underlying theory is a two-player game model called Stackelberg games. We propose algorithms for the cases where the fare does and does not depend on the distance traveled, in the L1 or L2 metrics. In particular, we propose an O(n log n) algorithm for optimal pricing of a highway under the L2 metric, and an O(nk log n log 3 k) algorithm for orthogonally convex networks of complexity O(k) under the L1 metric.

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.

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.

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.

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.

The goal of generalized logical analysis is to model complex biological systems, especially so-called regulatory systems, such as genetic networks. This theory is mainly characterized by its capacity to find all the steady states of a given system and the functional positive and negative circuits, which generate multistationarity and a cycle in the state sequence graph, respectively. So far, this has been achieved by exhaustive enumeration, which severely limits the size of the systems that can be analysed. In this paper, we introduce a mathematical function, called image function, which allows the calculation of the value of the logical parameter associated with a logical variable depending on the state of the system. Thus the state table of the system is represented analytically. We then show how all steady states can be derived as solutions to a system of steady-state equations. Constraint programming, a recent method for solving constraint satisfaction problems, is applied for that purpose. To illustrate the potential of our approach, we present results from computer experiments carried out on very large randomly-generated systems (graphs) with hundreds, or even thousands, of interacting components, and show that these systems can be solved using moderate computing time. Moreover, we illustrate the approach through two published applications, one of which concerns the computation times of all steady states for a large genetic network.

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.

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.

In this paper network location problems with several objectives are discussed, where every single objective is a classical median objective function. We will lock 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 multi-criteria problems are developed. In the special case of a tree network a generalization of Goldman's dominance algorithm for finding Pareto locations is presented.

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.

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.

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.

Consider the problem of maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. This work is concerned with two new combinatorial formulations of this problem and provides a framework for deriving valid inequalities.

We consider a bilevel model where the leader wants to maximize revenues from a taxation scheme, while the follower rationally reacts to those tax levels. We focus our attention on the special case of a toll-setting problem defined on a multicommodity transportation network. We show that the general problem is NP-complete, while particular instances are polynomially solvable. Numerical examples are given.