Hacking Tensorflow into a sudoku solver

Google’s Tensorflow has seen great success in deep learning applications. How can we repurpose its functionality for mixed-integer optimization? Specifically, can we use its optimization capabilities to solve a sudoku?

Better trained weights every iteration

Optimal square foot gardening with companion planting and mixed-integer programming

Some plants grow better together, and some do not. Let’s optimize for it!

Training a classifier on 1 billion data points in under 3.5 minutes on a laptop.

No GPU involved. It’s privacy-preserving, and uses parallel computing.

Mixed Integer-Convex Nonlinear Programming: forcing integrality by convex regularization

We use a sequence of regularization terms to force a decision variable in a convex problem to have an integer value. In this way, we can do Mixed Integer-Convex Nonlinear Programming (MICNLP) using convex optimization only, without using branch-and-bound methods.

SequentialConvexRelaxation.jl

I released the Julia package SequentialConvexRelaxation.jl, which applies a series of convex optimizations as a heuristic optimization method for nonconvex problems that can be described as convex problems with additional bilinear equality constraints. The software can be found here.

ZernikePolynomials.jl

ZernikePolynomials.jl is a package for working with Zernike polynomials in Julia. I give a short introduction to the package. The software can be found here.

Speeding up Sequential Convex Relaxation: Random Rescaling

Sometimes the Sequential Convex Relaxation (SCR) approach to solving optimization problems with bilinear matrix equalities can suffer from slow convergence. Here we offer a strategy that can accelerate the convergence.

An example converge plot of the SCR algorithm

Solving a sudoku with convex optimization

A sudoku puzzle is a nice example of integer programming where the goal is to find a solution that satisfies the rules of the game. We’re going to try and solve sudokus using convex optimization.

An unsolved sudoku

Solving a travelling salesman problem with convex optimization

The travelling salesman problem is a mixed-integer programming problem where the objective is to find the best route past a selection of cities. Here we attempt to solve it in a non-traditional way: by using convex optimization.

Training neural networks with convex optimization

Finding the optimal weights for a neural network is a non-convex optimization. However, is there a convex heuristic to find the optimal weights?

Better trained weights every iteration