Automatic identification of embedded network rows in large-scale optimization models
Abstract
The solution of a contemporary large-scale linear, integer, or mixed-integer programming problem is often facilitated by the exploitation of intrinsic special structure in the model. This paper deals with the problem of identifying embedded pure network rows within the coefficient matrix of such models and presents two heuristic algorithms for identifying such structure. The problem of identifying the maximum-size embedded pure network is shown to be among the class of NP-hard problems; therefore, the polynomially bounded, efficient algorithms presented here do not guarantee network sets of maximum size. However, upper bounds on the size of the maximum network set are developed and used to evaluate the algorithms. Computational tests with large-scale, real-world models are presented.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.NPS Report Number
NPS55-80-030Collections
Related items
Showing items related by title, author, creator and subject.
-
Automatic identification of embedded network rows in large-scale optimization models
Brown, Gerald G.; Wright, William G. (Springer, 1984);The solution of a large-scale linear, integer, or mixed integer programming problem is often facilitated by the exploitation of special structure in the model. This paper presents heuristic algorithms for identifying ... -
Homeland Security Affairs Journal, Volume II - 2006: Issue 2, July
Naval Postgraduate School Center for Homeland Defense and Security (CHDS) (Monterey, California. Naval Postgraduate SchoolCenter for Homeland Defense and Security, 2006-07);July 2006. The July 2006 issue of Homeland Security Affairs offers articles about risk perception, domestic right wing extremist groups, social network analysis, and the impact of foreign policy on homeland security. It ... -
Homeland Security Affairs Journal, Volume III - 2007: Issue 3, September
Naval Postgraduate School Center for Homeland Defense and Security (CHDS) (Monterey, California. Naval Postgraduate SchoolCenter for Homeland Defense and Security, 2007-09);September 2007. Six years after the attacks of 9/11, the practice and discipline of homeland defense and security have evolved and matured, moving into an era of self-evaluation. The essays and articles in Volume III, Issue ...