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$
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$
1
  • $\begingroup$ As I suspected, something simple that I was failing to see. Thanks a lot for your help and for the prompt answer! $\endgroup$ – Felipe Toledo Jun 20 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.