I have an optimization problem that's closely related to the generalized assignment problem with an additional constraint. Each knapsack $i$ has capacity $b^i$. There is a number of tasks $j$, each has a cost $c_{i,j}$ and a weight $w_{i,j}$ when assigned t knapsack $i$. The problem is to find an assignment $A^*$ such that the total cost is minimized while each knapsack's capacity is not exceeded by the items' weights. Given that the set of tasks are partitioned into a finite number of non overlapping $l$ groups (i.e., a group of tasks constitutes a job). The additional constraint is as follows: the assignment $A^*$ has a predefined integer $\beta$ of fully assigned groups of tasks: $\sum_{\forall l }\sum_{\forall j} 1_{A*}(x_{i,j}) = \beta$. I am well aware of the classic GAP and heuristics for it. Is there a name for this type of variant of GAP? What are some good resources to go about solving the problem with the additional indicator constraint?

P.S.: I am able to generate the exact solution, I am looking for good resources for approxaimations/heuristics



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.