ABSTRACT Given a directed graph, the Capacitated Steiner Arborescence Problem (CSAP) aims to determine the least‐cost connection from the root node to terminal nodes requiring a demand through Steiner nodes coming with a capacity, such that there is a unique path from the root to each terminal. This paper presents a new extended formulation of the CSAP, which extends the classical multicommodity flow formulation of CSAP by introducing the notion of cardinality of terminals served by arcs. We show that our extended formulation is stronger than the classical one. We present two classes of inequalities and separation heuristics exploiting the cardinality effect of the extended formulation. The first class is a generalization of cardinality induced Cover and (1, k )‐Configuration inequalities. The second class is called the p‐ Arc Cardinality matching inequalities and is based on matching the number of commodities flowing on active arcs across a cut‐set to its composite cardinality. The computational study clearly demonstrates the superiority of the extended formulation over the classical one. In particular, it consistently provides significantly tighter lower bounds at the root node. Moreover, for all hard instances, solving CSAP to optimality requires a number of branch‐and‐bound nodes that is several orders of magnitude larger under the classical formulation than under the extended one.

Abstract We consider polyhedral separation of sets as a possible tool in supervised classification. In particular, we focus on the optimization model introduced by Astorino and Gaudioso (J Optim Theory Appl 112(2):265–293, 2002) and adopt its reformulation in difference of convex (DC) form. We tackle the problem by adapting the algorithm for DC programming known as DCA. We present the results of the implementation of DCA on a number of benchmark classification datasets.

Abstract This paper is motivated by the case of a forwarder dealing with inland transportation planning, from a seaport, of inbound containers filled with pallets having different destinations in the land‐side. Although the forwarder is not the owner nor controls any vehicle, he is required to plan both the assignment of containers to intermediate depots, where the pallets are unpacked, and the assignment of pallets to the vehicles used for the distribution from depots to consignees. We present a mathematical model supporting the forwarder in this two‐echelon network to minimize assignment costs, while accounting for a balanced workload among all carriers involved in this distribution scheme. We discuss a tailor‐made implementation of the model in a realistic context and present a heuristic method to solve realistic‐sized instances. Our computational experiments confirm the viability of this method.

During the planning of communication networks, the routing decision process (distributed and online) often remains decoupled from the network design process, that is, resource installation and allocation‐planning process (centralized and offline). To reconcile both processes and take into account demand variability, we generalize the capacitated multicommodity fixed charge network design 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 of this problem. Two major difficulties are encountered when using commercial solvers to solve the associated mixed integer programs: (i) problems are large scale and even solving the linear relaxation of the problem can be challenging; and (ii) the solver hardly find good feasible solutions for medium to large scale 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, it always provides a lower bound on the optimal solution. Moreover, based on this relaxation, we propose a Lagrangian heuristic that makes the approach more robust than a black‐box usage of a Mixed Integer Programming (MIP) solver. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 110–123 2017

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.