How to perform discrete optimization of functions over matrices?

Question

I would like to optimize over all 30 by 30 matrices with entries that are 0 or 1. My objective function is the determinant. One way to do this would be some sort of stochastic gradient descent or simulated annealing.

I looked at scipy.optimize but it doesn't seem to support this sort of optimization as far as I can tell. scipy.optimize.basinhopping looked very tempting but it seems to require continuous variables.

Are there any tools in Python for this sort of general discrete optimization?

Answer 1

I don't know of any straight-forward method for discrete optimization in scipy. One alternative is using the simanneal package from pip or github, which allows you to introduce your own move function, such that you can restrict it to moves within your domain:

import random
import numpy as np
import simanneal

class BinaryAnnealer(simanneal.Annealer):

    def move(self):
        # choose a random entry in the matrix
        i = random.randrange(self.state.size)
        # flip the entry 0 <=> 1
        self.state.flat[i] = 1 - self.state.flat[i]

    def energy(self):
        # evaluate the function to minimize
        return -np.linalg.det(self.state)

matrix = np.zeros((5, 5))
opt = BinaryAnnealer(matrix)
print(opt.anneal())