4
$\begingroup$

I've recently started to study how to formulate optimization problems as QUBO models through this paper/tutorial: https://arxiv.org/pdf/1811.11538.pdf

One of the steps is to transform the inequalities of the original optimization problem (in an LP formulation for example) into equalities by adding a slack variable. In the example below (taken from page 17) is quite trivial how the bound was found to be 7, assuming x1 = x2 = 0 and x3 = 1, which is the "worst case" or the "furthest" we can be from 6 in the right hand side.

enter image description here

==============================================================

On the other hand, in page 25 there's another example which is making me a bit puzzled:

enter image description here

I'm failing to understand why 3 and 6 were chosen as the bounds here.

For example, for the first constraint, why isn't the bound 7? (assuming x1=x2=x3=x4=x5=0)

As for the third constraint, why isn't the bound 11? (assuming x1=x2=x3=x4=x5=1, so we'd have -16 + s <= -5)

Any help will be much appreciated! Maybe there's something obvious which I haven't realized :)

$\endgroup$

1 Answer 1

3
$\begingroup$

According to the equality constraint (the equal to 4 one), at least two of the $x_{?}$ are 1. Therefore, the slack for the 1st constraint is at most 3.

According to the equality constraint, the worst case is $x_1$, $x_4$, $x_5$ are 1 while other xs are 0. The slack is 6 in that case for the 3rd constraint.

Alternatively, we can approximate the bound of the slacks by noticing that the coefficients in each inequality constraint are all bigger than the coefficients in the equality constraint. Therefore we can at least subtract 4 from the bound of the slacks of the inequality constraints. 7 - 4 = 3 and 11 - 4 = 7 (ok, that is not 6).

$\endgroup$
3
  • $\begingroup$ As I suspected, something simple that I was failing to see. Thanks a lot for your help and for the prompt answer! $\endgroup$ Jun 20, 2021 at 15:43
  • $\begingroup$ Sorry, I don’t understand your second paragraph on the worst cases. I though at least two $$x_i$$s have to be 1. Therefore, inequality 3 will always be >=5. So I’m still unsure how slack 6 is obtained. Also, I don’t understand why you used 11 - 4 = 7. Would appreciate if you could explain a bit more :) $\endgroup$
    – Colin Hong
    Jun 10, 2022 at 7:55
  • $\begingroup$ In the s3 binary expansion, isn't there a missing penalty for 1x8 + 2x9 + 4x10 = 7, since it's only supposed to go to 6? $\endgroup$
    – Fax
    May 5, 2023 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.