  [Bil10b] Solving a cut problem in bipartite graphs by linear programming: Application to a forest management problem

Revue Internationale avec comité de lecture : Journal Applied Mathematical Modelling, vol. 34(4), pp. 1042-1050, 2010, (doi:10.1016/j.apm.2009.07.014)

Mots clés: Bipartite graph, Cut, Linear programming, Biodiversity conservation, Land allocation modelling, Wildlife habitat, Experiments

Résumé: Given a bipartite graph G=(V,E), a weight for each node, and a weight for each edge, we consider an extension of the MAX-CUT problem that consists in searching for a partition of V into two subsets V1 and V2 such that the sum of the weights of the edges from E that have one endpoint in each set plus the sum of the weights of the nodes from V that are in V1, is maximal. We prove that this problem can be modeled as a linear program (with real variables) and therefore efficiently solved by standard algorithms. Then, we show how this result can be applied to model a land allocation problem by a 01 linear program. This problem consists in determining the cells of a land area, divided into a matrix of identical square cells, which must be harvested and the cells which must be left in old growth so that the weighted sum of the expected populations of some species is maximized. Some computational results are presented to illustrate the efficiency of the method.

Equipe: oc

BibTeX

 @article { Bil10b, title = "{Solving a cut problem in bipartite graphs by linear programming: Application to a forest management problem}", author = "A. Billionnet", journal = "Applied Mathematical Modelling", year = 2010, volume = 34, number = 4, pages = "1042-1050", doi = "10.1016/j.apm.2009.07.014", }