ABSTRACT The vehicle routing problem with time windows is a well‐researched problem in literature. We study the 2‐index flow formulation for the problem and propose a relatively little‐used approach of polar duality/local cuts to compute new general valid inequalities for the problem. Our method of applying polar duality is quite distinct from and complimentary to an earlier attempt of applying the same idea to this problem and produces significantly better results on instances with tight time windows. On almost all 25‐customer Solomon instances with tight time windows, our approach is capable of producing very strong lower bounds that are close to 100% of the optimal solution within reasonable computing time. On larger instances too the lower bounds are significantly better than those reported in the literature. We also present a new version of the previously proposed ‐path inequalities that are easy to compute as well as effective. These inequalities also lead to a substantial improvement in lower bounds and solution times for some classes of instances. Computational tests performed on benchmark instances indicate significant improvement in computing time and decrease in the number of nodes in the branch‐and‐bound tree as compared to extant methods that employ the flow formulation for the problem.

ABSTRACT We study the problem of the optimal design of fiber‐to‐the‐home (FTTH) optical access networks. Given a network of nodes and edges rooted at an optical distribution point (ODP) with a given demand for optical fibers at a subset of these nodes, the problem entails finding the optimal placement of splitters, which allows multiple demand points to share a common fiber between ODP and a splitter, such that sum of the costs of the fiber cables and the splitters is minimized. Additionally, it needs to decide on the optimal selection of a cable type of appropriate capacity on each edge of the network to carry the required traffic. The existing literature on FTTH access network design typically assumes the same number of splitting stages for all demand points—specifically, one in case of a single splitting problem (SSP) or two in case of a double splitting problem (DSP). We provide a mixed‐integer programming (MIP) formulation of a mixed splitting problem (MSP), wherein some demand points can be served through one stage of splitting, whereas others can be served through two stages of splitting. We further propose several valid inequalities (VIs), with or without a pre‐specified template, to strengthen the formulation. Through our computational experiments on large instances, we demonstrate the efficacy of our proposed VIs, which help improve the lower bound of the problem from 79% to 86.9% of the MIP optimal cost, on average. For the special cases of SSP and DSP, we show that our formulation produces much tighter lower bounds compared to the existing formulation in the literature. On top of that, our proposed VIs are comparatively much more effective in tightening the bounds. Specifically, our proposed formulation with our VIs consistently outperforms that available in the literature, being as much as 500 times faster in some instances.

Abstract The symmetric vehicle routing problem with simultaneous pickup and deliveries is considered. The current state‐of‐the‐art method to solve this problem employs the idea of a no‐good cut. This article achieves an order of magnitude improvement in the computational time needed to solve difficult problem instances by generalizing the no‐good cuts and developing a way to generate improved no‐good cuts much earlier in a branch‐and‐bound tree. Results are reported on benchmark instances in literature and new difficult instances generated by the authors. Some polyhedral results are presented about the strength of the generalized no‐good cuts for a special case of the problem.

Abstract The team orienteering problem (TOP) requires a team of time‐constrained agents to maximize the total collected profit by serving a subset of given customers. The exact solution approaches for TOP in the literature have considered only the case of identical agents, even though the heterogeneity of the agents is of essence in many applications. The heuristic approaches, on the other hand, although providing good feasible solutions, do not offer any measure of solution quality, such as an optimality gap. In this study, we consider an extension of the conventional TOP in which the agents are allowed to be identical as well as completely nonidentical. We explore a Lagrangian relaxation based approach that simultaneously obtains tight upper and lower bounds on the optimal solution of the problem and, therefore, provides a measure of solution quality by way of duality gap. Our algorithm achieves an average gap of less than 2% within an average time of around 120 s across 135 randomly generated instances with up to 100 customers and five nonidentical agents. We also introduce a new set of valid symmetry breaking constraints that significantly improves the effectiveness of our formulation and Lagrangian implementation for the case of identical agents. For the three most difficult sets of benchmark instances for TOP with identical agents, our approach achieves upper bounds that are, on average, 1.08% above the best‐known solutions, and feasible solutions that are 0.35% below the best‐known solutions. The average time taken to solve these problems was about 115 s.

The problem of designing a spanning tree on an underlying graph to minimize the flow costs of a given set of traffic demands is considered. Several new classes of valid inequalities are developed for the problem. Tests on 10-node problem instances show that the addition of these inequalities results in integer solutions for a significant majority of the instances without requiring any branching. In the remaining cases, root gaps of less than 1% from the optimal solutions are realized. For 30-node problem instances, the inequalities substantially reduce the number of nodes explored in the branch-and-bound tree, resulting in significantly reduced computational times. Optimal solutions are reported for problems with 30 nodes, 60 edges, fully dense traffic matrices, and Euclidean distance-based flow costs. Problems with such flow costs are well-known to be a very difficult class of problems to solve. Using the inequalities substantially improves the performance of a variable-fixing heuristic. Some polyhedral issues relating to the strength of these inequalities are also discussed. The e-companion is available at https://doi.org/10.1287/ijoc.2018.0827 .

The article studies the problem of designing telecommunication networks using transmission facilities of two different capacities. The point‐to‐point communication demands are met by installing a mix of facilities of both capacities on the edges to minimize total cost. We consider 3‐partitions of the original graph which results in smaller 3‐node subproblems. The extreme points of this subproblem polyhedron are characterized using a set of propositions. A new approach for computing the facets of the 3‐node subproblem is introduced based on polarity theory. The facets of the subproblem are then translated back to those of the original problem using a generalized version of a previously known theorem. The approach has been tested on several randomly generated and real life networks. The computational results show that the new family of facets significantly strengthen the linear programming formulation and reduce the integrality gap. Also, there is a substantial reduction in the size of the branch‐and‐bound (B&B) tree if these facets are used. Problems as large as 37 nodes and 57 edges have been solved to optimality within a few minutes of computer time. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 11–32 2015

Abstract This article studies the polyhedral structure of the 4‐node network design problem (NDP). Using a theorem from the previous work of this author, the facets of the 4‐node NDP can be translated into facets of larger size problems. The knowledge of complete polyhedral description of the 4‐node NDP is important because it implies complete knowledge of 4‐partition‐based facets of larger NDPs. After reviewing the previously known facets of the 4‐node NDP, a new class of facets is derived. An enumerative methodology is presented for determining whether a given set of inequalities provides a complete polyhedral description. By implementing this methodology in a computer code, it is determined that the known facets of the 4‐node NDP indeed provide a complete polyhedral description of the problem. Working of the proof methodology is illustrated with examples, and the results of the computer enumeration are reported. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

This article addresses the problem of designing a multicommodity network using facilities of a fixed capacity to satisfy a given set of traffic demands. This problem (called the NDP) arises primarily in the design of high-capacity telecommunication networks. The k-partition of the NDP graph is introduced which results in a smaller k-node NDP. The main result of the article is a theorem, which shows that a facet inequality of the k-node problem translates into a facet of the original problem under a fairly mild condition, that is, the subgraph of each component of the k-partition be connected. This theorem is utilized to show that 2- and 3-partition-based inequalities identified by previous researchers yield families of facets for the original NDP. The structure of the 4-node NDP is explored to derive three different classes of valid inequalities and the conditions under which they are facet defining. The effectiveness of these inequalities is indicated by the computational experience on a 10-node example. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(3), 123–139, 2006