2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are you hoping to solve this on a D-Wave Quantum Annealing computer? bernalde.github.io/QuIP/slides/… $\endgroup$ – Mark L. Stone Oct 6 at 16:36
  • $\begingroup$ Is your $x_j$ non-negative? Further do you have an upper bound on $x_j$? $\endgroup$ – batwing Oct 6 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$ – Mark L. Stone Oct 6 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 Oct 6 at 21:09

Your Answer

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

Browse other questions tagged or ask your own question.