Adding the Max-k-Cut application #299

clausia · 2021-12-13T16:14:47Z

Summary

Adding the Max-k-Cut to the application section

Details and comments

Max-k-Cut: Given an undirected graph, find a partition of nodes into at most k subsets such that the total weight of the edges between the k subsets is maximized. To solve this problem, the space-efficient quantum optimization representation (or encoding) for the graph coloring problem proposed in [1] is used.

This work has been done in collaboration between Claudia Zendejas-Morales (@clausia) and Vyron Vasileiadis (@fedonman). This contribution was done under QIntern 2021 (https://qworld.net/qintern-2021/) organized by QWorld, under the supervision of Adam Glos (@adamglos92) and Zoltan Zimboras (@zimboras). We would like to thank Kareem H. El-Safty (@kareem1925) for bringing up the idea of implementing space-efficient Max-k-Cut on qiskit.

[1]: Z. Tabi et al., "Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding," 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 2020, pp. 56-62, doi: 10.1109/QCE49297.2020.00018.

Closes #255

* Add new Maxkcut class in qiskit_optimization/applications/max_k_cut.py * Add tests for new Maxkcut class in test/applications/test_max_k_cut.py * Add reference to Maxkcut class in qiskit_optimization/applications/__init__.py file * Mention Maxkcut application in docs/tutorials/09_application_classes.ipynb * Add necessary words in .pylintdict * Add release notes regarding new Maxkcut class in releasenotes/notes/add-max-k-cut-app-7e451a5993171175.yaml Co-authored-by: fedonman <hi@fedonman.com>

coveralls · 2021-12-14T19:47:32Z

Pull Request Test Coverage Report for Build 2265763085

79 of 90 (87.78%) changed or added relevant lines in 2 files are covered.
No unchanged relevant lines lost coverage.
Overall coverage decreased (-0.02%) to 91.222%

Changes Missing Coverage	Covered Lines	Changed/Added Lines	%
qiskit_optimization/applications/max_k_cut.py	78	89	87.64%

Totals
Change from base Build 2263161952:	-0.02%
Covered Lines:	4292
Relevant Lines:	4705

💛 - Coveralls

woodsp-ibm · 2022-01-06T15:00:56Z

qiskit_optimization/applications/max_k_cut.py

+        """
+        super().__init__(graph=graph)
+        self._subsets_num = k
+        self._colors = colors if colors and len(colors) >= k else None


For colors I see that more are allowed to be defined and presumably ignored; however if colors were given but less than k then they are discarded. In looking further, from what can see, these are just used if/when the user the draws the result.

I am wondering whether it might be better to move this off the constructor and just say have a method call something like set_draw_colors that takes the same thing and stores it for the rendering. That makes this feel less like part of the problem definition - at least to me. I would have said pass them on draw but then this is implementing logic defined in the base class and it does not seem to support customizing the rendering in this way.

In terms of the colors I think it should define what the string and int formats are - if its simply matplot color format then I think that can be stated perhaps with a link to matplot colot doc that has the info plus perhaps an example in the code to help people.

Also I wonder since this is a set of colors should they be passed in as a set so that it contains unique items - otherwise a user can specify the same color again. In regards of the behavior or more or less colors given than k maybe you prefer the less severe mechanism of discarding all or part of them depending on size. I think at least the code should emit a warning to alert the user - ideally they should be passing in k colors right not some other sized set. If this is a separate method just to set draw colors then maybe allowing only None (to reset to internal default) or a k sized set and raising a ValueError if the size if not equal to k might be more acceptable?

Thank you for your comments, they have already been addressed:

The importance of including the definition of colors in the constructor is that this implementation is based on the "Graph Coloring Problem", but I understand your concern, we can have the solution of the max-k-cut problem without the need to draw the resulting graph. To change (or add) the colors you have the methods set/get (colors, called like that for the same reason, that we are thinking about the "Graph Coloring Problem").
So, I have removed the colors parameter from the constructor, (before it was optional), I have already done this update.

As for the documentation, certainly including an example is much better for people who use this class, that update is ready, please review.

Regarding that the user can specify a repeated color, it seems to me that we should allow this type of flexibility, that this decision is up to the user, finally if it was not his/her intention, she/he will be able to see the result when he requests the drawing of the graph (the user will see fewer colors than 'k').

Now it is being validated that the size of the color list is equal to the k parameter, and if it is not, the ValueError is thrown indicating that the colors have not been assigned because they are not the correct amount.

@woodsp-ibm, what do you think of the changes?

woodsp-ibm · 2022-01-06T15:07:32Z

qiskit_optimization/applications/max_k_cut.py

+
+        n = self._graph.number_of_nodes()
+
+        # k colors chosen (randomly or from cm.rainbow), or from given color list


As far as doing things randomly there exists an random generator in algorithm_globals in Terra that we created to have a common generator that algorithms and applications would use so that a user could create reproducible results by seeding it. Using that, instead of whats done here, would allow a user to seed it and have the same colored drawing each time if they prefer - of course they could pass in their own colors too, but I think using the common generator is preferable.

Now algorithm_globals is used

CLAassistant · 2022-01-09T13:47:38Z

All committers have signed the CLA.

Co-authored-by: Claudia Zendejas-Morales <ing.claudia@gmail.com>

t-imamichi · 2022-02-09T15:30:30Z

qiskit_optimization/applications/max_k_cut.py

+
+    References:
+        [1]: Z. Tabi et al.,
+             "Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding"


This paper addresses a graph coloring problem and does not mention max-k-cut problem.
Could you refer an appropriate paper or page?

Hi @t-imamichi, graph colouring problem is a decision variant of max-k-cut. Graph coloring problem is about checking if there "exists colouring of the nodes which make every edge connecting nodes with a different colour." Contrary, Max-K-Cut is about finding the colouring for which the number of such edges is maximized. You could say that graph colouring to max-K-Cut shows similar relation as SAT to MAX-SAT. For this reason, and the fact max cut is already used in the package we decided to choose max-k-cut name

As far as the paper mentions only coloring problem, I don't think it's an appropriate citation of max-k-cut. It would confuse users. Why not rename the class "k-coloring problem" as the paper addresses?

Moreover, there are many papers directly addressing max-k-cut problem. Why do you need to refer that paper (Tabi et al.) for max-k-cut class?

The notion of feasibility changes. For Max-Cut every solution is feasible, for graph colouring only those with all edges connecting different nodes are feasible. This is obviously correct but inconsistent with max-cut used in the qiskit-optimization.
Since this is for optimization purposes mostly we found Max-K-Cut more accurate. But we can also move it to k-graph-coloring
We are not aware of older papers that propose the given formulation. If there is one, we're open to replacing the reference.

You mentioned

if there "exists colouring of the nodes which make every edge connecting nodes with a different colour."

But, coloring does not take care of edge weights. So, I don't think the optimal solution of coloring does not corresponds to the optimal solution to max-k-cut problem.

You must make a mixed integer programming model of max-k-cut. Here is the definition of k-cut value (though this page addresses minimization)
https://en.wikipedia.org/wiki/Minimum_k-cut

You may perhaps try to use an solution of coloring problem as a heuristic solution of max-k-cut problem?
If so, I ask you to make a proper mixed integer programming model of max-k-cut problem.
The model of application classes should be exact. Otherwise, even if we apply CPLEX or Gurobi to the model, we may not be able to obtain the optimal solution.

t-imamichi · 2022-02-09T15:33:07Z

qiskit_optimization/applications/max_k_cut.py

+        n = self._graph.number_of_nodes()
+        k = self._subsets_num
+        x = {(v, i): mdl.binary_var(name=f"x_{v}_{i}") for v in range(n) for i in range(k)}
+        first_penalty = mdl.sum_squares((1 - mdl.sum(x[v, i] for i in range(k)) for v in range(n)))


Could you make a model with a standard formulation of the problem? Please do not penalize constraints by yourself.
In the application classes, we make a model with a standard formulation. The conversion to QUBO will be done within algorithm classes.

t-imamichi · 2022-02-09T15:41:58Z

qiskit_optimization/applications/max_k_cut.py

+        x = {(v, i): mdl.binary_var(name=f"x_{v}_{i}") for v in range(n) for i in range(k)}
+        first_penalty = mdl.sum_squares((1 - mdl.sum(x[v, i] for i in range(k)) for v in range(n)))
+        second_penalty = mdl.sum(
+            mdl.sum(self._graph.edges[v, w]["weight"] * x[v, i] * x[w, i] for i in range(k))


I think this takes sum of edges whose end nodes are same color (i). Is it a correct k-cut value?
I think k-cut value is the sum of edges whose end nodes have different colors.
Anyways, could you refer an appropriate paper or page and make a model (obj func + constraints).

t-imamichi · 2023-08-21T05:13:20Z

@clausia Do you have any updates? If not, we will close this PR.

clausia · 2023-08-21T14:40:54Z

@t-imamichi Hi, thanks for asking, I think it's best to close this PR and open another one when the update is ready

clausia requested review from manoelmarques, pbark, stefan-woerner, t-imamichi and woodsp-ibm as code owners December 13, 2021 16:14

clausia added 2 commits December 13, 2021 19:51

validate if it is possible to use the matplotlib library

57208a7

minor fix (for library validations)

4db521a

clausia and others added 6 commits December 16, 2021 03:47

Merge branch 'main' into max-k-cut-app

11d6f96

Merge branch 'main' into max-k-cut-app

5fa9126

Merge branch 'main' into max-k-cut-app

6cb7536

Merge branch 'main' into max-k-cut-app

9fb9458

Merge branch 'main' into max-k-cut-app

d457732

Merge branch 'main' into max-k-cut-app

6408781

woodsp-ibm reviewed Jan 6, 2022

View reviewed changes

Merge branch 'main' into max-k-cut-app

afdabab

clausia and others added 2 commits January 10, 2022 02:32

Get colors parameter out of init, using algorithm_globals

2ccae04

update copyright year

63ba6b1

Co-authored-by: Claudia Zendejas-Morales <ing.claudia@gmail.com>

clausia force-pushed the max-k-cut-app branch from 0c62355 to 63ba6b1 Compare January 10, 2022 17:13

clausia and others added 5 commits January 14, 2022 15:39

Merge branch 'main' into max-k-cut-app

c42e061

Merge branch 'main' into max-k-cut-app

82c67bd

Merge branch 'main' into max-k-cut-app

6e64655

Merge branch 'main' into max-k-cut-app

6bec1f9

Merge branch 'main' into max-k-cut-app

4aa90a8

t-imamichi reviewed Feb 9, 2022

View reviewed changes

clausia added 12 commits February 9, 2022 11:34

Merge branch 'main' into max-k-cut-app

c8a8107

Merge branch 'main' into max-k-cut-app

a74c686

Merge branch 'main' into max-k-cut-app

323ec1e

Merge branch 'main' into max-k-cut-app

980df66

Merge branch 'main' into max-k-cut-app

e696d23

Merge branch 'main' into max-k-cut-app

647028f

Merge branch 'main' into max-k-cut-app

c869735

Merge branch 'main' into max-k-cut-app

5cf0eee

Merge branch 'main' into max-k-cut-app

2997c45

Merge branch 'main' into max-k-cut-app

91f390c

Merge branch 'main' into max-k-cut-app

2d1e302

Merge branch 'main' into max-k-cut-app

d19b1d1

manoelmarques removed the request for review from pbark June 29, 2022 18:26

HuangJunye added the Commmunity PR PRs from contributors that are not 'members' of the Qiskit organization label Jun 30, 2022

t-imamichi closed this Aug 21, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Adding the Max-k-Cut application #299

Adding the Max-k-Cut application #299

clausia commented Dec 13, 2021

coveralls commented Dec 14, 2021 •

edited

woodsp-ibm Jan 6, 2022

clausia Jan 10, 2022

clausia Jan 17, 2022

woodsp-ibm Jan 6, 2022

clausia Jan 10, 2022

CLAassistant commented Jan 9, 2022 •

edited

t-imamichi Feb 9, 2022

adamglos92 Feb 9, 2022

t-imamichi Feb 9, 2022 •

edited

t-imamichi Feb 9, 2022

adamglos92 Feb 9, 2022 •

edited

t-imamichi Feb 9, 2022 •

edited

t-imamichi Feb 9, 2022

t-imamichi Feb 9, 2022

t-imamichi Feb 9, 2022

t-imamichi commented Aug 21, 2023 •

edited

clausia commented Aug 21, 2023


		n = self._graph.number_of_nodes()

		# k colors chosen (randomly or from cm.rainbow), or from given color list

Adding the Max-k-Cut application #299

Adding the Max-k-Cut application #299

Conversation

clausia commented Dec 13, 2021

Summary

Details and comments

coveralls commented Dec 14, 2021 • edited

Pull Request Test Coverage Report for Build 2265763085

💛 - Coveralls

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

CLAassistant commented Jan 9, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

t-imamichi Feb 9, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

adamglos92 Feb 9, 2022 • edited

Choose a reason for hiding this comment

t-imamichi Feb 9, 2022 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

t-imamichi commented Aug 21, 2023 • edited

clausia commented Aug 21, 2023

coveralls commented Dec 14, 2021 •

edited

CLAassistant commented Jan 9, 2022 •

edited

t-imamichi Feb 9, 2022 •

edited

adamglos92 Feb 9, 2022 •

edited

t-imamichi Feb 9, 2022 •

edited

t-imamichi commented Aug 21, 2023 •

edited