Solve Ising model for various graphs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Import"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Populating the interactive namespace from numpy and matplotlib\n",
      "Python: 3.7.6\n",
      "Numba:  0.48.0\n"
     ]
    }
   ],
   "source": [
    "%pylab inline\n",
    "\n",
    "import numpy as np\n",
    "import scipy.sparse as sps\n",
    "\n",
    "import numba\n",
    "from numba import jit\n",
    "import random\n",
    "\n",
    "from gurobipy import *\n",
    "import gurobipy as grb\n",
    "\n",
    "from platform import python_version\n",
    "print('Python:', python_version())\n",
    "print('Numba: ', numba.__version__)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ising energy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "@jit(nopython=True)\n",
    "def get_ising_energy(J, spins):\n",
    "    \"\"\"Returns Ising energy\"\"\"\n",
    "    return - np.dot(spins.T, np.dot(J, spins))[0, 0]\n",
    "\n",
    "\n",
    "@jit(nopython=True)\n",
    "def get_ising_energy_sparse(data, indices, indptr, N, spins):\n",
    "    \"\"\"Returns Ising energy for sparse coupling matrix J\"\"\"\n",
    "    return - np.dot(spins.T, sparse_mat_vec_numba(spins, data, indices, indptr, N))[0, 0]\n",
    "\n",
    "\n",
    "@jit(nopython=True)\n",
    "def sparse_mat_vec_numba(x, data, indices, indptr, N):\n",
    "    \"\"\"Custom sparse matvec product with numba\"\"\"\n",
    "    matvec = np.zeros_like(x)\n",
    "    for i in range(N):\n",
    "        matvec_i = 0.       \n",
    "        for ind_data in range(indptr[i], indptr[i+1]):\n",
    "            j = indices[ind_data]\n",
    "            matvec_i += data[ind_data] * x[j, 0]\n",
    "        matvec[i, 0] = matvec_i            \n",
    "\n",
    "    return matvec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ising methods"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_Ising_model(J, method, connectivity):\n",
    "    \"\"\"\n",
    "    Available methods: \n",
    "    - The Hopfield-Tank neural networks ('hopfield')\n",
    "    - The commercial exact solver Gurobi ('gurobi')\n",
    "    \"\"\"\n",
    "    \n",
    "    additional_data = {}\n",
    "    if method == 'hopfield':\n",
    "        spins, energy_min, prob = hopfield_solver(J, connectivity)\n",
    "        additional_data['prob'] = prob\n",
    "    elif method == 'gurobi':\n",
    "        spins, energy_min, energy_gap, time_gurobi = gurobi_solver(J)\n",
    "        additional_data['energy_gap'] = energy_gap\n",
    "        additional_data['time_gurobi'] = time_gurobi\n",
    "    else:\n",
    "        print('The method is not implemented, please try one of ', help(solve_Ising_model))\n",
    "\n",
    "    return spins, energy_min, additional_data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hopfield solver"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def hopfield_solver(J, connectivity):\n",
    "    \"\"\"Wrapping function for running the Hopfield-Tank algorithm\"\"\"\n",
    "    N = shape(J)[0]\n",
    "    N_iter, dt, tau, u0_IC, N_IC = params_hopfield()\n",
    "    \n",
    "    # number of timesteps to save for studying dynamics\n",
    "    N_time = 1\n",
    "    \n",
    "    N_t = int(N_iter / N_time)\n",
    "    \n",
    "    if connectivity == 'dense':\n",
    "        spins_set, energy_Ising_set = hopfield_net_model(N_IC, u0_IC, J, tau, N_t, dt, N_time, N)\n",
    "    elif connectivity == 'sparse':\n",
    "        J_sparse = sps.csr_matrix(J)\n",
    "        J_data = J_sparse.data\n",
    "        J_indices = J_sparse.indices\n",
    "        J_indptr = J_sparse.indptr\n",
    "        spins_set, energy_Ising_set = hopfield_net_model_sparse(N_IC, u0_IC, J_data, J_indices, \n",
    "                                                                J_indptr, tau, N_t, dt, N_time, N)\n",
    "    \n",
    "    ind_min = np.argmin(energy_Ising_set)\n",
    "    energy_min, spins = energy_Ising_set[-1, ind_min], spins_set[:, -1, ind_min]\n",
    "    prob = len(np.nonzero(energy_Ising_set[-1, :] == energy_min)[0]) / N_IC\n",
    "\n",
    "    return spins, energy_min, prob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Functions for the Hopfield solver on dense coupling matrices J\n",
    "@jit(nopython=True, parallel=True)\n",
    "def hopfield_net_model(N_IC, u0_IC, J, tau, N_t, dt, N_time, N):\n",
    "    \"\"\"Hopfield network for many initial conditions N_IC (dense matrix J)\"\"\"\n",
    "    spins_set_IC = np.zeros((N, N_time, N_IC))\n",
    "    energy_ising_set_IC = np.zeros((N_time, N_IC))\n",
    "\n",
    "    for ind_IC in numba.prange(N_IC):\n",
    "        spins_set, energy_ising_set = hopfield_net(u0_IC[ind_IC, 0], J, tau, N_t, dt, N_time, N)\n",
    "        \n",
    "        spins_set_IC[:, :, ind_IC] = spins_set\n",
    "        energy_ising_set_IC[:, ind_IC] = energy_ising_set\n",
    "\n",
    "    return spins_set_IC, energy_ising_set_IC\n",
    "\n",
    "\n",
    "@jit(nopython=True)\n",
    "def hopfield_net(u0, J, tau, N_t, dt, N_time, N):\n",
    "    \"\"\"Hopfield network for one initial condition (dense matrix J)\"\"\"\n",
    "    spins_set = np.zeros((N, N_time))\n",
    "    energy_ising_set = np.zeros((N_time))\n",
    "\n",
    "    u_t = 0.01 * np.random.random((N, 1))\n",
    "    for ind_time in range(N_time):\n",
    "        u_t, v = hopfield_net_iter(u_t, u0, J, tau, N_t, dt)\n",
    "        spins_set[:, ind_time] = v[:, 0]\n",
    "        energy_ising_set[ind_time] = get_ising_energy(J, np.sign(v))\n",
    "    return spins_set, energy_ising_set\n",
    "\n",
    "\n",
    "@jit(nopython=True)\n",
    "def hopfield_net_iter(u_t, u0, J, tau, N_t, dt):\n",
    "    \"\"\"Running the Hopfield network for N_t iterations (dense matrix J)\"\"\"\n",
    "    for i in range(N_t):\n",
    "        v = np.tanh(u_t / u0)\n",
    "        rhs_u = - u_t / tau + np.dot(J, v)\n",
    "        u_t = u_t + rhs_u * dt\n",
    "    return u_t, v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Functions for the Hopfield solver on sparse coupling matrices J\n",
    "@jit(nopython=True, parallel=True)\n",
    "def hopfield_net_model_sparse(N_IC, u0_IC, J_data, J_indices, J_indptr, tau, N_t, dt, N_time, N):\n",
    "    \"\"\"Hopfield network for many initial conditions N_IC (sparse matrix J)\"\"\"\n",
    "    spins_set_IC = np.zeros((N, N_time, N_IC))\n",
    "    energy_ising_set_IC = np.zeros((N_time, N_IC))\n",
    "\n",
    "    for ind_IC in numba.prange(N_IC):\n",
    "        spins_set, energy_ising_set = hopfield_net_sparse(u0_IC[ind_IC, 0], J_data, J_indices, J_indptr, \n",
    "                                                     tau, N_t, dt, N_time, N)\n",
    "        spins_set_IC[:, :, ind_IC] = spins_set\n",
    "        energy_ising_set_IC[:, ind_IC] = energy_ising_set\n",
    "\n",
    "    return spins_set_IC, energy_ising_set_IC\n",
    "\n",
    "\n",
    "@jit(nopython=True)\n",
    "def hopfield_net_sparse(u0, J_data, J_indices, J_indptr, tau, N_t, dt, N_time, N):\n",
    "    \"\"\"Hopfield network for one initial condition (sparse matrix J)\"\"\"\n",
    "    spins_set = np.zeros((N, N_time))\n",
    "    energy_ising_set = np.zeros((N_time))\n",
    "\n",
    "    u_t = 0.01 * np.random.random((N, 1))\n",
    "    for ind_time in range(N_time):\n",
    "        u_t, v = hopfield_net_iter_sparse(u_t, u0, J_data, J_indices, J_indptr, tau, N_t, dt, N)\n",
    "        spins_set[:, ind_time] = v[:, 0]\n",
    "        energy_ising_set[ind_time] = get_ising_energy_sparse(J_data, J_indices, J_indptr, N, np.sign(v))\n",
    "    \n",
    "    return spins_set, energy_ising_set\n",
    "\n",
    "\n",
    "@jit(nopython=True)\n",
    "def hopfield_net_iter_sparse(u_t, u0, J_data, J_indices, J_indptr, tau, N_t, dt, N):\n",
    "    \"\"\"Running the Hopfield network for N_t iterations (sparse matrix J)\"\"\"\n",
    "    for i in range(N_t):\n",
    "        v = np.tanh(u_t / u0)\n",
    "        rhs_u = - u_t / tau + sparse_mat_vec_numba(v, J_data, J_indices, J_indptr, N)\n",
    "        u_t += rhs_u * dt\n",
    "    \n",
    "    return u_t, v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gurobi solver"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gurobi_solver(J):\n",
    "    \"\"\"Gurobi solver for the Ising model\"\"\"\n",
    "    N = shape(J)[0]\n",
    "    output_flag, time_limit = params_gurobi()\n",
    "\n",
    "    J_boolean, fields, offset = get_J_for_boolean_spins(J)\n",
    "    model_ising = get_ising_model_gurobi(J_boolean, fields, N, output_flag, time_limit)\n",
    "    model_ising.optimize()\n",
    "\n",
    "    energy_min = model_ising.ObjVal + offset\n",
    "    spins = np.zeros((N, 1))\n",
    "    spins[:, 0] = model_ising.X\n",
    "    spins[spins == 0] = -1\n",
    "    energy_gap = model_ising.MIPGap\n",
    "    time_gurobi = model_ising.Runtime\n",
    "\n",
    "    return spins, energy_min, energy_gap, time_gurobi\n",
    "\n",
    "\n",
    "def get_ising_model_gurobi(J_boolean, fields, N, output_flag, time_limit):\n",
    "    \"\"\"Define the Ising model for Gurobi solver\"\"\"\n",
    "    ind_nonzero = list(np.nonzero(np.triu(J_boolean)))\n",
    "\n",
    "    opt_gurobi = grb.Model(name=\"Ising Model\")\n",
    "    opt_gurobi.params.OutputFlag = output_flag\n",
    "    opt_gurobi.params.NonConvex = -1\n",
    "\n",
    "    spins = {}\n",
    "    for i in range(N):\n",
    "        spins[i] = opt_gurobi.addVar(lb=0, ub=1, vtype = GRB.BINARY)\n",
    "    opt_gurobi.update()\n",
    "\n",
    "    energy = 0.\n",
    "    for i, j in zip(ind_nonzero[0], ind_nonzero[1]):\n",
    "        energy += - 2. * J_boolean[i, j] * spins[i] * spins[j]\n",
    "\n",
    "    for i in range(N):\n",
    "        energy += fields[i, 0] * spins[i]\n",
    "\n",
    "    opt_gurobi.setParam(\"TimeLimit\", time_limit)\n",
    "    opt_gurobi.setObjective(energy, GRB.MINIMIZE)\n",
    "    opt_gurobi.update()\n",
    "    \n",
    "    return opt_gurobi\n",
    "\n",
    "\n",
    "def get_J_for_boolean_spins(JJ):\n",
    "    \"\"\"Define the coupling matrix in terms of boolean spins [0, 1]\"\"\"\n",
    "    N = shape(JJ)[0]\n",
    "    fields = np.zeros((N, 1))\n",
    "    J = np.zeros((N, N))\n",
    "    J[:, :] = 4. * JJ\n",
    "    fields[:, 0] = 4. * np.sum(JJ, 0)\n",
    "    offset = - np.sum(JJ)\n",
    "    \n",
    "    return J, fields, offset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ising coupling matrices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_ising_model(N, model, distribution):  \n",
    "    \"\"\"\n",
    "    Available Ising models:\n",
    "    - Sherrington-Kirkpatrick ('sk')\n",
    "    - 3-regular maximum cut ('maxcut')\n",
    "    - Mobius ladder ('mobius')\n",
    "    \n",
    "    Available coupling distributions: \n",
    "    - 'unweighted'\n",
    "    - 'bimodal'\n",
    "    - 'gaussian'\n",
    "    \"\"\"\n",
    "    \n",
    "    if model == 'sk':\n",
    "        J = get_sk_model(N, distribution)\n",
    "    elif model == 'maxcut':\n",
    "        J = get_maxcut_model(N, distribution)\n",
    "    elif model == 'mobius':\n",
    "        J = get_mobius_model(N, distribution)\n",
    "    else:\n",
    "        print('Warning: the Ising model: ', str(model), 'is not supported, consider one of: ')\n",
    "        help(generate_ising_model)\n",
    "\n",
    "    return J"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### SK, Mobius, Maxcut models"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_sk_model(N, distribution):\n",
    "    \"\"\"The Sherrington-Kirkpatrick model\"\"\"\n",
    "    if distribution == 'unweighted':\n",
    "        J = - np.ones((N, N))\n",
    "    elif distribution == 'bimodal':\n",
    "        J = np.random.choice([-1, 1], size=(N, N))\n",
    "    elif distribution == 'gaussian':\n",
    "        J = np.random.normal(0, 1., size=(N, N))\n",
    "    else:\n",
    "        print('Warning: not supported distribution name')\n",
    "\n",
    "    J = np.triu(J) + np.triu(J).T\n",
    "    np.fill_diagonal(J, 0)\n",
    "    \n",
    "    check_model_is_symmetric_and_regular(J, N - 1)\n",
    "    \n",
    "    return J\n",
    "\n",
    "\n",
    "def get_mobius_model(N, distribution):\n",
    "    \"\"\"The Ising model on the Mobius Ladder graph (N is even)\"\"\"\n",
    "    if N % 2 != 0:\n",
    "        print('Warning: N has to be even for the Mobius Ladder graph')\n",
    "\n",
    "    J = np.zeros((N, N))\n",
    "    n = int(N/2)\n",
    "    \n",
    "    if distribution == 'unweighted':\n",
    "        np.fill_diagonal(J[:, n:], -1)\n",
    "        np.fill_diagonal(J[:, 1:], -1)\n",
    "        J[0, -1] = -1\n",
    "    elif distribution == 'bimodal':\n",
    "        J[:, :] = np.diag(np.random.choice([-1, 1], size=(N - n)), n) + np.diag(np.random.choice([-1, 1], size=(N-1)), 1)\n",
    "        J[0, -1] = np.random.choice([-1, 1])\n",
    "    elif distribution == 'gaussian':\n",
    "        J[:, :] = np.diag(np.random.normal(0,1, size=(N - n)), n) + np.diag(np.random.normal(0,1, size=(N-1)), 1)\n",
    "        J[0, -1] = np.random.normal(0, 1)\n",
    "    else:\n",
    "        print('Warning: not supported distribution name')\n",
    "\n",
    "    J = J + J.T\n",
    "    check_model_is_symmetric_and_regular(J, 3)\n",
    "    \n",
    "    return J\n",
    "\n",
    "def get_maxcut_model(N, distribution):\n",
    "    \"\"\"The Ising model on 3-regular graph\"\"\"\n",
    "    J_mobius = get_mobius_model(N, distribution)\n",
    "    J = rewire_regular_graph(J_mobius, int(3 * N))\n",
    "    check_model_is_symmetric_and_regular(J, 3)\n",
    "    \n",
    "    return J\n",
    "\n",
    "\n",
    "def check_model_is_symmetric_and_regular(J, k):\n",
    "    \"\"\"Check if the coupling matrix of the Ising model is symmetric and regular\"\"\"\n",
    "    N = len(J)\n",
    "    if not np.all(np.array([len(np.nonzero(J[:, i])[0]) for i in range(N)]) == k):\n",
    "        print('Warning: the Ising model is NOT of degree %d' % k)\n",
    "    if not np.all(J - J.T == 0):\n",
    "        print('Warning: the Ising model is NOT symmetric')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rewiring procedure"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rewire_two_edges(ind_edges, n_rewirings_done, J, i, i1, i2, j1, j2):\n",
    "    \"\"\"Rewire two given edges of the coupling matrix J\"\"\"\n",
    "    val1 = J[i1, i2]\n",
    "    val2 = J[j1, j2]\n",
    "    \n",
    "    # remove old edges\n",
    "    J[i1, i2], J[i2, i1] = 0, 0\n",
    "    J[j1, j2], J[j2, j1] = 0, 0\n",
    "    \n",
    "    # create two new edges\n",
    "    J[i1, j2], J[j2, i1] = val1, val1\n",
    "    J[j1, i2], J[i2, j1] = val2, val2\n",
    "\n",
    "    ind_edges.pop(i)\n",
    "    n_rewirings_done += 1\n",
    "    rewiring_is_found = True\n",
    "    \n",
    "    return ind_edges, n_rewirings_done, J, rewiring_is_found\n",
    "\n",
    "\n",
    "def rewire_regular_graph(JJ, N_rewirings):\n",
    "    \"\"\"Do N_rewirings for the coupling matrix J\"\"\"\n",
    "    J = np.copy(JJ)\n",
    "    connectivity = len(np.nonzero(J[:, 0])[0])\n",
    "    N_nonzeros = int(connectivity * shape(J)[0] / 2.)\n",
    "\n",
    "    n_rewirings_done = 0\n",
    "    while n_rewirings_done != N_rewirings:\n",
    "        # count nonzeros only for upper triangular J to count all edges ones\n",
    "        ind_nonzeros = np.nonzero(np.triu(J))\n",
    "        ind_edges = list(arange(0,N_nonzeros))\n",
    "        random.shuffle(ind_edges)\n",
    "\n",
    "        kk = 0\n",
    "        while ind_edges:\n",
    "            i1, i2 = ind_nonzeros[0][ind_edges[0]], ind_nonzeros[1][ind_edges[0]]\n",
    "            ind_edges.pop(0)\n",
    "\n",
    "            for i in range(len(ind_edges)):\n",
    "                j1, j2 = ind_nonzeros[0][ind_edges[i]], ind_nonzeros[1][ind_edges[i]]\n",
    "            \n",
    "                # count only non-trivial rewirings leading to a new graph structure\n",
    "                # check that we are not adding any self-interactions (diagonal elements)\n",
    "                # check that the new edges will not coincide with the old edges\n",
    "                cond1 = (len(set([i1, i2, j1, j2])) == 4) and (J[i1, j2] == 0) and (J[j1, i2] == 0)\n",
    "                cond2 = (len(set([i1, i2, j1, j2])) == 4) and (J[i1, j1] == 0) and (J[j2, i2] == 0)\n",
    "\n",
    "                ## choose at random which condition to check first if both are valid (to avoid the bias)\n",
    "                random_number = np.random.choice([-1, 1])\n",
    "                rewiring_is_found = False\n",
    "                if cond1 and cond2 and (random_number == 1):\n",
    "                    ind_edges, n_rewirings_done, J, rewiring_is_found = rewire_two_edges(\n",
    "                                                ind_edges, n_rewirings_done, J, i, i1, i2, j1, j2)\n",
    "                elif cond1 and cond2 and (random_number == -1):\n",
    "                    ind_edges, n_rewirings_done, J, rewiring_is_found = rewire_two_edges(\n",
    "                                                ind_edges, n_rewirings_done, J, i, i1, i2, j2, j1)\n",
    "                elif cond1:\n",
    "                    ind_edges, n_rewirings_done, J, rewiring_is_found = rewire_two_edges(\n",
    "                                                ind_edges, n_rewirings_done, J, i, i1, i2, j1, j2)\n",
    "                elif cond2:\n",
    "                    ind_edges, n_rewirings_done, J, rewiring_is_found = rewire_two_edges(\n",
    "                                                ind_edges, n_rewirings_done, J, i, i1, i2, j2, j1)\n",
    "                \n",
    "                if rewiring_is_found:\n",
    "                    break\n",
    "            kk += 1\n",
    "            \n",
    "            if n_rewirings_done == N_rewirings:\n",
    "                break\n",
    "    \n",
    "    check_model_is_symmetric_and_regular(J, connectivity)\n",
    "    \n",
    "    return J"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Upper bound energy estimation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_ising_energy_upper_bound(J, sparse_connectivity=False, circulant=False):\n",
    "    \"\"\"Calculate the upper bound energy for the coupling matrix J\"\"\"\n",
    "    N = len(J)\n",
    "    spins = np.zeros((N, 1))\n",
    "    \n",
    "    # if the coupling matrix is circulant then the upper bound for the Ising energy is \n",
    "    # evaluated from the DFT matrix, otherwise the J eigenvectors are used\n",
    "    if circulant:\n",
    "        e_vecs = np.real(scipy.linalg.dft(N))\n",
    "        energy_evec = np.zeros((shape(F)[-1]))\n",
    "    else:\n",
    "        _, e_vecs = np.linalg.eigh(J)\n",
    "        energy_evec = np.zeros((shape(e_vecs)[-1]))\n",
    "    \n",
    "    if sparse_connectivity == True:\n",
    "        J_sparse = sps.csr_matrix(J)\n",
    "        J_data = J_sparse.data\n",
    "        J_indices = J_sparse.indices\n",
    "        J_indptr = J_sparse.indptr\n",
    "        \n",
    "        for i in range(len(energy_evec)):\n",
    "            spins[:, 0] = np.sign(e_vecs[:, i])\n",
    "            energy_evec[i] = get_ising_energy_sparse(J_data, J_indices, J_indptr, N, spins)\n",
    "    else:\n",
    "        for i in range(len(energy_evec)):\n",
    "            spins[:, 0] = np.sign(e_vecs[:, i])\n",
    "            energy_evec[i] = get_ising_energy(J, spins)\n",
    "    \n",
    "    min_energy = np.min(energy_evec)\n",
    "    ind_min_energy = np.nonzero(min_energy == energy_evec)[0]\n",
    "\n",
    "    spins[:, 0] = np.sign(e_vecs[:, ind_min_energy[0]])\n",
    "    \n",
    "    return min_energy, spins"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Methods params"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def params_hopfield():\n",
    "    \"\"\"Parameters for the Hopfield method\"\"\"\n",
    "    # number of initial conditions, number of time iterations, time step, linear dissipation\n",
    "    N_IC, N_iter, dt, tau = 100, 1000, 0.9, 1.\n",
    "    u0_IC = 3. * np.ones((N_IC, 1))\n",
    "    params = [N_iter, dt, tau, u0_IC, N_IC]\n",
    "    \n",
    "    return params\n",
    "\n",
    "\n",
    "### gurobi parameters\n",
    "def params_gurobi():\n",
    "    \"\"\"Parameters for the Gurobi solver\"\"\"\n",
    "    # output_flag prints internal gurobi steps if 1, time limit in seconds\n",
    "    output_flag, time_limit = 0, 100\n",
    "    params = [output_flag, time_limit]\n",
    "    \n",
    "    return params"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solve Ising model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "    Available Ising models:\n",
      "    - Sherrington-Kirkpatrick ('sk')\n",
      "    - 3-regular maximum cut ('maxcut')\n",
      "    - Mobius ladder ('mobius')\n",
      "    \n",
      "    Available coupling distributions: \n",
      "    - 'unweighted'\n",
      "    - 'bimodal'\n",
      "    - 'gaussian'\n",
      "    \n",
      "\n",
      "    Available methods: \n",
      "    - The Hopfield-Tank neural networks ('hopfield')\n",
      "    - The commercial exact solver Gurobi ('gurobi')\n",
      "    \n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "<matplotlib.image.AxesImage at 0x6299403d0>"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPsAAAD8CAYAAACxd9IeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAPlUlEQVR4nO3dX4xcZ33G8e9TG0NjhGwnm8jYUeNIFhAh0eBVmpCqqmKqAkU4F0EKQsiqjHzDn/BHgqS9QL1rJETCRYVkxUVWFUGoieooQqDImIveuOySqCRxUrsJckxMvIkSqHIDFr9ezBlnvZ7ZPTtzzpn3Pe/zkVa758yM5zfv63ef98y+54wiAjPrvz+ZdQFm1g0PdrNCeLCbFcKD3awQHuxmhfBgNytEZ4Nd0kckPS/pjKR7u3reuiRdL+mEpFOSnpF0T7V/m6QnJJ2uvm+dda1DkjZIelLS49X2Lkknq1ofkbRp1jUOSdoi6aik56o2vi3VtpX05er/wNOSvifpHSm3bV2dDHZJG4B/AT4K3AR8StJNXTz3OlwEvhoR7wNuBT5X1XgvcDwidgPHq+1U3AOcWrZ9P/BAVevrwIGZVDXat4EfR8R7gQ8wqDu5tpW0A/giMB8R7wc2AHeTdtvWExGtfwG3AT9Ztn0fcF8Xzz1FzceAvwGeB7ZX+7YDz8+6tqqWnQwGyB3A44CAV4GNo9p8xrW+C3gR0Ir9ybUtsAN4CdgGbKza9m9Tbdv1fHU1jR824NC5al+SJN0A3AycBK6LiPMA1fdrZ1fZZR4Evgb8sdq+GngjIi5W2ym18Y3AEvDd6rDjIUmbSbBtI+LXwDeBs8B54LfAIum2bW1dDXaN2JfkOl1J7wR+CHwpIn4363pGkfRx4EJELC7fPeKuqbTxRuCDwHci4mbgTRKYso9SvW+wD9gFvBvYzODwc6VU2ra2rgb7OeD6Zds7gZc7eu7aJL2NwUB/OCIerXa/Iml7dft24MKs6lvmduATkn4FfJ/BVP5BYIukjdV9Umrjc8C5iDhZbR9lMPhTbNsPAy9GxFJE/AF4FPgQ6bZtbV0N9p8Du6t3NDcxeMPjsY6euxZJAg4DpyLiW8tuegzYX/28n8Gx/ExFxH0RsTMibmDQlj+NiE8DJ4C7qrslUStARPwGeEnSe6pde4FnSbBtGUzfb5V0VfV/Ylhrkm27Lh2+8fEx4H+A/wX+cdZvVoyo7y8ZTM3+G3iq+voYg2Ph48Dp6vu2Wde6ou6/Bh6vfr4R+C/gDPDvwNtnXd+yOv8cWKja9z+Aram2LfBPwHPA08C/AW9PuW3rfql6cWbWc15BZ1YID3azQniwmxXCg92sEB7sZoWYarBPciabpIPTPGeXcqoV8qo3p1ohv3pHmXiwT3EmW06NllOtkFe9OdUK+dV7hWmS/RbgTES8EBG/Z7Bsc18zZZlZ0yZeVCPpLuAjEfHZavszwF9ExOfHPeaaa66JzZs3c/bsWQD27Nkz0XN3ZWlpibm5uVmXUVsb9S4uDs61abqv3LbNG/ZVRIw6KYqNo3bWVOssq+pY59IU6LXXXhsuSWSw9JhhgVOUYm0b9pX7KW3z8/Njb5tmsNc6ky0iDgGHACT5f4rZjExzzL7uM9n27NkzWJAvIenyRfrVPkvTyn5yX+Vn4mSPiIuSPg/8hMF1uv41Ip5prDIza9Q003gi4kfAjxqqxcxaNNVgn9Rqb9D5jaC0Le8X91VevFzWrBAzSfah1VLCqZE+91VenOxmhZhpsi83LiWcGulzX+XByW5WiGSSfcgJny/3Vdqc7GaFSC7Zh9ZK+OX7LC1O+DQ52c0KkWyyD62WEk6OtHk2lhYnu1khPNjNCpH8NH7IJ8/ky4deaXCymxUim2Qf8skzeXNfzY6T3awQ2SX7cl5amy/3Vfec7GaFyDrZh7y0Nh8r+8j90h0nu1khepHsQ15am7612t+zsfY42c0K4cFuVoheTeOHvLQ2Xz70ao+T3awQvUz2IS+tzZv7qllOdrNC9DrZl/PS2ny5r5rhZDcrRDHJPuSE707Tbeq+mY6T3awQxSX7UF8TPaXlpm0/f9/6rm1OdrNCFJvsQ6ulQo7JUdIKNJ/KvD5rJruk6yWdkHRK0jOS7qn2b5P0hKTT1fet7ZdrZpOqM42/CHw1It4H3Ap8TtJNwL3A8YjYDRyvts0sUWsO9og4HxG/qH7+P+AUsAPYBxyp7nYEuLOtIrsk6dJXRBARl7ZzM6y/74avM+e+6sK63qCTdANwM3ASuC4izsPgFwJw7ZjHHJS0IGlhaWlpumrNbGK1B7ukdwI/BL4UEb+r+7iIOBQR8xExPzc3N0mNnRqVEk6NfLivxqs12CW9jcFAfzgiHq12vyJpe3X7duBCOyWaWRPqvBsv4DBwKiK+teymx4D91c/7gWPNlzdbTvh8ua+uVOfv7LcDnwF+Kempat8/AP8M/EDSAeAs8Ml2SjSzJqw52CPiP4Fxvxr3NltOmnzyTL7cV2/xclmzQhS/XHY9/Mkz+XLCO9nNiuFkn4A/eSZfJc/GnOxmhfBgNyuEp/FT8CfP5KvEQy8nu1khnOwN8CfP5K2UvnKymxXCyd4wL63NV9/7ysluVggne0u8tDZfK/ulL33mZDcrhJO9ZV5aa6lwspsVwoPdrBCexnfES2vz1ZdDLye7WSGc7B3z0tq85dxXTnazQjjZZ8hLa/OVY1852c0K4WRPgBM+X231TRt972Q3K4STPSE+eSZ/TSVyG/3sZDcrhJM9QT55Jl8pz8ac7GaF8GA3K4Sn8QnzyTP5arpfmuhvJ7tZIZzsGfDJM/0wTV810b9OdrNC1B7skjZIelLS49X2LkknJZ2W9IikTe2VaUMRQUQgCUmXtkcZ3qfufmvXan3VhfUk+z3AqWXb9wMPRMRu4HXgQJOFmVmzag12STuBvwMeqrYF3AEcre5yBLizjQJttHEpMUzt1VJ/1gljA6NmWG3Ouuom+4PA14A/VttXA29ExMVq+xywo+HazKxBaw52SR8HLkTE4vLdI+46MiokHZS0IGlhaWlpwjLbl/tx7Mo0d3Knb+X7L2u9BzOtOsl+O/AJSb8Cvs9g+v4gsEXS8E93O4GXRz04Ig5FxHxEzM/NzTVQsplNYs3BHhH3RcTOiLgBuBv4aUR8GjgB3FXdbT9wrLUqzWxq0/yd/evAVySdYXAMf7iZkmZj1JQqB9P8Cc7S0NWh17pW0EXEz4CfVT+/ANzSfElm1gYvl10htze2Vqu3b0tp+/Z6hro6993LZc0K4WTvsb4lYF9ez8oZSlcnOjnZzQrhZM/cNL/5+3oMnLrV2nvlbU0mvJPdrBBO9sw1kegpXgnVLtdEwjvZzQrhZC+Qr0ufr2lmY052s0J4sJsVwtP4gvm69Pma5NDLyW5WCCe7+br0mRs1QxvFyW5WiE6TfXFx8dKFFixN4xLdCZ++iGB+fn7s7U52s0J0Otj37Nlz2aWfLF3jPnkmt8t22Vuc7GaFmMm78T4BIx9eWtsfTnazQniwmxVipotqPCXMh5fW5s/JblaIZJbLOiXy4KW1+XKymxUimWQfckrkw0tr8+JkNytEcsk+5JTIR9d95f8Tk3GymxUi2WQfajs1nBLNWe3z4de6TxPPY6tzspsVIvlkH2rr5BmnRHvWM2vyDKt9TnazQniwmxWi1mCXtEXSUUnPSTol6TZJ2yQ9Iel09X1r28XCW1dQWe2KN76SShqG/TTKyj5a7b7WjLrJ/m3gxxHxXuADwCngXuB4ROwGjlfbZpaoNQe7pHcBfwUcBoiI30fEG8A+4Eh1tyPAnW0VOc64hHdKpGvcNe2sfXWS/UZgCfiupCclPSRpM3BdRJwHqL5fO+rBkg5KWpC0sLS01FjhZrY+dQb7RuCDwHci4mbgTdYxZY+IQxExHxHzc3NzE5a55nM4JTKx1lVrrT11Bvs54FxEnKy2jzIY/K9I2g5Qfb/QTolm1oQ1B3tE/AZ4SdJ7ql17gWeBx4D91b79wLFWKlwHH6unadS15n1d+u7VXUH3BeBhSZuAF4C/Z/CL4geSDgBngU+2U6KZNaHWYI+Ip4BRHyK1t9lymuXr0qdhtbb3dem74xV0ZoXwYDcrRDZnvU3CU8J8+Lr07XOymxWi18m+nFMiD74ufXuc7GaFKCbZh0pMiVxfa4l91SYnu1khikv2oZJSouvX2nQSr3XV2j72ZRuvzcluVohik32lPqdE17r+RJg+Lotu43U42c0K4WSv9Dkl+sYnz0zGyW5WCA92s0J4Gr+Cp4T58Mkz6+NkNyuEk30VTok8+OSZepzsZoVwstfglMjHuL5y3znZzYrhZF8Hp0Q+nPBXcrKbFcLJPgGnRD7WSvjl+/rOyW5WCCf7FEpOidz45Bknu1kxPNjNCuFpfANKnBLmquSTZ5zsZoVwsjeslJTIXYknzzjZzQrhZG9J31OiT0pZWutkNytErcEu6cuSnpH0tKTvSXqHpF2STko6LekRSZvaLjZHEdGbZOi7YV9JQtIV28u/crTmYJe0A/giMB8R7wc2AHcD9wMPRMRu4HXgQJuFmtl06k7jNwJ/KmkjcBVwHrgDOFrdfgS4s/ny+qMv6VCCcQm//CtHaw72iPg18E3gLINB/ltgEXgjIi5WdzsH7GirSDObXp1p/FZgH7ALeDewGfjoiLuO/HUn6aCkBUkLS0tL09RqZlOoM43/MPBiRCxFxB+AR4EPAVuqaT3ATuDlUQ+OiEMRMR8R83Nzc40UnaNRU0FP5/OVY9/VGexngVslXaXBq9sLPAucAO6q7rMfONZOiWbWhDrH7CcZvBH3C+CX1WMOAV8HviLpDHA1cLjFOnvJCZ+2UW/GjfuzXA5qraCLiG8A31ix+wXglsYrMrNWeLlsAvq6PLOPcl5a6+WyZoVwsick5VSwy7WV8G3OEJzsZoVwsicsh+PA0jV9Xfo2+9rJblYIJ3vCfF36fORwXXonu1khPNjNCuFpfAZmPf2z+tq+Lv00/4aT3awQTvZMpfKmj43W1nXpp+lvJ7tZIZzsmZrkN7xnA7ORyskzTnazQjjZe6JOSjjRZ6vppbXr5WQ3K4STvSdK/tzx3PiY3cxa5cFuVghP43titSmhp/Ptm6Rtu+4HJ7tZIZzsCWorJfqS6CnOUNqqpcnX6mQ3K4STPUE5pMQs5V5/HW0srXWymxXCyZ6ZJk6P7EvC91kbfeVkNyuEkz0zTfyGd8J3q42LVUxy8oyT3awQTvaC+br03WiyTae5Lr2T3awQHuxmhfA03pL8qCIbrc51C8ZxspsVotNkX1xcRJJTI2H+s1wexs3G5ufnxz7GyW5WiK6P2V8F3pT0asfPO6lrGNSci8brXes4cArFt23Tqr76s7G3dz1Nk7QQEePnGgnJqVbIq96caoX86h3F03izQniwmxViFoP90Ayec1I51Qp51ZtTrZBfvVfo/JjdzGbD03izQniwmxXCg92sEB7sZoXwYDcrxP8DJ3SydKTDipoAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "help(generate_ising_model)\n",
    "help(solve_Ising_model)\n",
    "\n",
    "# choose the problem size N, Ising model, and coupling distribution\n",
    "N = 100\n",
    "ising_model = 'mobius'\n",
    "coupling_distribution = 'unweighted'\n",
    "\n",
    "# create coupling matrix\n",
    "J = generate_ising_model(N, ising_model, coupling_distribution)\n",
    "\n",
    "# rewire edges in the coupling matrix if necessary\n",
    "J = rewire_regular_graph(J, N_rewirings=10)\n",
    "\n",
    "spy(J)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "energy_gap = 0.000\n",
      "time_gurobi = 0.065\n",
      "gurobi: Ising energy best = -268.000\n",
      "Upper bound energy = -248.000\n",
      "Coupling matrix is easy to optimise:  False\n"
     ]
    }
   ],
   "source": [
    "solver_method = 'gurobi'\n",
    "connectivity = 'sparse'\n",
    "spins, energy_best, additional_data = solve_Ising_model(J, solver_method, connectivity)\n",
    "\n",
    "for key, item in additional_data.items():\n",
    "    vars()[key] = item\n",
    "    print(key, '= %.3f' % item)\n",
    "print(solver_method + ': Ising energy best = %.3f' % energy_best)\n",
    "    \n",
    "energy_upper_bound, spins_upper_bound = get_ising_energy_upper_bound(J)\n",
    "print('Upper bound energy = %.3f' % energy_upper_bound)\n",
    "\n",
    "if (solver_method == 'gurobi') and (energy_gap == 0):\n",
    "    print('Coupling matrix is easy to optimise: ', energy_upper_bound == energy_best)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7 (tensorflow)",
   "language": "python",
   "name": "tensorflow"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  },
  "toc-autonumbering": false,
  "toc-showcode": false,
  "toc-showmarkdowntxt": false,
  "toc-showtags": false
 },
 "nbformat": 4,
 "nbformat_minor": 4
}