Given a matrix S and a subset of columns R, we study the problem of finding a cover of R with extreme rays of the cone, where an extreme ray v covers a column k if v[k] > 0. In order to measure how proportional a cover is, we introduce two different minimization problems, namely the minimum global ratio cover (MGRC) and the minimum local ratio cover (MLRC) problems. In both cases, we apply the notion of the ratio of a vector v. We show that these two problems are NP-hard, even in the case in which |R| = 1. We introduce a mixed integer programming formulation for the MGRC problem, which is solvable in polynomial time if all columns should be covered, and introduce a branch-and-cut algorithm for the MLRC problem. Finally, we present computational experiments on data obtained from real metabolic networks.
MINIMUM RATIO COVER OF MATRIX COLUMNS BY EXTREME RAYS OF ITS INDUCED CONE / A. FREIRE; V. ACUÑA; P. CRESCENZI; C. FERREIRA; V. LACROIX; P. VIEIRA MILREU; E. MORENO; M. SAGOT. - STAMPA. - (2012), pp. 165-177. (Intervento presentato al convegno SECOND INTERNATIONAL SYMPOSIUM ON COMBINATORIAL OPTIMIZATION) [10.1007/978-3-642-32147-4_16].
MINIMUM RATIO COVER OF MATRIX COLUMNS BY EXTREME RAYS OF ITS INDUCED CONE
CRESCENZI, PIERLUIGI;
2012
Abstract
Given a matrix S and a subset of columns R, we study the problem of finding a cover of R with extreme rays of the cone, where an extreme ray v covers a column k if v[k] > 0. In order to measure how proportional a cover is, we introduce two different minimization problems, namely the minimum global ratio cover (MGRC) and the minimum local ratio cover (MLRC) problems. In both cases, we apply the notion of the ratio of a vector v. We show that these two problems are NP-hard, even in the case in which |R| = 1. We introduce a mixed integer programming formulation for the MGRC problem, which is solvable in polynomial time if all columns should be covered, and introduce a branch-and-cut algorithm for the MLRC problem. Finally, we present computational experiments on data obtained from real metabolic networks.I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.