0

At first, there are a bunch of objects. Every single object has an attribute, which tells the type of groups it wants to belong to. A group is a container for a given number of objects. It has a type.

Now I'm looking for the combination where most objects are in a group that the object preferred. As the amount of groups is calculated by a formula which gives the lowest possible number, there are combinations where not all objects are in a preferred type of group. That's ok, because I'm looking for the combination(s) where most objects are in a preferred group.

A object can favor multiple types of groups, so it doesn't matter in which of the favored groups it is.

The group type can be chosen freely from the requested group types.

Is there an algorithm which can solve this problem?

Example

There are five objects. The first two don't care whether they are in a group of type A or B. The third wants to be in a group of type A, the fourth in a group of type C and the last one wants to be in type B.

The group size is two. The count of groups is calculated by the formula below.

Every type of a group can be chosen freely from the requested types (A, B or C).

example of question

Edit

Think about group size 6 and 12 objects. Eleven of them with preferred group type A and one of them with preferred group type B. For 12 objects and group size 6 there are 2 groups. The best solution would be to make two groups with type A. Then eleven objects are in a preferred group and one is in a group that it didn't prefer. Just to clarify, every object should be in a group.

How to find the best combination of group types? In this example, how can I connect the object with preferred group type B to a group (in the graph)? As far as I understood, Ford Fulkerson requires that the group types are already knwon.

Improve this question
1
  • 1
    This might be doable with min-cost max-flow (in poly-time). As it's very late here, i will only provide the keyword for further research. You can check out some ortools example which is not exactly (caveat: small model-deviations often have dramatic effects: P vs. NP) what you are trying. But it's a first read if you are new to this concept. Commented Nov 3, 2018 at 1:33

1 Answer 1

Reset to default
1

This problem can solve using max flow. In the comment section @sascha suggests min-cost max-flow. But i think there's no need to add cost to the flow network for this problem. Also complexity of min-cost max flow is greater than the complexity of max flow. There are several algorithm for max flow(see https://en.wikipedia.org/wiki/Maximum_flow_problem#Solutions) with different complexity.

Max Flow Problem: You are given flow network with capacity. Now you have to find maximum flow from source node to destination node. For example see the figure below:

enter image description here

Convert Your Problem to max flow problem:

Your problem: You are given objects. Each objects has preferred group type( they can have multiple group type). Each group has a capacity of how many objects they can hold. Now you are looking for the combination where most objects are in a group that the object preferred.

Converting to max flow: Think each object and each group as a node. Each object has preferred group type, so set an edge from each object to it's preferred group and set the capacity 1(as each object can be assigned to one group). Also set an edge from source node to each object, set capacity 1(as one object). Each group has a capacity of how many objects they can hold, so set an edge from each group to destination node and set the capacity how many objects it can hold.

For your given examples, flow network is illustrated in the below figure:

enter image description here

You can figure out which object assigned to which group from the flow path after you run the algorithm.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I edited my question and added another example. How can I apply this example to the max-flow problem?
Max flow is best way assign objects(with multiple preferred group) to groups. @Antict you could try combinations of groups and run max flow. Whichever combitnation gives you maximum flow will be you answer. Also for objects that are not assigned, you can assign them to the groups that have empty slots.

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.