@techreport{TR-IC-PFG-17-13,
   number = {IC-PFG-17-13},
   author  =  {K.  Rollmann  and  W.  Cardoso and V. L. Lima and F. K.
                   Miyazawa},
   title  =  {{Heuristic  and  Exact  Algorithms  for  the 2D Knapsack
                   Problem with Relations Between Items}},
   month = {December},
   year = {2017},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 27 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       This  work  deals  with  a variation of the 0-1 two-dimensional
       knapsack problem, where each item has a value and there is also
       a  value  between  each  pair of items. The value of adding one
       item into the packing depends not only on the item's value, but
       also  on  its  relation values with other items that are in the
       packing.   We   adapted  some  inputs  commonly  found  on  the 
       literature   to   our   problem   and  we  propose  some  exact 
       formulations to solve the problem. Our formulations use integer
       programming  models  that work in two phases: the first finds a
       packing  considering relaxed constraints, and the second checks
       if  the  packing  is  feasible.  Three  approaches to check the
       packing  feasibility  were  compared. Moreover, we propose four
       decoders  to the BRKGA meta-heuristic and compare their quality
       with  the  solutions  found  using  exact models. Computational
       results are also provided to show the quality of our methods.
  }
}