Open alejomonbar opened 1 year ago
I agree that having something like a penalization_method
keyword argument to add_linear_inequality_constraint
seems like a desirable feature.
@arcondello If you agree, I will try to implement it.
Please do! Feel free to ask questions here if you need any help
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 inadd_linear_inequality_constraint
.Proposed Solution Implement a function
unbalanced_penalization
to be used inadd_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