Inspiration

Aiden was hungry for soup, and came across https://xkcd.com/1293/ . Alex had learned about semidefinite relaxations of binary quadratic programs (such as described in http://www.info.univ-angers.fr/~hao/papers/JOCO2014.pdf ) and wanted to make it better.

What it does

If you're hungry, take your Hōzz and connect it to any faucet. Attach your mouth to the other end, and turn the faucet on. Fresh, delicious soup! On the other hand, if you're facing any problem that can be solved via binary quadratic optimization -- such as stress/strain calculations, stock portfolio optimization, SVP training, genomic analysis, circuit evaluation, or cancer laser dosing problems -- open up a Hōzz instance and feel it your quadratic problem. Hōzz extends the popular and effective semidefinite programming (SDP) version of the problem, by quickly identifying only relevant additional constraints that will move the solution, we can get competitive solutions to hard problems, and verifiable optima many times.

How we built it

-Garden hose -Bouillon cubes -Eigen C library for fast Cholesky decomposition and determinant computation -GLPK C library for calling the linear programming subproblem -Built a MAX 2-SAT and k-SAT compiler in to produce quadratic programs

Challenges we ran into

Accomplishments that we're proud of

The pun! You get Bouillon cubes and Boolean cubes.

What we learned

What's next for Hōzz

-Implementing more constraint types -Better rounding for inexact solutions -Caching PSD submatrices to more quickly identify problematic cores

Built With

  • garden-hose
  • bouillon-cubes
  • c
  • eigen
  • glpk
  • bouillon-cube
  • c++
Share this project:
×

Updates