toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Acuna, V.; Ferreira, C.E.; Freire, A.S.; Moreno, E. pdf  doi
openurl 
  Title Solving the maximum edge biclique packing problem on unbalanced bipartite graphs Type Journal Article
  Year 2014 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.  
  Volume 164 Issue Pages 2-12  
  Keywords Maximum edge biclique packing; Branch-and-price; Metabolic networks; Product bundling  
  Abstract A biclique is a complete bipartite graph. Given an (L, R)-bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved.  
  Address [Acuna, V.] Univ Lyon 1, F-69622 Villeurbanne, France, Email: afreire@ime.usp.br  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0166-218x ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000332427400002 Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 361  
Permanent link to this record
 

 
Author Osorio-Valenzuela, L.; Pereira, J.; Quezada, F.; Vasquez, O.C. doi  openurl
  Title Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints Type Journal Article
  Year 2019 Publication Applied Mathematical Modelling Abbreviated Journal Appl. Math. Model.  
  Volume 74 Issue Pages 512-527  
  Keywords Scheduling; Parallel machines; Interval and workload constraints; Branch-and-price  
  Abstract In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-andprice approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem. (C) 2019 Elsevier Inc. All rights reserved.  
  Address [Osorio-Valenzuela, Luis] Univ Santiago Chile, Elect Engn Dept, Santiago, Chile, Email: luis.osoriov@usach.cl;  
  Corporate Author Thesis  
  Publisher Elsevier Science Inc Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0307-904x ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000474317800031 Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 1013  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: