Abstract This work focuses on the capacitated dispersion problem for which we study several mathematical formulations in different spaces using variables associated with nodes, edges, and costs. The relationships among the presented formulations are investigated by comparing the projections of the feasible sets of the LP relaxations onto the subspace of natural variables. These formulations are then strengthened with families of valid inequalities and variable‐fixing procedures. The separation problems associated with the valid inequalities that are exponential in number are shown to be polynomially solvable by reducing them to longest path problems in acyclic graphs. The dual bounds obtained from stronger but larger formulations are used to improve the strength of weaker but smaller formulations. Several sets of computational experiments are conducted to illustrate the usefulness of the findings, as well as the aptness of the formulations for different types of instances.

This paper presents an exact algorithm for the team formation problem, in which the aim is, given a project and its required skills, to construct a capable team that can communicate and collaborate effectively. This combinatorial optimization problem is modeled as a quadratic set covering problem. The study provides a novel branch-and-bound algorithm where a reformulation of the problem is relaxed so that it decomposes into a series of linear set covering problems, and the relaxed constraints are imposed through branching. The algorithm is able to solve instances that are intractable for commercial solvers. The study illustrates an efficient usage of algorithmic methods and modeling techniques for an operations research problem. It contributes to the field of computational optimization by proposing a new application and a new algorithm to solve a quadratic version of a classical combinatorial optimization problem.

This article considers the problem of designing a two‐level network where the upper level consists of a backbone ring network connecting the so‐called hub nodes, and the lower level is formed by access ring networks that connect the non‐hub nodes to the hub nodes. There is a fixed cost for each type of link, and a facility opening cost associated to each hub. The number of nodes in each access ring is bounded, and the number of access rings connected to a hub is limited to , thus resulting in a ring/ ‐rings topology. The aim is to decide the hubs to open and to design the backbone and access rings to minimize the installation cost. We propose a mathematical model, give valid inequalities, and describe a branch‐and‐cut algorithm to solve the problem. Computational results show the algorithm is able to find optimal solutions on instances involving up to 40 nodes within a reasonable time. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 130–140 2016

The motivation behind this study is the essential need for survivability in the telecommunications networks. An optical signal should find its destination even if the network experiences an occasional fiber cut. We consider the design of a two-level survivable telecommunications network. Terminals compiling the access layer communicate through hubs forming the backbone layer. To hedge against single link failures in the network, we require the backbone subgraph to be two-edge connected and the terminal nodes to connect to the backbone layer in a dual-homed fashion, i.e., at two distinct hubs. The underlying design problem partitions a given set of nodes into hubs and terminals, chooses a set of connections between the hubs such that the resulting backbone network is two-edge connected, and for each terminal chooses two hubs to provide the dual-homing backbone access. All of these decisions are jointly made based on some cost considerations. We give alternative formulations using cut inequalities, compare these formulations, provide a polyhedral analysis of the small-sized formulation, describe valid inequalities, study the associated separation problems, and design variable fixing rules. All of these findings are then utilized in devising an efficient branch-and-cut algorithm to solve this network design problem.

We study the lot-sizing problem with piecewise concave production costs and concave holding costs. This problem is a generalization of the lot-sizing problem with quantity discounts, minimum order quantities, capacities, overloading, subcontracting or a combination of these. We develop a dynamic programming algorithm to solve this problem and answer an open question in the literature: we show that the problem is polynomially solvable when the breakpoints of the production cost function are time invariant and the number of breakpoints is fixed. For the special cases with capacities and subcontracting, the time complexity of our algorithm is as good as the complexity of algorithms available in the literature. We report the results of a computational experiment where the dynamic programming is able to solve instances that are hard for a mixed-integer programming solver. We enhance the mixed-integer programming formulation with valid inequalities based on mixing sets and use a cut-and-branch algorithm to compute better bounds. We propose a state space reduction–based heuristic algorithm for large instances and show that the solutions are of good quality by comparing them with the bounds obtained from the cut-and-branch.

Abstract The survivable hierarchical telecommunications network design problem consists of locating concentrators, assigning user nodes to concentrators, and linking concentrators in a reliable backbone network. In this article, we study this problem when the backbone is 2‐edge connected and when user nodes are linked to concentrators by a point‐to‐point access network. We formulate this problem as an integer linear program and present a facial study of the associated polytope. We describe valid inequalities and give sufficient conditions for these inequalities to be facet defining. We investigate the computational complexity of the corresponding separation problems. We propose some reduction operations to speed up the separation procedures. Finally, we devise a branch‐and‐cut algorithm based on these results and present the outcome of a computational study. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

We consider the network loading problem (NLP) under a polyhedral uncertainty description of traffic demands. After giving a compact multicommodity flow formulation of the problem, we state a decomposition property obtained from projecting out the flow variables. This property considerably simplifies the resulting polyhedral analysis and computations by doing away with metric inequalities. Then we focus on a specific choice of the uncertainty description, called the “hose model,” which specifies aggregate traffic upper bounds for selected endpoints of the network. We study the polyhedral aspects of the NLP under hose demand uncertainty and use the results as the basis of an efficient branch-and-cut algorithm. The results of extensive computational experiments on well-known network design instances are reported.

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

We study the integer knapsack cover polyhedron which is the convex hull of the set of vectors $x\in \mathbb{Z}_{+}^{n}$ that satisfy $C^{T}x\geq b$, with $C\in \mathbb{Z}_{++}^{n}$ and $b\in \mathbb{Z}_{++}$. We present some general results about the nontrivial facet-defining inequalities. Then we derive specific families of valid inequalities, namely, rounding, residual capacity, and lifted rounding inequalities, and identify cases where they define facets. We also study some known families of valid inequalities called 2-partition inequalities and improve them using sequence-independent lifting.

We consider the problem of installing a two-level telecommunication network. Terminal nodes communicate with each other through hubs. Hubs can be installed on terminal nodes and they are interconnected by a complete network. Each terminal is connected directly to a hub node. Integer amounts of capacity units are installed on the arcs between hub pairs and terminals and their hubs. The aim is to minimize the cost of installing hubs and capacity units on arcs. We present valid and facet defining inequalities for the polyhedron associated with this problem.

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