dwavesystems / dwavesystems/dimod

Add unbalanced penalization for inequality constraints

Open
#1,339 3 comments 0 reactions 0 assignees View on GitHub
enhancement
Dominant language
Python
Stars
143
Forks
91
Avg merge
1h 24m
Merged PRs (30d)
3

Description

**Application**

Unbalanced penalization is an alternative way to represent inequality constraints without the need of using extra slack variables. We have shown that this method works well for the bin packing problem (BPP) [1] and the traveling salesman problem (TSP) [2] using D-Wave Advantage and D-Wave hybrid solvers. Additionally, it outperforms the results obtained when using slack variables. It would be nice if you implement this method as a new type of constraint. I propose to add the unbalanced penalization method to `/binary/binary_quadratic_model.py` to handle inequality constraints with this method in `add_linear_inequality_constraint`.

**Proposed Solution**
Implement a function `unbalanced_penalization` to be used in `add_linear_inequality_constraint` if the user want to use the unbalanced penalization method.

**Additional Context**
[1] Montanez-Barrera, A., Willsch, D., A., Maldonado-Romo, & Michielsen, K. (2022). Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms. 23–25. http://arxiv.org/abs/2211.13914

[2] Montanez-Barrera, J. A., Heuvel, P. van den, Willsch, D., & Michielsen, K. (2023). Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage. http://arxiv.org/abs/2305.18757

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.