Optimization with binet matrices |
| |
Authors: | Gautam Appa,Balá zs Kotnyek,Leonidas Pitsoulis |
| |
Affiliation: | a Operational Research Department, London School of Economics, Houghton Street, London WC2A 2AE, UK b I3S & Inria Sophia Antipolis, France c Department of Mathematical and Physical Sciences, Aristotle University of Thessaloniki, Thessaloniki 54124, Greece |
| |
Abstract: | This paper deals with linear and integer programming problems in which the constraint matrix is a binet matrix. Linear programs can be solved with the generalized network simplex method, while integer programs are converted to a matching problem. It is also proved that an integral binet matrix has strong Chvátal rank 1. |
| |
Keywords: | Half-integrality Generalized networks Matching Strong Chvá tal rank |
本文献已被 ScienceDirect 等数据库收录! |
|