NotesFAQContact Us
Collection
Advanced
Search Tips
Back to results
Peer reviewed Peer reviewed
Direct linkDirect link
ERIC Number: EJ764371
Record Type: Journal
Publication Date: 2007-Apr
Pages: 9
Abstractor: Author
ISBN: N/A
ISSN: ISSN-0020-739X
EISSN: N/A
Available Date: N/A
A Structural Connection between Linear and 0-1 Integer Linear Formulations
Adlakha, V.; Kowalski, K.
International Journal of Mathematical Education in Science and Technology, v38 n3 p383-391 Apr 2007
The connection between linear and 0-1 integer linear formulations has attracted the attention of many researchers. The main reason triggering this interest has been an availability of efficient computer programs for solving pure linear problems including the transportation problem. Also the optimality of linear problems is easily verifiable through existing algorithms. However, there is no efficient general technique available to solve 0-1 integer linear problems or to verify their optimality. This paper shows that in the case of one of the easier 0-1 integer linear problems, namely a single assignment problem, such a relation between linear and 0-1 integer linear formulation can be built. The theory behind the proposed "bridge" is based on the combination of the absolute point principle and shadow price theory. The main practical benefit of this work is in providing an algorithm to find a MFL (more-for-less) solution for the assignment problem. To the best of our knowledge, this is one of the first efforts to provide a "more-for-less" result for a 0-1 integer linear problem. (Contains 5 tables.)
Taylor & Francis, Ltd. 325 Chestnut Street Suite 800, Philadelphia, PA 19106. Tel: 800-354-1420; Fax: 215-625-2940; Web site: http://www.tandf.co.uk/journals/default.html
Publication Type: Journal Articles; Reports - Descriptive
Education Level: N/A
Audience: N/A
Language: English
Sponsor: N/A
Authoring Institution: N/A
Grant or Contract Numbers: N/A
Author Affiliations: N/A