An MSSP-Like Problem
- From: "Charles Tsai" <charles@xxxxxxxxxxxxxx>
- Date: Wed, 24 Aug 2005 21:10:04 +0800
Hello, Everyone,
We need advice on an optimization problem
that we are trying to solve. The problem is stated
as follows.
Given a set of m bins with capacities c_1, c_2,
...., c_m, and a set of n items with positive integral
weights w_1, w_2, ..., w_n, the objective is to assign
the items to the bins so that the sum of 'effective
weights' is maximized. The 'effective weight' with
respect to a bin is defined as the minimum of 'the
total weights of the items assigned to the bin' and
'the capacity of the bin'. Each item can either stay
unassigned or be assigned to exact one bin. That is,
the goal is to
maximize Sum_i(Min(Sum_j(w_j * x_ij), c_i))
subject to (1) Sum_i(x_ij) <= 1 for j = 1, 2, ..., n,
and (2) x_ij is either 0 or 1 for i = 1, 2, ..., m,
and j = 1, 2, ..., n.
This problem is similar to the Multiple Subset
Sum Problem (MSSP). However, the problem stated here
allows the sum of the weights of the items assigned to
a bin to exceed the capacity of the bin, and then it
uses the Min() function to balance the gain of
such assignment.
What we want to know is the complexity of this
problem. Please kindly share your opinions with us.
Thanks in advance.
Regards,
Charles
.
- Prev by Date: An MSSP-Like Problem
- Next by Date: Re: proper deletion algorithm for Patricia trie
- Previous by thread: An MSSP-Like Problem
- Index(es):
Relevant Pages
|
