← ALB News · curated headline

Compact Slack-Free Penalty Functions for Inequality Constraints in Higher-Order Unconstrained Binary Optimization

arXiv Mathematics · WORLD · Mathematics · 11/20/2026, 12:00:00 AM

arXiv:2611.25102v1 Announce Type: new Abstract: Inequality constraints in higher-order unconstrained binary optimization (HUBO) are commonly handled using slack variables or by enumerating infeasible assignments, which respectively enlarge the search space or produce penalties whose size grows with the number of forbidden values. We construct exact slack-free penalty functions for upper- and lower-bound constraints on binary-encoded integers. Each function is constructed hierarchically from the threshold bits through a recursive addition-and-multiplication rule, and its correctness for arbitrary bit widths and representable thresholds is proved by mathematical induction. Equivalent explicit finite sum-product representations are also derived, enabling direct analysis of product-term count and polynomial degree. Interval constraints are obtained by adding the lower- and upper-bound penalties, while exclusion constraints are obtained by multiplying them. Compared with the trivial enumerative construction, the proposed method reduces the worst-case product-term count from linear to logarithmic in the representable range. Except at one non-vacuous boundary threshold for each bound, it also reduces both product-term count and degree. The resulting single-bound penalties have minimum positive value 1 and maximum value at most the bit width, which may simplify penalty-weight selection. The same construction also extends exactly to fixed-scale fractional variables through appropriate scaling of the integer thresholds.

Continue to arXiv Mathematics →

You are being forwarded in 6s — stay on this page