A conic quadratic formulation for a class of convex congestion functions in network flow problems

Date

2011-06-01

Author

Gürel, Sinan

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

215
views

0
downloads

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.

Subject Keywords

Management Science and Operations Research, Modelling and Simulation, Information Systems and Management

URI

https://hdl.handle.net/11511/41100

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

DOI

https://doi.org/10.1016/j.ejor.2010.12.018

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A NEW HEURISTIC APPROACH FOR THE MULTIITEM DYNAMIC LOT-SIZING PROBLEM KIRCA, O; KOKTEN, M (Elsevier BV, 1994-06-09) In this paper a framework for a new heuristic approach for solving the single level multi-item capacitated dynamic lot sizing problem is presented. The approach uses an iterative item-by-item strategy for generating solutions to the problem. In each iteration a set of items are scheduled over the planning horizon and the procedure terminates when all items are scheduled. An algorithm that implements this approach is developed in which in each iteration a single item is selected and scheduled over the planni...
A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems Chung, Chia-Shin; Flynn, James; Kırca, Ömer (Elsevier BV, 2006-10-01) The m-machine permutation flowshop problem with the total tardiness objective is a common scheduling problem, which is known to be NP-hard. Here, we develop a branch and bound algorithm to solve this problem. Our algorithm incorporates a machine-based lower bound and a dominance test for pruning nodes. We undertake a numerical study that evaluates our algorithm and compares it with the best alternative existing algorithm. Extensive computational experiments indicate that our algorithm performs better and ca...
Approximate queueing models for capacitated multi-stage inventory systems under base-stock control Avşar, Zeynep Müge (Elsevier BV, 2014-07-01) A queueing analysis is presented for base-stock controlled multi-stage production-inventory systems with capacity constraints. The exact queueing model is approximated by replacing some state-dependent conditional probabilities (that are used to express the transition rates) by constants. Two recursive algorithms (each with several variants) are developed for analysis of the steady-state performance. It is analytically shown that one of these algorithms is equivalent to the existing approximations given in ...
A flexible flowshop problem with total flow time minimization Azizoğlu, Meral; Kondakci, S (Elsevier BV, 2001-08-01) In this study, we consider total flow time problem in a flexible flowshop environment. We develop a branch and bound algorithm to find the optimal schedule. The efficiency of the algorithm is enhanced by upper and lower bounds and a dominance criterion. Computational experience reveals that the algorithm solves moderate sized problems in reasonable solution times.
An efficient algorithm for the capacitated single item dynamic lot size problem Kırca, Ö. (Elsevier BV, 1990-3) A dynamic programming based algorithm is developed for the single item lot size problem with concave costs and arbitrary capacities. By making use of the extreme point properties of the problem, first the set of all feasible cumulative production levels that may occur in an optimal solution is generated. In the second stage, a dynamic programming procedure is carried out over this set. The worst case computational effort is equal to that of the standard dynamic programming approach but extensive computation...

Citation Formats

S. Gürel, “A conic quadratic formulation for a class of convex congestion functions in network flow problems,” EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, pp. 252–262, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41100.