Browse Prior Art Database

Set Packing Formulation for Resource Allocation Problems

IP.com Disclosure Number: IPCOM000118858D
Original Publication Date: 1997-Aug-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 2 page(s) / 38K

Publishing Venue

IBM

Related People

Misono, S: AUTHOR [+2]

Abstract

Disclosed is a method that solves resource allocation problems where relative relations among resources are considered. Precisely, the resources are divided into subgroups within which the relative positions should be considered and evaluated.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 100% of the total text.

Set Packing Formulation for Resource Allocation Problems

      Disclosed is a method that solves resource allocation problems
where relative relations among resources are considered.  Precisely,
the resources are divided into subgroups within which the relative
positions should be considered and evaluated.

      This method treats each subgroup as a unit of assignment,
and a candidate of allocation for the subgroup is defined as a set of
destinations of the members of the subgroup.  The problem is
formulated as a kind of integer programming, Set Packing Problem,
where rows of the constraint matrix represent destinations for the
allocation and the columns represent candidates for the allocation of
each subgroup.  Additional rows are defined in order to specify that
each subgroup has only one destination.  The mathematical
representation is  shown in the Figure.  Equation (2) in the Figure
represents that each destination should be occupied by at most one
resource.  Equation (3) in the Figure represents that each subgroup
has exactly one destination.

      The Set Packing Problem can be solved using mathematical
programming packages, and the user only has to enumerate candidates
and evaluate the likeliness as to their costs.