This paper deals with the ring star problem that consists in designing a ring that pass through a central depot, and then assigning each non visited customer to a node of the ring. The objective is to minimize the total routing and assignment costs. A new chain based formulation is proposed. Valid inequalities are proposed … Read more
The Minimum Capacity s-t Cut Problem (Min Cut) is an intensively studied problem in combinatorial optimization. In this paper, we study Min Cut when arc capacities are uncertain but known to exist in pre-specified intervals. This framework can be used to model many real-world applications of Min Cut under data uncertainty such as in open-pit … Read more
In many path planning situations we would like to find a path of constrained Euclidean length in 2D that minimises a line integral. We call this the Continuous Length-Constrained Minimum Cost Path Problem (C-LCMCPP). Generally, this will be a non-convex optimization problem, for which continuous approaches only ensure locally optimal solutions. However, network discretisations yield … Read more
Conventional Lagrangean preprocessing for the network Weight Constrained Shortest Path Problem (WCSPP calculates lower bounds on the cost of using each node and edge in a feasible path using a single optimal Lagrange multiplier for the relaxation of the WCSPP. These lower bounds are used in conjunction with an upper bound to eliminate nodes and … Read more
This article presents the Multiple Objective Spanning Trees repository – MOST – Project. As the name suggests, the MOST Project intends to maintain a repository of tests for the MOST related problems, mainly addressing real-life situations. MOST is motivated by the scarcity of repositories for the problems in the referred field. This entails difficulty in … Read more
We study the Maximum Flow Network Interdiction Problem (MFNIP). We present two classes of polynomially separable valid inequalities for Cardinality MFNIP. We also prove the integrality gap of the LP relaxation of Wood’s (1993) integer program is not bounded by a constant factor, even when the LP relaxation is strengthened by our valid inequalities. Finally, … Read more
We investigate how to rapidly solve an online sequence of maximum flow problems. Sequences of maximum flow problems arise in a diverse collection of settings, including stochastic network programming and real-time scheduling of jobs on a two-processor computer. In this paper, we formulate solving an online sequence of maximum flow problems as the Maximum Flow … Read more
This short note on the Traffic Assignment Problem (TAP) provides the relevant information on test problems previously used in the literature to facilitate benchmarking CitationTechnical report, Ordecsys, 2008.ArticleDownload View PDF
This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be … Read more
We describe a specialized truncated-Newton primal-dual interior-point method that solves large scale network utility maximization problems, with concave utility functions, efficiently and reliably. Our method is not decentralized, but easily scales to problems with a million flows and links. We compare our method to a standard decentralized algorithm based on dual decomposition, and show by … Read more