I have $n$ integer variables $\vec{x}$ with the following integer programming problem.

$$ COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0) $$

Here, $a_i, b_j \in \mathbb{R}_+$ and $I$ is the indicator function. I would like to minimize COST. How can I implement $\sum^{n-1}_{j=0} b_j I(x_j > 0)$ so that it is a quadratic unconstrained binary/integer optimization problem?

  • $\begingroup$ Are you hoping to solve this on a D-Wave Quantum Annealing computer? bernalde.github.io/QuIP/slides/… $\endgroup$ Commented Oct 6, 2020 at 16:36
  • $\begingroup$ Is your $x_j$ non-negative? Further do you have an upper bound on $x_j$? $\endgroup$
    – batwing
    Commented Oct 6, 2020 at 17:03
  • $\begingroup$ I see you work for IonQ. D-Wave is a one-trick pony (and as of now, I don't think it's even a very good trick), heuristically solving QUBO 's. by Quantum Annealing. Does IonQ have other tricks? Shoehorning everything into QUBO 's doesn't seem to me to necessarily be the best way of solving MILPs. Constraints now, constrains Forever. $\endgroup$ Commented Oct 6, 2020 at 20:31
  • 4
    $\begingroup$ Since the cost coefficients are nonnegative and you have no other constraints, no model is required. There are two possibilities. If the $x$ variables are nonnegative, set them all to zero and declare victory. Otherwise, set every variable that can be negative to its most negative possible value, set the remaining variables to zero, and declare victory. I sense that something is missing. $\endgroup$
    – prubin
    Commented Oct 6, 2020 at 21:09


Your Answer

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