algorithmcombinationsmathematical-optimizationor-toolspowerset

Finding best result matching sets of items. Powerset optimization

I'm having this combination problem where I'm trying to find subsets of matching combinations of 2 items which results in the highest amount of total matches. Every item can only be in a match once. In the example below I have 4 items. With all combinations checked I get the results which end up being true or false. The problem is finding the Option with the highest amount of matches. In this case Option 2. In my case the number of items is up to 100. I've coded a brute force solution with a Powerset of the tested combinations but it takes too long with a large number of items. I'm looking at python OR-tools from google but not sure how to translate my problem to one of the examples. How is the problem called I'm trying to solve? Can you point me in the right direction?

Thank you!

[1, 2, 3, 4]

1 - 2 false
1 - 3 true
1 - 4 true
2 - 3 true
2 - 4 false
3 - 4 true

Option 1
1 - 3

Option 2
1 - 4
2 - 3

Option 3
3 - 4

Based on the answer below I've created this working code.

import networkx as nx

# List of items
items = [1, 2, 3, 4]

# Create a bipartite graph
G = nx.Graph()

all_matching = [(1, 3), (1, 4), (2, 3), (3, 4)]

# Add nodes for the two partitions (left and right)
G.add_nodes_from(items, bipartite=0)
G.add_nodes_from(items, bipartite=1)

# Add edges connecting items to pairs they belong to
for item, pair in all_matching:
    G.add_edge(item, pair)

# Find the maximum matching
matching = nx.max_weight_matching(G)

print(matching)
Solution

  • You can formulate the problem as maximum bipartite matching problem. You can use network flow algorithms like the Edmonds-Karp or Dinic's algorithm to find the maximum matching in a bipartite graph. In your case, the items can be considered as nodes in a graph, and you can create edges between items that can form valid matches.

    Here's a high-level outline of how you can approach this problem:

    Represent the problem as a bipartite graph:

    Create a graph where each item is represented as a node. Connect nodes (items) that can form valid matches with edges. Assign capacities to the edges:

    Assign a capacity of 1 to each edge because each item can only be used once. Find the maximum matching:

    Use a maximum flow algorithm to find the maximum matching in the bipartite graph.

    If you are looking for a python library check NetworkX :

    Check this for more detail : GeeksforGeeks