Highligths•We present matheuristics for multicommodity capacitated fixed charge network design.•The heuristics combine iterative linear programming and slope scaling methods.•We present extensive ...testing on benchmark instances from the literature.•We show that our matheuristics are competitive with state-of-the-art heuristics.
We present new matheuristics for the multicommodity capacitated fixed-charge network design problem (MCND). The matheuristics are based on combining iterative linear programming (ILP) methods and slope scaling (SS) heuristics. Each iteration alternates between solving a linear program obtained by adding pseudo-cuts and a restricted mixed-integer programming (MIP) model. The SS heuristic is used as a warm start to a state-of-the-art generic method that solves the restricted MIP model. The resulting ILP/SS matheuristics are compared against state-of-the-art heuristics for the MCND on a set of large-scale difficult instances. The computational results show that the approach is competitive: when performed for a time limit of 1 hour, it finds more best solutions than any other heuristic, using comparable running times; when performed for a time limit of 5 hours, it identifies an optimal solution for each instance for which an optimal solution is known and it is able to find new best solutions for some very hard instances.
We improve the mixed-integer programming formulation of the multicommodity capacitated fixed-charge network design problem by incorporating valid inequalities into a cutting-plane algorithm. We use ...five classes of known valid inequalities: the strong, cover, minimum cardinality, flow cover, and flow pack inequalities. The first class is particularly useful when a disaggregated representation of the commodities is chosen, and the last four are expressed in terms of network cut sets. We develop efficient separation and lifting procedures for these classes of inequalities. We present computational results on a large set of instances of various characteristics, allowing us to measure the impact of the different classes of valid inequalities on the quality of the lower bounds, in particular with respect to the representation of the commodities.
In this paper we present an exact algorithm for the capacitated location-routing problem (CLRP) based on cut-and-column generation. The CLRP is formulated as a set-partitioning problem that also ...inherits all of the known valid inequalities for the flow formulations of the CLRP. We introduce five new families of inequalities that are shown to dominate some of the cuts from the two-index formulation. The problem is solved by column generation, where the subproblem consists in finding a shortest path of minimum reduced cost under capacity constraints. We first use the two-index formulation for enumerating all of the possible subsets of depot locations that could lead to an optimal solution of cost less than or equal to a given upper bound. For each of these subsets, the corresponding multiple depot vehicle routing problem is then solved by means of column generation. The results show that we can improve the bounds found in the literature, solve to optimality some previously open instances, and improve the upper bounds on some other instances.
In this paper, we present an approach and an algorithm aimed at minimising the energy consumption of enterprise Wireless Local Area Networks (WLANs) during periods of low user activity. We act on two ...network management aspects: powering off some Access Points (APs), and choosing the level of transmission power of each AP. An efficient technique to allocate the user terminals to the various APs is the key to achieving this goal. The approach has been formulated as an integer programming problem with nonlinear constraints, which comes from a general but accurate characterisation of the WLAN. This general problem formulation has two implications: the formulation is widely applicable, but the nonlinearity makes it NP-hard. To solve this problem to optimality, we devised an exact algorithm based on a customised version of Benders' decomposition method. The computational results proved the ability to obtain remarkable power savings. In addition, the good performance of our algorithm in terms of solving times paves the way for its future deployment in real WLANs.
We consider a general network design model for which we compare theoretically different Lagrangian relaxations. Fairly general assumptions on the model are proposed, allowing us to generalize results ...obtained for special cases. The concepts are illustrated on two classical network design problems, the fixed-charge multicommodity capacitated network design problem and the single-source capacitated facility location problem. We also show that, even though our assumptions might not be verified, it is often possible to derive extended reformulations that satisfy them. We study the impact of such extended reformulations on Lagrangian relaxations, by focusing on two particular cases, the hop-constrained fixed-charge multicommodity capacitated network design problem and the multicommodity capacitated network design problem.
We present a branch-and-price-and-cut algorithm for solving large-scale instances of the multicommodity capacitated fixed-charge network design problem. We assume good feasible solutions are already ...known and we focus on an efficient algorithm for proving the optimality of the solutions. The restricted master problem solved at each column generation iteration is obtained directly from the compact arc-based model by considering only a subset of the commodity flow variables. The pricing subproblem corresponds to a Lagrangian relaxation of the flow conservation and capacity constraints, leaving in the Lagrangian subproblem only the strong inequalities. The column generation procedure is completed by a cut generation step based on strong inequalities. The resulting column-and-row generation procedure is embedded within an enumerative scheme. Computational experiments on a large set of randomly generated instances are presented and analyzed.
We study a generic minimization problem with separable nonconvex piecewise linear costs, showing that the linear programming (LP) relaxation of three textbook mixed-integer programming formulations ...each approximates the cost function by its lower convex envelope. We also show a relationship between this result and classical Lagrangian duality theory.
To efficiently derive bounds for large-scale instances of the capacitated fixed-charge network design problem, Lagrangian relaxations appear promising. This paper presents the results of ...comprehensive experiments aimed at calibrating and comparing bundle and subgradient methods applied to the optimization of Lagrangian duals arising from two Lagrangian relaxations. This study substantiates the fact that bundle methods appear superior to subgradient approches because they converge faster and are more robust relative to different relaxations, problem characteristics, and selection of the initial parameter values. It also demonstrates that effective lower bounds may be computed efficiently for large-scale instances of the capacitated fixed-charge network design problem. Indeed, in a fraction of the time required by a standard simplex approach to solve the linear programming relaxation, the methods we present attain very high-quality solutions.
La relaxation lagrangienne apparaı̂t comme une technique prometteuse pour générer efficacement des bornes de qualité pour des exemplaires de grande taille du problème de conception de réseau avec coût fixe et capacité. Cet article présente les résultats d'expériences visant à comparer les méthodes de sous-gradients et de faisceaux, appliquées à l'optimisation des duaux lagrangiens issus de deux relaxations lagrangiennes. Cette étude démontre que les méthodes de faisceaux semblent supérieures aux méthodes de sous-gradients puisqu'elles convergent plus rapidement et sont plus robustes. Cet article montre également que des bornes inférieures de qualité pour des exemplaires de grande taille du problème de conception de réseau avec coût fixe et capacité peuvent être calculées de manière efficace. En effet, les approches de relaxation lagrangienne obtiennent des bornes de très grande qualité en une fraction du temps requis par des méthodes de type simplexe.
We consider the piecewise linear multicommodity network flow problem with the addition of a constraint specifying that the total flow on each arc must be an integer. This problem has applications in ...transportation and logistics, where total flows might represent vehicles or containers filled with different products. We introduce formulations that exploit this integrality constraint by adapting to our problem a technique known as discretization that has been used to derive mixed-integer programming models for several combinatorial optimization problems. We enhance the discretized models either by adding valid inequalities derived from cut-set inequalities or by using flow disaggregation techniques. Since the size of the formulations derived from discretization and flow disaggregation rapidly increases with problem dimensions, we develop an efficient and effective Lagrangian relaxation method to compute lower and upper bounds. We perform computational results on a large set of randomly generated instances that allow us to compare the relative efficiency of the different modeling alternatives (flow disaggregation plus addition of cut-set inequalities with or without discretization), when used within the Lagrangian relaxation approach.
PDF
