Python to Julia: Boolean Optimization

Hello Julians:

I am looking to find the lowest energy
state for the following system:

(5x_a) - (0.1x_0) - (2x_a*x_0) - 1.5

Using the following truth table:
x_a | x_0
0 | | 0
0 | | 1
1 | | 0
1 | | 1

The first step in this series is to
initialize the empty qubo object
as:

qubo = QUBO()

Then build the qubo elements
with:

qubo[('a',)] += 5
qubo[(0,)] -= 0.1
qubo[(0, 'a')] -= 2
qubo -= 1.5
model_solution = qubo.solve_bruteforce()

After, find the optimum value
using

qubo.value(model_solution)

Could any of you point me to
resources that could help
convert these process steps
to Julia?

Thanks,

Sorry, what is a QUBO object? I am from the area of optimization and have never heard of it.

I guess it stands for quadratic unconstrained binary optimization? As someone who has next to no experience with optimization stuff, I found the README in this related repo (GitHub - lanl/find-qubo: Construct a QUBO from a truth table) a lot more helpful, but I could be totally off here

1 Like

So you want to find which one of those four options gives the lowest value for the function? I would probably do

x_a = [false, true, false, true]
x_0 = [false, false, true, true]
y = 5*x_a .- 0.1*x_0 .- 2*x_a.*x_0 .+ 1.5

y_1, i = findmin(y)

x_a1 = x_a[i]
x_01 = x_0[i]
2 Likes

Well, if what Python is doing is a brute-force (as hinted by solve_bruteforce()), then @gustaphe is adequate (while it probably allocates more memory than necessary).

I remember the Quadratic Binary Problem, I just did not associate with the acronym and the example. It is NP-Hard and you probably will need something more elaborate if you want to solve larger instances.

As @icweaver expressed, QUBO, is a quadratic function
on boolean variables. The QUBO problem, then finds the
assignment of boolean variables that five a minimum
function value. In this scenario, (1,0) giving (-1.6) – you
are probably familiar, was only expanding the knowledge.

@Henrique_Becker – do you have any idea what packages/
modules might help me deal with larger D and N? Or might
this require a native build?

Thank you,

I did not work on QUBO, so I am not aware if the Julia ecosystem has something specific aimed at it. I do know that JuMP supports commercial solvers (with free academic licenses) which support non-linear optimization. And QUBO is not the hardest problem to model (the gap between the input and a trivial formulation is small). Did you already consider using Gurobi, CPLEX, or other solver?

2 Likes

Just found this and might be of interest:

https://psrenergy.github.io/ToQUBO.jl/dev/

@pedromxavier @joaquimg

1 Like

This was just sent to the registry! 2 more days before it’s there.
The goal is to convert “any” JuMP model into a QUBO approximation and then solve it with Annealers (classical or quantum).
You can also write your QUBO directly in JuMP (just make all your variables binary and pass your quadratic objective). In this case, ToQUBO won’t need to reformulate but will send the problem to your selected annealer.

1 Like

@joaquimg

How would you write the I/O request in Pluto 1.8.*
(web, not the REPL):

$ git clone https://github.com/psrenergy/ToQUBO.jl
$ cd ToQUBO.jl
$ julia --project=.

I started by using the HTTP package so that

using HTTP
r = HTTP.request("GET", "https://github.com/psrenergy/ToQUBO.jl")

How might I change the directory to (“ToQUBO.jl”) here?

Also: I do not believe git clone is a recognized command
in the REPL. (dev) might be the most viable substitute?

Thank you,

Hopefully the registration will make this unnecessary, but in general see here:
https://pkgdocs.julialang.org/v1/managing-packages/#Adding-unregistered-packages
But also in general, add this code to the beginning of the notebook:

using Pkg
Pkg.add(url="https://github.com/psrenergy/ToQUBO.jl", rev="master")

(Change the string after rev= to the desired branch name).

1 Like

Thank you for this @jd-foster

I implemented the following using Git
recommended by a colleague here

using Git
run(git(["clone", "https://github.com/psrenergy/ToQUBO.jl"]))
cd("ToQUBO.jl")

How would you implement in
a Pluto.jl session (NOT the REPL)

julia --project=.