dwavesystems
Add unbalanced penalization for inequality constraints
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
I agree that having something like a penalization_method keyword argument to add_linear_inequality_constraint seems like a desirable feature.
