pyBnPLib.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Branch-and-Price Framework\n",
    "\n",
    "- Features:\n",
    "    - Python + Gurobi/etc.\n",
    "    - Self-defined PricingProblem/BranchingRules\n",
    "    - A demo of GraphColoringProblem\n",
    "    \n",
    "- TODOs: \n",
    "    - Unify format\n",
    "    - Add Cut\n",
    "    - Parallel\n",
    "    - Node Visiting Priority"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "# from __future__ import annotations\n",
    "from typing import List, Tuple, Dict, Type, Set\n",
    "import numpy as np\n",
    "import random\n",
    "from gurobipy import *\n",
    "import queue\n",
    "import time\n",
    "from abc import ABC, abstractmethod\n",
    "from timeit import default_timer as timer\n",
    "from enum import Enum\n",
    "from collections import Counter\n",
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### debug utils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# debug utils\n",
    "from importlib import reload\n",
    "import logging\n",
    "import inspect\n",
    "\n",
    "\n",
    "def log(message, logger=logging.error):\n",
    "    func = inspect.currentframe().f_back.f_code\n",
    "    txt = \"{}\\t[{}, {}, {}]\".format(message,\n",
    "        func.co_name, \n",
    "        func.co_filename, \n",
    "        func.co_firstlineno)\n",
    "    logging.debug(txt)\n",
    "    print('@@@@@', txt)\n",
    "    \n",
    "    \n",
    "def _printLP(m):\n",
    "    m.write('tmp.lp')\n",
    "    f = open('tmp.lp', 'r')\n",
    "    for l in f.readlines():\n",
    "        print(l)\n",
    "    print('====================')\n",
    "    \n",
    "\n",
    "def isInt(num):\n",
    "    return (float(num)).is_integer()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### display flags"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# display flags\n",
    "DEBUG = True\n",
    "OUTPUT_LP = True\n",
    "GRB_OUTPUT = False\n",
    "\n",
    "reload(logging)\n",
    "logging.basicConfig(level=logging.DEBUG if DEBUG else logging.INFO, format='%(asctime)s %(levelname)s: %(message)s', datefmt='%I:%M:%S')\n",
    "printGRBLP = lambda m: _printLP(m) if OUTPUT_LP else False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Consts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "MAX_IT = 100000\n",
    "MAX = 1e6\n",
    "EPS = 1e-5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "class VarType(Enum):\n",
    "    REAL = 0\n",
    "    BINARY = 1\n",
    "    INTEGER = 2\n",
    "    \n",
    "\n",
    "class ModelSense(Enum):\n",
    "    MAX = 1\n",
    "    MIN = -1\n",
    "    \n",
    "    \n",
    "class NodeStatus(Enum):\n",
    "    INFEASIBLE = 'inf'\n",
    "    WORSE_BOUND = 'boundWorse' \n",
    "    WORSE_INT = 'intWorse'\n",
    "    LOCAL_OPT = 'localOpt'\n",
    "    GLOBAL_OPT = 'globalOpt'\n",
    "    NOT_SOLVED = 'unsolved'\n",
    "    FRAC = 'frac'\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### abstract model\n",
    "\n",
    "initRowsWithRHS(rowNames:List[str], bs: List[int])\n",
    "\n",
    "addOneColByRowName(self, name:str, vtype:VarType, objCoe:float, rowNames:List[str], rowCoes:List[float], ub:float, instant:bool)\n",
    "\n",
    "setObjByColNames(varNames:List[str], objCoes:List[float])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "# abstract model\n",
    "# min obj\n",
    "# s.t. Ax <= b; x >= 0\n",
    "class AbstractModel(ABC):\n",
    "    def __init__(self, name, sense:Type[ModelSense]):\n",
    "        self.name = name\n",
    "        self.counter = Counter()\n",
    "        self.name2col = {}\n",
    "        self.name2row = {}\n",
    "        self.modelSense = sense\n",
    "        #self.count_namer = lambda name,count: \"{}_{}\".format(name, count)\n",
    "        self.count_namer = lambda name,count: name\n",
    "    \n",
    "        \n",
    "    def modify(col=False, row=False, add=False, remove=False, update=False):\n",
    "        def modify_key(func):\n",
    "            def foo(*args, **kwargs):\n",
    "                if col == row or (add == False and remove == False and update == False):\n",
    "                    print( col == row , (add == False and remove == False and update == False) , args, kwargs)\n",
    "                    raise Exception(\"Decorator Error\")\n",
    "                else:\n",
    "                    self = args[0]\n",
    "                    key = ''\n",
    "                    if len(args) >= 2:\n",
    "                        key = args[1]\n",
    "                    elif 'colName' in kwargs:\n",
    "                        key = kwargs['colName']\n",
    "                    elif 'rowName' in kwargs:\n",
    "                        key = kwargs['rowName']\n",
    "                    else:\n",
    "                        raise Exception('no name')\n",
    "#                     print(key, '()', update, add, remove, self.name)\n",
    "                    name2obj = self.name2col if col else self.name2row\n",
    "                    if add:\n",
    "                        res = func(*args, **kwargs)\n",
    "                        k = (key, col, row)\n",
    "                        self.counter[k] += 1\n",
    "                        \n",
    "                        if self.counter[k] > 1:\n",
    "                            key = self.count_namer(key, self.counter[k])\n",
    "                            log(\"Name Already Exists: {}\".format(key))\n",
    "                        name2obj[key] = res\n",
    "                        return key\n",
    "                    else:\n",
    "                        if key in name2obj:\n",
    "                            func(*args, **kwargs)\n",
    "                            if remove:\n",
    "                                name2obj.pop(key)\n",
    "                                k = (key, col, row)\n",
    "                                self.counter[k]  -= 1\n",
    "                        else:\n",
    "                            log(\"Name Does Not Exist: {}\".format(key))\n",
    "            return foo\n",
    "        return modify_key\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def update_model(self):\n",
    "        pass\n",
    "    \n",
    "\n",
    "#     @modify(row=True, add=True)\n",
    "    @abstractmethod\n",
    "    def addEmptyRowWithRHS(self, rowName:str, rhs:float, instant:bool):\n",
    "        pass\n",
    "        \n",
    "#     @modify(col=True, add=True)\n",
    "    @abstractmethod\n",
    "    def addOneColByRowName(self, colName:str, vtype:VarType, objCoe:float, rowNames:List[str], rowCoes:List[float], ub:float, instant:bool):\n",
    "        pass\n",
    "    \n",
    "#     @modify(row=True, add=True)\n",
    "    @abstractmethod\n",
    "    def addOneRowByColName(self, rowName:str, lhVarNames:List[str], lhCoes:List[float], rhs:float, instant:bool):\n",
    "         pass\n",
    "        \n",
    "#     @modify(col=True, remove=True)        \n",
    "    @abstractmethod\n",
    "    def removeColByName(self, colName:str, instant:bool):\n",
    "        pass\n",
    "        \n",
    "#     @modify(row=True, remove=True)        \n",
    "    @abstractmethod\n",
    "    def removeOneRowByName(self, rowName:str, instant:bool):\n",
    "        pass\n",
    "        \n",
    "        \n",
    "#     @modify(col=True, update=True)    \n",
    "    @abstractmethod\n",
    "    def updateOneObjCoeByColName(self, colName:str, objCoe: float, instant:bool):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    # Default Bulk Modification, could be overriden by customimzed implementation\n",
    "    def initRowsWithRHS(self, rowNames:List[str], bs: List[int]):\n",
    "        for r, b in zip(rowNames, bs):\n",
    "            self.addEmptyRowWithRHS(r, b, False)\n",
    "        self.update_model()\n",
    "        \n",
    "    \n",
    "    def removeColsByNames(self, colNames:List[str]):\n",
    "        for c in colNames:\n",
    "            self.removeColByName(c, False)\n",
    "        self.update_model()\n",
    "            \n",
    "    \n",
    "    def removeRowsByNames(self, rowNames:List[str]):\n",
    "        for r in rowNames:\n",
    "            self.removeOneRowByName(r, False)    \n",
    "        self.update_model()\n",
    "    \n",
    "    \n",
    "    def setObjByColNames(self, varNames:List[str], objCoes:List[float]):\n",
    "        for c, v in zip(objCoes, varNames):\n",
    "            self.updateOneObjCoeByColName(v, c, False)\n",
    "        self.update_model()\n",
    "    # End of Default Bulk Modification\n",
    "    \n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def optimize(self, timeout:int):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def getIsOptimal(self)->bool:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def getObjVal(self)->float:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def getSol(self)->List[Tuple[str, float]]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def getCols(self)->List[str]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def getDualPis(self)->List[Tuple[str,float]]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def printProgram(self):\n",
    "        pass\n",
    "\n",
    "    \n",
    "    @abstractmethod\n",
    "    def printSolution(self):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def getRHS(self)->List[Tuple[str, float]]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    def getNonZeroColsSol(self)->List[Tuple[str, float]]:\n",
    "        return [(c,v) for c, v in self.getSol() if v > 0]\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### GurobiModelSolver"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# abstract model\n",
    "# min obj\n",
    "# s.t. Ax <= b; x >= 0\n",
    "class GurobiModel(AbstractModel):\n",
    "    def __init__(self, name=\"untitled_model\", sense=ModelSense.MIN):\n",
    "        super().__init__(name, sense)\n",
    "        \n",
    "        sense = GRB.MAXIMIZE if sense == ModelSense.MAX else GRB.MINIMIZE\n",
    "        \n",
    "        self.model = Model(name)\n",
    "        self.model.setParam(\"OutputFlag\", GRB_OUTPUT)\n",
    "        self.model.setObjective(0, sense=sense)\n",
    "        self.ineqSense = GRB.GREATER_EQUAL if self.modelSense == ModelSense.MIN else GRB.LESS_EQUAL\n",
    "    \n",
    "    vartype2GRBvtype = dict({VarType.INTEGER: GRB.INTEGER, VarType.REAL: GRB.CONTINUOUS, VarType.BINARY: GRB.BINARY})\n",
    "\n",
    "    def update_model(self):\n",
    "        self.model.update()\n",
    "\n",
    "\n",
    "    @AbstractModel.modify(row=True, add=True)\n",
    "    def addEmptyRowWithRHS(self, rowName:str, rhs:float, instant=True):\n",
    "        res = self.model.addConstr(lhs=0, sense=self.ineqSense, rhs=rhs, name=rowName)\n",
    "        if instant:\n",
    "            self.update_model()\n",
    "        return res\n",
    "        \n",
    "    \n",
    "    @AbstractModel.modify(col=True, add=True)\n",
    "    def addOneColByRowName(self, colName:str, vtype:VarType, objCoe:float, rowNames:List[str], rowCoes:List[float], ub=float('inf'), instant=True):\n",
    "#         print(self.name2row, rowNames)\n",
    "        column = Column(rowCoes, [self.name2row[n] for n in rowNames]) if rowNames else None\n",
    "        ub = GRB.INFINITY if ub==float('inf') else ub\n",
    "        vtype = GurobiModel.vartype2GRBvtype[vtype]\n",
    "        res = self.model.addVar(obj=objCoe, vtype=vtype, name=colName, ub=ub, column=column)\n",
    "        if instant:\n",
    "            self.update_model()\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    @AbstractModel.modify(row=True, add=True)\n",
    "    def addOneRowByColName(self, rowName:str, lhVarNames:List[str], lhCoes:List[float], rhs:float, instant=True):\n",
    "        res = self.model.addConstr(lhs=quicksum( c * self.name2col[n] for c, n in zip(lhCoes, lhVarNames)), sense=self.ineqSense, rhs=rhs, name=rowName)\n",
    "        if instant:\n",
    "            self.update_model()\n",
    "        return res\n",
    "        \n",
    "        \n",
    "    @AbstractModel.modify(col=True, remove=True)\n",
    "    def removeColByName(self, colName:str, instant=True):\n",
    "        res = self.model.remove(self.name2col[colName])\n",
    "        if instant:\n",
    "            self.update_model()\n",
    "        return res\n",
    "\n",
    "        \n",
    "    @AbstractModel.modify(row=True, remove=True)\n",
    "    def removeOneRowByName(self, rowName:str, instant=True):\n",
    "        res = self.model.remove(self.name2row[rowName])\n",
    "        if instant:\n",
    "            self.update_model()\n",
    "        return res\n",
    "\n",
    "\n",
    "    @AbstractModel.modify(col=True, update=True)\n",
    "    def updateOneObjCoeByColName(self, colName:str, objCoe: float, instant=True):\n",
    "        self.name2col[colName].setAttr(GRB.Attr.Obj, objCoe)\n",
    "        if instant:\n",
    "            self.update_model()\n",
    "        \n",
    "\n",
    "    def optimize(self, timeout=0):\n",
    "        if timeout > 0:\n",
    "            self.model.setParam('TimeLimit', timeout)\n",
    "        self.model.optimize()\n",
    "        return self.model.Runtime\n",
    "    \n",
    "    \n",
    "    def getIsOptimal(self)->bool:\n",
    "        return self.model.status == GRB.OPTIMAL\n",
    "    \n",
    "    \n",
    "    def getObjVal(self)->float:\n",
    "        return self.model.objVal\n",
    "    \n",
    "    \n",
    "    def getSol(self)->List[Tuple[str, float]]:\n",
    "        return [(c.varName, c.X) for c in self.model.getVars()]\n",
    "    \n",
    "    \n",
    "    def getCols(self)->List[str]:\n",
    "        return [c.varName for c in self.model.getVars()]\n",
    "    \n",
    "\n",
    "    def getDualPis(self)->List[Tuple[str, float]]:\n",
    "        rows = self.model.getConstrs()\n",
    "        return [(r.constrName,p) for r,p in zip(rows, self.model.getAttr('Pi',  rows))]\n",
    "    \n",
    "\n",
    "    def printProgram(self):\n",
    "        printGRBLP(self.model)\n",
    "\n",
    "    \n",
    "    def printSolution(self):\n",
    "        if not OUTPUT_LP:\n",
    "            return \n",
    "        if self.getIsOptimal():\n",
    "            for c, v in self.getSol():\n",
    "                print('{} = {}'.format(c, v))\n",
    "        else:\n",
    "            print('no optimal sol')\n",
    "    \n",
    "    \n",
    "    def getRHS(self)->List[Tuple[str, float]]:\n",
    "        return [ (r.constrName, r.RHS) for r in self.model.getConstrs() ]\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\ Model ModelX\n",
      "\n",
      "\\ LP format - for model browsing. Use MPS format to capture full model detail.\n",
      "\n",
      "Minimize\n",
      "\n",
      " \n",
      "\n",
      "Subject To\n",
      "\n",
      " row0: >= 1\n",
      "\n",
      " row_a: >= 2.1\n",
      "\n",
      " row_b: >= 2\n",
      "\n",
      " row1: x >= 5\n",
      "\n",
      " row2: 3 x >= 2.1\n",
      "\n",
      "Bounds\n",
      "\n",
      "End\n",
      "\n",
      "====================\n",
      "\\ Model ModelX\n",
      "\n",
      "\\ LP format - for model browsing. Use MPS format to capture full model detail.\n",
      "\n",
      "Minimize\n",
      "\n",
      "  2 x\n",
      "\n",
      "Subject To\n",
      "\n",
      " row_a: >= 2.1\n",
      "\n",
      " row_b: >= 2\n",
      "\n",
      " row1: x >= 5\n",
      "\n",
      " row2: 3 x >= 2.1\n",
      "\n",
      "Bounds\n",
      "\n",
      "End\n",
      "\n",
      "====================\n",
      "\\ Model ModelX\n",
      "\n",
      "\\ LP format - for model browsing. Use MPS format to capture full model detail.\n",
      "\n",
      "Minimize\n",
      "\n",
      "  2 x\n",
      "\n",
      "Subject To\n",
      "\n",
      " row_a: >= 2.1\n",
      "\n",
      " row_b: >= 2\n",
      "\n",
      " row1: x + 2.4 y >= 5\n",
      "\n",
      " row2: 3 x + 2.2 y >= 2.1\n",
      "\n",
      "Bounds\n",
      "\n",
      "End\n",
      "\n",
      "====================\n",
      "\\ Model ModelX\n",
      "\n",
      "\\ LP format - for model browsing. Use MPS format to capture full model detail.\n",
      "\n",
      "Minimize\n",
      "\n",
      " \n",
      "\n",
      "Subject To\n",
      "\n",
      " row_a: >= 2.1\n",
      "\n",
      " row_b: >= 2\n",
      "\n",
      " row1: 2.4 y >= 5\n",
      "\n",
      " row2: 2.2 y >= 2.1\n",
      "\n",
      "Bounds\n",
      "\n",
      "End\n",
      "\n",
      "====================\n",
      "y = 2.0833333333333335\n",
      "0.0\n",
      "[('row1', -0.0), ('row2', 0.0)]\n"
     ]
    }
   ],
   "source": [
    "# Unit Test of GurobiModel\n",
    "m =  GurobiModel(name=\"ModelX\", sense=GRB.MINIMIZE)\n",
    "m.addEmptyRowWithRHS(rowName='row0', rhs=1)\n",
    "\n",
    "m.initRowsWithRHS(rowNames=['row_a', 'row_b'], bs=[2.1, 2])\n",
    "\n",
    "m.addOneColByRowName(colName='x', vtype=VarType.REAL, objCoe=0, rowNames=[], rowCoes=[], ub=float('inf'))\n",
    "m.addOneRowByColName(rowName='row1', lhVarNames=['x'], lhCoes=[1], rhs=5)\n",
    "m.addOneRowByColName(rowName='row2', lhVarNames=['x'], lhCoes=[3], rhs=2.1)\n",
    "m.printProgram()\n",
    "\n",
    "m.removeOneRowByName(rowName='row0')\n",
    "m.updateOneObjCoeByColName(colName='x',objCoe=2)\n",
    "m.printProgram()\n",
    "\n",
    "m.addOneColByRowName(colName='y', vtype=VarType.REAL, objCoe=0, rowNames=['row1', 'row2'], rowCoes=[2.4, 2.2], instant=False)\n",
    "m.update_model()\n",
    "m.printProgram()\n",
    "\n",
    "m.removeColByName(colName='x')\n",
    "m.printProgram()\n",
    "\n",
    "m.removeOneRowByName(rowName='row_a')\n",
    "m.removeOneRowByName(rowName='row_b')\n",
    "m.optimize()\n",
    "m.printSolution()\n",
    "print(m.getObjVal())\n",
    "print(m.getDualPis())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### abstractBranchAndPrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### BnPTreeNode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BnBTreeNode:\n",
    "    def __init__(self, nid:int, decision:str, father:int, status:NodeStatus, bound:float, path=[]):\n",
    "        self.decision = decision\n",
    "        self.nid = nid\n",
    "        self.father = father\n",
    "        self.status = status\n",
    "        self.bound = bound\n",
    "        self.children = []\n",
    "        self.solution = []\n",
    "        self.path = path\n",
    "        if father!= None:\n",
    "            self.path.append(father.nid)\n",
    "        \n",
    "\n",
    "    def convert2another(self, node)->Tuple[List[int], List[int]]:\n",
    "        i = 0\n",
    "        while i < min(len(node.path), len(self.path)) and node.path[i] == self.path[i]:\n",
    "            i += 1\n",
    "        return self.path[i:][::-1], node.path[i:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### abstractHelper"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AbstractHelper(ABC):\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "        \n",
    "        \n",
    "    @abstractmethod\n",
    "    def nameOfCol(self, sth)->str:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def colOfName(self, name:str):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def colCoes(self, sth)->Tuple[List, List[float]]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def objOfCol(self, sth)->float:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def nameOfRow(self, sth)->str:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def rowOfName(self, name:str):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod  \n",
    "    def nameOfBranch(self, sth)->str:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def branchOfName(self, name:str):\n",
    "        pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### abstractMaster"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AbstractMaster(ABC):\n",
    "    def __init__(self, name:str, data, modelClass:Type[AbstractModel], \n",
    "                 modelSense, helper:Type[AbstractHelper]):\n",
    "        \n",
    "        self.name = name\n",
    "        self.data = data\n",
    "        self.model = modelClass(name, modelSense)\n",
    "        self.helper = helper\n",
    "        \n",
    "        self.branch2actions = {}\n",
    "        \n",
    "        self.nameOfCol = helper.nameOfCol\n",
    "        self.colOfName = helper.colOfName\n",
    "        self.colCoes = helper.colCoes\n",
    "        self.objOfCol = helper.objOfCol\n",
    "        self.nameOfRow = helper.nameOfRow\n",
    "        self.rowOfName = helper.rowOfName\n",
    "        self.nameOfBranch = helper.nameOfBranch\n",
    "        self.branchOfName = helper.branchOfName\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def cutCoes(self, sth)->Tuple[List, List[float], float]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def provideRHS(self, sth)->float:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def provideInitRows(self)->List:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def provideInitCols(self)->List:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def onBranchPerformed(self, node:Type[BnBTreeNode]):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def onBranchReverted(self, node:Type[BnBTreeNode]):\n",
    "        pass\n",
    "    \n",
    "    # returns list of branch sth\n",
    "    @abstractmethod\n",
    "    def branchGenerator(self)->List:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    def isIntSol(self):\n",
    "        for c,v in self.model.getSol():\n",
    "            if abs(math.ceil(v) - v) + abs(math.floor(v)-v) > EPS:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "\n",
    "    def add_col(self, col):\n",
    "#         print(col, 'new')\n",
    "        colName = self.nameOfCol(col)\n",
    "        rows, colCoes = self.colCoes(col)\n",
    "        rowNames = [self.nameOfRow(i) for i in rows]\n",
    "        colObj = self.objOfCol(col)\n",
    "            \n",
    "        self.model.addOneColByRowName(colName=colName, vtype=VarType.REAL, \n",
    "                                        objCoe=colObj, rowNames=rowNames, rowCoes=colCoes, \n",
    "                                        ub=float('inf'), instant=False)\n",
    "        \n",
    "    \n",
    "    def build(self):\n",
    "        rows = self.provideInitRows()\n",
    "        rowNames = [self.nameOfRow(r) for r in rows]\n",
    "        bs = [self.provideRHS(r) for r in rows]\n",
    "        self.model.initRowsWithRHS(rowNames=rowNames, bs=bs)\n",
    "        \n",
    "        for col in self.provideInitCols():\n",
    "            self.add_col(col)\n",
    "        \n",
    "        self.model.update_model()\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### abstractPricing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "class AbstractPricing(ABC):\n",
    "    def __init__(self, name, data, helper):\n",
    "        self.name = name\n",
    "        self.data = data\n",
    "        self.nameOfCol = helper.nameOfCol\n",
    "        self.colOfName = helper.colOfName\n",
    "        self.colCoes = helper.colCoes\n",
    "        self.objOfCol = helper.objOfCol\n",
    "        self.nameOfRow = helper.nameOfRow\n",
    "        self.rowOfName = helper.rowOfName\n",
    "        self.nameOfBranch = helper.nameOfBranch\n",
    "        self.branchOfName = helper.branchOfName\n",
    "        self.helper = helper\n",
    "        \n",
    "        self.branch2actions = {}\n",
    "        \n",
    "        \n",
    "    @abstractmethod\n",
    "    def build(self):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def updateByDual(self, sths:List, duals:List[float]):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    # return a col object or None\n",
    "    @abstractmethod\n",
    "    def genAColAndReturn(self):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def onBranchPerformed(self, node:Type[BnBTreeNode]):\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    @abstractmethod\n",
    "    def onBranchReverted(self, node:Type[BnBTreeNode]):\n",
    "        pass\n",
    "    \n",
    "    @abstractmethod\n",
    "    def printProgram(self):\n",
    "        pass\n",
    "    \n",
    "    @abstractmethod\n",
    "    def printSolution(self):\n",
    "        pass\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### B&P"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BnP:\n",
    "    def __init__(self, name:str, data, modelClass:Type[AbstractModel], \n",
    "                masterClass, modelSense: Type[ModelSense], pricingClass, helperClass,\n",
    "                muteColGened=False, muteBranchBegin=False, muteBranchSolved=False, muteNewBranchAdded=False):\n",
    "        \n",
    "        self.muteColGened = muteColGened\n",
    "        self.muteBranchBegin = muteBranchBegin\n",
    "        self.muteBranchSolved = muteBranchSolved\n",
    "        self.muteNewBranchAdded = muteNewBranchAdded\n",
    "        \n",
    "        \n",
    "        self.name = name\n",
    "        self.data = data\n",
    "        self.modelSense = modelSense\n",
    "        self.helper = helperClass(data)\n",
    "        \n",
    "        self.master = masterClass(name+\"-Master\", data, modelClass, modelSense, self.helper)\n",
    "        self.pricing = pricingClass(name+\"-Pricing\", data, self.helper)\n",
    "        self.root = BnBTreeNode(decision='ROOT', nid=0, father=None, status=NodeStatus.NOT_SOLVED, bound=float('inf'), path=[0])\n",
    "        self.nodes = [self.root]\n",
    "        self.nodeCount = 0\n",
    "        self.queue = []\n",
    "        self.incumbent = float('inf') if self.modelSense == ModelSense.MIN else -float('inf') \n",
    "        \n",
    "        self.best_incumbent = 0\n",
    "        self.quitEarly = False\n",
    "\n",
    "        helper = self.helper\n",
    "        self.nameOfCol = helper.nameOfCol\n",
    "        self.colOfName = helper.colOfName\n",
    "        self.colCoes = helper.colCoes\n",
    "        self.objOfCol = helper.objOfCol\n",
    "        self.nameOfRow = helper.nameOfRow\n",
    "        self.rowOfName = helper.rowOfName\n",
    "        self.nameOfBranch = helper.nameOfBranch\n",
    "        self.branchOfName = helper.branchOfName\n",
    "        \n",
    "        self.numCols = 0\n",
    "\n",
    "\n",
    "    def newNodeIndex(self)->int:\n",
    "        self.nodeCount += 1 \n",
    "        return self.nodeCount\n",
    "\n",
    "\n",
    "    def performBranch(self, node:Type[BnBTreeNode]):\n",
    "        res = self.master.onBranchPerformed(node)\n",
    "        res = self.pricing.onBranchPerformed(node)\n",
    "\n",
    "\n",
    "    def revertBranch(self, node:Type[BnBTreeNode]):\n",
    "        self.master.onBranchReverted(node)\n",
    "        self.pricing.onBranchReverted(node)\n",
    "\n",
    "\n",
    "    def newBranch(self, decision:str, curNode:Type[BnBTreeNode]):\n",
    "        for nid in curNode.path:\n",
    "            if self.nodes[nid].decision == decision:\n",
    "                return\n",
    "            \n",
    "        dup = set()\n",
    "        for n in self.nodes:\n",
    "            r = str(sorted([self.nodes[x].decision for x in n.path]))\n",
    "#             print(r)\n",
    "            assert r not in dup\n",
    "            dup.add(r)\n",
    "            \n",
    "        node = BnBTreeNode(nid=self.newNodeIndex(), decision=decision, father=curNode, status=NodeStatus.NOT_SOLVED, bound=curNode.bound)\n",
    "        \n",
    "        node.path = curNode.path + [node.nid]\n",
    "        curNode.children.append(node)\n",
    "        self.nodes.append(node)\n",
    "        self.queue.append(node)\n",
    "        self.logNewBranchAdded(decision)\n",
    "\n",
    "\n",
    "    def gcsolve(self):\n",
    "        for it in range(MAX_IT):\n",
    "            if not self.genACol():\n",
    "                break\n",
    "            \n",
    "            if not self.master.model.getIsOptimal():\n",
    "                log('master not good')\n",
    "                break\n",
    "\n",
    "        return self.master.model.getIsOptimal()\n",
    "    \n",
    "\n",
    "    def visitANode(self, node:Type[BnBTreeNode], last:Type[BnBTreeNode]):\n",
    "        toRevert, toPerform = last.convert2another(node)\n",
    "        self.logBranchBegin(node, toRevert, toPerform)\n",
    "        \n",
    "        for b in toRevert:\n",
    "            self.revertBranch(self.nodes[b])\n",
    "        for b in toPerform:\n",
    "            self.performBranch(self.nodes[b])\n",
    "        \n",
    "\n",
    "        if self.gcsolve():\n",
    "            bound = self.master.model.getObjVal() \n",
    "            sol = self.master.model.getSol()\n",
    "            node.bound = bound\n",
    "                \n",
    "            if self.modelSense == ModelSense.MIN and bound > self.incumbent or \\\n",
    "                self.modelSense == ModelSense.MAX and bound < self.incumbent :\n",
    "                \n",
    "#                 node.bound = bound\n",
    "                if self.master.isIntSol():\n",
    "                    node.status = NodeStatus.WORSE_INT\n",
    "                else:\n",
    "                    node.ststus = NodeStatus.WORSE_BOUND\n",
    "            else:\n",
    "                if self.master.isIntSol():\n",
    "                    self.incumbent = bound\n",
    "                    node.bound = bound\n",
    "                    node.status = NodeStatus.LOCAL_OPT\n",
    "                    node.solution = sol\n",
    "                    \n",
    "                    if bound == self.best_incumbent:\n",
    "                        self.quitEarly = True\n",
    "                    \n",
    "                else:\n",
    "                    node.status = NodeStatus.FRAC\n",
    "                    \n",
    "                    if node.decision == 'ROOT':\n",
    "                        self.best_incumbent = math.floor(bound) if self.modelSense == ModelSense.MAX else math.ceil(bound)\n",
    "                    \n",
    "                    for branch in self.master.branchGenerator():\n",
    "                        self.newBranch( self.nameOfBranch(branch), node )\n",
    "        else:\n",
    "            node.status = NodeStatus.INFEASIBLE\n",
    "            node.bound = float('inf')\n",
    "            \n",
    "        self.logBranchSolved(node)\n",
    "\n",
    "\n",
    "\n",
    "    def branchAndPrice(self):\n",
    "        self.master.build()\n",
    "        self.pricing.build()\n",
    "        self.queue.append(self.root)\n",
    "        last = self.root\n",
    "        while self.queue:\n",
    "            \n",
    "            if self.quitEarly:\n",
    "                break\n",
    "            \n",
    "            node = self.queue.pop()\n",
    "            self.visitANode(node, last)\n",
    "            last = node\n",
    "            \n",
    "            self.numCols = max(self.numCols, len(self.master.model.getCols()))\n",
    "            \n",
    "        for l in self.nodes:\n",
    "            if l.bound == self.incumbent:\n",
    "                l.status = NodeStatus.GLOBAL_OPT\n",
    "          \n",
    "\n",
    "    def genACol(self):\n",
    "        self.master.model.optimize()\n",
    "        colAddedFlag = False\n",
    "        \n",
    "        if self.master.model.getIsOptimal():\n",
    "            rows, pis = [], []\n",
    "            for rowName, pi in self.master.model.getDualPis():\n",
    "                rows.append(self.rowOfName(rowName))\n",
    "                pis.append(pi)\n",
    "\n",
    "            self.pricing.updateByDual(rows, pis)\n",
    "            newCol = self.pricing.genAColAndReturn()\n",
    "            \n",
    "            if not (newCol is None):\n",
    "                self.master.add_col(newCol)\n",
    "                colAddedFlag = True\n",
    "\n",
    "            self.logColGened(rows, pis, newCol)\n",
    "        \n",
    "        return colAddedFlag\n",
    "\n",
    "\n",
    "    def dispMasterSolution(self):\n",
    "        cols, sol = self.master.getNonZeroColsSol()\n",
    "        self.dispASolution(cols, sol)\n",
    "        \n",
    "    \n",
    "    def logColGened(self, rows, pis, newCol):\n",
    "        if self.muteColGened:\n",
    "            return\n",
    "        \n",
    "        print(\"Pis:\" + '; '.join([\"[{}]: {} \".format(r,p) for r,p in zip(rows, pis)]))\n",
    "        if newCol != None:\n",
    "            print('New Col Generated: ', newCol)        \n",
    "#             self.pricing.printProgram()\n",
    "#         self.pricing.printSolution()\n",
    "    \n",
    "    \n",
    "    def logBranchBegin(self, node, toRevert, toPerform):\n",
    "        if self.muteBranchBegin:\n",
    "            return\n",
    "        print('\\n\\n', ''.join(['-']*64), '\\n')\n",
    "        print('Current Branch Path: ', [self.nodes[nid].decision for nid in node.path], '\\n\\n')\n",
    "#         print('nRevert', [self.nodes[nid].decision for nid in toRevert], toRevert)\n",
    "#         print('nPerform', [self.nodes[nid].decision for nid in toPerform])\n",
    "#         print('Master Before: ') \n",
    "#         self.master.model.printProgram()\n",
    "        \n",
    "        \n",
    "    def logBranchSolved(self, node):\n",
    "        if self.muteBranchSolved:\n",
    "            return\n",
    "        print('\\n\\n\\n')\n",
    "        print('Master After: ')\n",
    "        self.master.model.printProgram()\n",
    "        print('\\n\\n')\n",
    "        print(\"#cols: \",len(self.master.model.getCols()))\n",
    "        print('current incumbent: ', self.incumbent)\n",
    "        if self.master.model.getIsOptimal():\n",
    "            print('Solution: ')\n",
    "            self.master.model.printSolution()\n",
    "            print('current bound: ', self.master.model.getObjVal(), '\\n\\n')\n",
    "        \n",
    "    \n",
    "    def logNewBranchAdded(self, newBranch):\n",
    "        if self.muteNewBranchAdded:\n",
    "            return\n",
    "        print('\\n\\nnew branch: {}'.format(newBranch))\n",
    "\n",
    "\n",
    "    \n",
    "    def drawBnPTree(self):\n",
    "        g = nx.DiGraph()\n",
    "        for node in self.nodes:\n",
    "            if node.father != None:\n",
    "                g.add_edge(node.father.nid, node.nid)\n",
    "      \n",
    "        cm = {}  \n",
    "        cm[NodeStatus.INFEASIBLE.value] = 'red'\n",
    "        cm[NodeStatus.WORSE_BOUND.value] = 'purple'\n",
    "        cm[NodeStatus.WORSE_INT.value] = 'yellow'\n",
    "        cm[NodeStatus.LOCAL_OPT.value] = 'blue'\n",
    "        cm[NodeStatus.GLOBAL_OPT.value] = 'green'\n",
    "        cm[NodeStatus.FRAC.value] = 'orange'\n",
    "        cm[NodeStatus.NOT_SOLVED.value] = 'gray'\n",
    "    \n",
    "        colorMap = ['black'] * len(self.nodes)\n",
    "        #print(g.nodes(), self.nodeStatus)\n",
    "        for node in self.nodes:\n",
    "            colorMap[node.nid] = cm[node.status.value]\n",
    "            \n",
    "        colorMap[0] = 'royalblue'\n",
    "\n",
    "        nx.draw(g, pos=nx.spring_layout(g), node_color = colorMap)\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### UnitTest GCP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "class GCPHelper(AbstractHelper):\n",
    "    def nameOfCol(self, sth:Set[int])->str:\n",
    "        return 'X'+str(sth)\n",
    "        \n",
    "        \n",
    "    def colOfName(self, name:str):\n",
    "        return eval(name[1:])\n",
    "    \n",
    "    \n",
    "    def colCoes(self, sth:Set[int])->Tuple[List[int], List[float]]:\n",
    "        rows = []\n",
    "        rowCoes = []\n",
    "        for v in sth:\n",
    "            rows.append(v)\n",
    "            rowCoes.append(1)\n",
    "        return rows, rowCoes\n",
    "            \n",
    "    \n",
    "    def objOfCol(self, sth:Set[int])->float:\n",
    "        return 1\n",
    "    \n",
    "    \n",
    "    def nameOfRow(self, sth:int)->str:\n",
    "        return \"N\"+str(sth)\n",
    "    \n",
    "    \n",
    "    def rowOfName(self, name:str):\n",
    "        return int(name[1:])\n",
    "    \n",
    "    \n",
    "    # branch: same, node_i, node_j\n",
    "    def nameOfBranch(self, sth:Tuple[bool, int, int])->str:\n",
    "        return str(sth)\n",
    "    \n",
    "    \n",
    "    def branchOfName(self, name:str):\n",
    "        if name == 'ROOT':\n",
    "            return None\n",
    "        return eval(name)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data = (N, edges)\n",
    "class GCPMaster(AbstractMaster):\n",
    "    def cutCoes(self, sth)->Tuple[List, List[float], float]:\n",
    "        pass\n",
    "    \n",
    "    \n",
    "    def provideRHS(self, sth:str)->float:\n",
    "        return 1\n",
    "    \n",
    "    \n",
    "    def provideInitRows(self)->List[int]:\n",
    "        return list(range(self.data[0]))\n",
    "    \n",
    "    \n",
    "    def provideInitCols(self)->List[Set[int]]:\n",
    "        return [set([v]) for v in range(self.data[0])]\n",
    "    \n",
    "    \n",
    "    def onBranchPerformed(self, node:Type[BnBTreeNode]):\n",
    "        self.branch2actions[node.nid] = []\n",
    "        branchDecisionSth = self.branchOfName(node.decision)\n",
    "        if branchDecisionSth is None:\n",
    "            return\n",
    "        same, node_i, node_j = branchDecisionSth\n",
    "        for vname in self.model.getCols():\n",
    "            col = self.colOfName(vname)\n",
    "            flag = False\n",
    "            if not same:\n",
    "                if node_i in col and node_j in col:\n",
    "                    flag = True\n",
    "            else:\n",
    "                if node_i in col and node_j not in col or node_i not in col and node_j in col:\n",
    "                    flag = True\n",
    "                    \n",
    "            if flag:\n",
    "#                 print(vname, 'remove')\n",
    "                self.model.removeColByName(vname)\n",
    "                self.branch2actions[node.nid].append(('delCol', col))\n",
    "    \n",
    "    \n",
    "    def onBranchReverted(self, node:Type[BnBTreeNode]): \n",
    "        for action, col in self.branch2actions[node.nid]:\n",
    "            if action == 'delCol':\n",
    "#                 print(col, 'readd')\n",
    "                self.add_col(col)\n",
    "        self.branch2actions.pop(node.nid)\n",
    "        \n",
    "\n",
    "    def branchGenerator(self)->List[Tuple[bool, int, int]]:\n",
    "        sets = []\n",
    "        for c,v in self.model.getSol():\n",
    "            if abs(math.ceil(v) - v) + abs(math.floor(v)-v) > EPS:\n",
    "                sets.append(self.colOfName(c))\n",
    "        for i in range(len(sets)):\n",
    "            for j in range(1, len(sets)):\n",
    "                S1 = set(sets[i])\n",
    "                S2 = set(sets[j])\n",
    "                S12 = S1.intersection(S2)\n",
    "                D = (S1-S12) if len(S1 - S12) > 0 else (S2-S12)\n",
    "                if len(D) > 0 and len(S12) > 0:\n",
    "                    n1 = D.pop()\n",
    "                    n2 = S12.pop()\n",
    "                    return [(False, n1, n2), (True, n1, n2)]\n",
    "        return []\n",
    "                    \n",
    "                \n",
    "        \n",
    "    \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "# data = (N, edges)\n",
    "\n",
    "def buildGRBModelGenIndSet(name, N, edges, helper):\n",
    "    m = GurobiModel(name)\n",
    "    for i in range(N):\n",
    "        m.addOneColByRowName(colName=helper.nameOfRow(i), \n",
    "                             vtype=VarType.BINARY, objCoe=-1, \n",
    "                             rowNames=[], rowCoes=[], ub=float('inf'))\n",
    "    for s,t in edges:\n",
    "        m.addOneRowByColName(rowName=str((s,t)), lhVarNames=[helper.nameOfRow(s), helper.nameOfRow(t)], lhCoes=[-1, -1], rhs=-1)\n",
    "    return m\n",
    "    \n",
    "\n",
    "class GCPPricing(AbstractPricing):\n",
    "    def build(self):\n",
    "        N, edges = self.data\n",
    "        self.model = buildGRBModelGenIndSet(self.name, N, edges, self.helper)\n",
    "    \n",
    "    \n",
    "    def updateByDual(self, sths:List[int], duals:List[float]):\n",
    "        self.model.setObjByColNames( [self.nameOfRow(s) for s in sths] , [-d for d in duals])\n",
    "    \n",
    "    \n",
    "    # return a col object or None\n",
    "    def genAColAndReturn(self):\n",
    "        self.model.optimize()\n",
    "        col = set([self.rowOfName(vname) for vname, val in self.model.getSol() if abs(val-1) < EPS])\n",
    "        if -self.model.getObjVal() > self.objOfCol(col) + EPS:\n",
    "            return col\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    \n",
    "    def onBranchPerformed(self, node:Type[BnBTreeNode]):\n",
    "        self.branch2actions[node.nid] = []\n",
    "        branchDecisionSth = self.branchOfName(node.decision)\n",
    "        if branchDecisionSth is None:\n",
    "            return\n",
    "        same, node_i, node_j = branchDecisionSth\n",
    "        rowName = 'row[{}]'.format(str(branchDecisionSth))\n",
    "        if same:\n",
    "            self.model.addOneRowByColName(rowName=rowName+'1',\n",
    "                                         lhVarNames=[self.nameOfRow(node_i), self.nameOfRow(node_j)],\n",
    "                                         lhCoes=[1, -1], rhs=0)\n",
    "            self.model.addOneRowByColName(rowName=rowName+'2',\n",
    "                                         lhVarNames=[self.nameOfRow(node_i), self.nameOfRow(node_j)],\n",
    "                                         lhCoes=[-1, 1], rhs=0)\n",
    "            self.branch2actions[node.nid].append( ('addRow', rowName+'1') )\n",
    "            self.branch2actions[node.nid].append( ('addRow', rowName+'2') )\n",
    "        else:\n",
    "            self.model.addOneRowByColName(rowName=rowName,\n",
    "                             lhVarNames=[self.nameOfRow(node_i), self.nameOfRow(node_j)],\n",
    "                             lhCoes=[-1, -1], rhs=-1)\n",
    "            self.branch2actions[node.nid].append( ('addRow', rowName) )\n",
    "            \n",
    "#         print('add_branch', node.decision, self.branch2actions[node.nid])\n",
    "        \n",
    "    \n",
    "    \n",
    "    def onBranchReverted(self, node:Type[BnBTreeNode]):\n",
    "#         print('remove_branch', node.decision, self.branch2actions[node.nid])\n",
    "        for action, rowName in self.branch2actions[node.nid]:\n",
    "            if action == 'addRow':\n",
    "                self.model.removeOneRowByName(rowName)\n",
    "        self.branch2actions.pop(node.nid)\n",
    "        \n",
    "        \n",
    "    def printProgram(self):\n",
    "        self.model.printProgram()\n",
    "        \n",
    "        \n",
    "    def printSolution(self):\n",
    "        self.model.printSolution()\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_sol(N, edges, sol:List[Tuple[str, float]], helper:Type[AbstractHelper]):\n",
    "    cm = [-1] * N\n",
    "    colors = ['red', 'purple', 'yellow', 'blue', 'green', 'orange', 'gray', 'black']\n",
    "    count = 0\n",
    "    for vname, val in sol:\n",
    "        if val > 0:\n",
    "            for n in helper.colOfName(vname):\n",
    "                cm[n] = colors[count]\n",
    "            count += 1 \n",
    "    g = nx.Graph()\n",
    "    for i in range(N):\n",
    "        g.add_node(i, label='xxx')\n",
    "    for s,t in edges:\n",
    "        g.add_edge(s,t)\n",
    "        \n",
    "    if count > len(colors):\n",
    "        print('WARNING: TOO MUCH COLORS')\n",
    "    \n",
    "        \n",
    "    \n",
    "    nx.draw(g, pos=nx.spring_layout(g), node_color = cm, with_labels=True,)\n",
    "    \n",
    "            \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "def all_ind_set(N, edges):\n",
    "    def b(i):\n",
    "        if i == 0:\n",
    "            return ['']\n",
    "        else:\n",
    "            res = []\n",
    "            for x in b(i-1):\n",
    "                res.append('0'+x)\n",
    "                res.append('1'+x)\n",
    "            return res\n",
    "        \n",
    "    res = []\n",
    "    for b in b(N):\n",
    "        flag = True\n",
    "        node_set = set([i for i, inside in zip(range(N), b) if inside=='1'])\n",
    "        for s,t in edges:\n",
    "            if s in node_set and t in node_set:\n",
    "                flag = False\n",
    "        if flag and len(node_set) > 0:\n",
    "            res.append(node_set)\n",
    "        \n",
    "    return res\n",
    "            \n",
    "    \n",
    "\n",
    "def solve_MIP(N, edges, cols):\n",
    "    model = Model('gcp-mip')\n",
    "    model.setParam(\"OutputFlag\", GRB_OUTPUT)\n",
    "    \n",
    "    rows = []\n",
    "    for i in range(N):\n",
    "        rows.append( model.addConstr(lhs=0, rhs=1, sense=GRB.GREATER_EQUAL) )\n",
    "    model.update()\n",
    "    \n",
    "    for c in cols:\n",
    "#         print(c, rows)\n",
    "        rs = [rows[i] for i in c]\n",
    "        x = model.addVar(name='X_{}'.format(c), obj=1, vtype=GRB.BINARY, column=Column([1] * len(rs),rs))\n",
    "    model.update()\n",
    "#     printGRBLP(model)\n",
    "    \n",
    "    model.optimize()\n",
    "    print('mip-solve:', model.objVal) #[v.varName for v in model.getVars() if v.X > 0])\n",
    "    return model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve_bnp(N, edeges, output=False):\n",
    "    if not output:\n",
    "        gcpBnP = BnP(name=\"GCP\", data=(N, edges), modelClass=GurobiModel, modelSense=ModelSense.MIN,\n",
    "                masterClass=GCPMaster, pricingClass=GCPPricing, helperClass=GCPHelper,\n",
    "                muteColGened=True, muteBranchBegin=True, muteBranchSolved=True, muteNewBranchAdded=True)\n",
    "    else:\n",
    "        gcpBnP = BnP(name=\"GCP\", data=(N, edges), modelClass=GurobiModel, modelSense=ModelSense.MIN,\n",
    "                masterClass=GCPMaster, pricingClass=GCPPricing, helperClass=GCPHelper)\n",
    "    gcpBnP.branchAndPrice()\n",
    "    gcpBnP.drawBnPTree()\n",
    "    for n in gcpBnP.nodes:\n",
    "        if n.status==NodeStatus.GLOBAL_OPT:\n",
    "            print('bnp-solve: ', n.bound) # n.solution)\n",
    "    return gcpBnP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "# N = 5\n",
    "# edges = [(0,1), (1,2), (2,3), (3,4), (4,0)]\n",
    "\n",
    "\n",
    "N = 3\n",
    "M = int(N*N * 0.45)\n",
    "edges = set() \n",
    "\n",
    "\n",
    "for i in range(M):\n",
    "    a = random.randint(0, N-1)\n",
    "    b = random.randint(0, N-1)\n",
    "    if a == b:\n",
    "        continue\n",
    "    edges.add((min(a, b), max(a, b)))\n",
    "    \n",
    "# print(edges)\n",
    "\n",
    "# N = 25\n",
    "# edges = [(0, 3), (0, 4), (0, 8), (0, 9), (0, 10), (0, 15), (0, 18), (0, 20), (0, 21), (0, 23), (1, 3), (1, 6), (1, 8), (1, 12), (1, 14), (1, 15), (1, 16), (1, 17), (1, 18), (1, 19), (1, 20), (1, 23), (1, 24), (2, 5), (2, 8), (2, 9), (2, 17), (2, 19), (2, 20), (2, 22), (2, 24), (3, 5), (3, 6), (3, 8), (3, 9), (3, 10), (3, 11), (3, 16), (3, 18), (3, 19), (3, 20), (3, 22), (3, 24), (4, 5), (4, 11), (4, 15), (4, 16), (4, 17), (4, 19), (4, 24), (5, 9), (5, 12), (5, 15), (5, 18), (5, 20), (5, 24), (6, 7), (6, 8), (6, 12), (6, 15), (6, 17), (6, 18), (6, 24), (7, 10), (7, 11), (7, 12), (7, 15), (7, 16), (7, 18), (7, 19), (7, 20), (7, 23), (8, 12), (8, 13), (8, 18), (8, 19), (8, 20), (8, 22), (9, 12), (9, 16), (9, 18), (9, 19), (9, 20), (9, 22), (9, 23), (9, 24), (10, 13), (10, 14), (10, 15), (10, 17), (10, 20), (10, 22), (10, 23), (11, 12), (11, 14), (11, 16), (11, 20), (11, 21), (11, 22), (11, 24), (12, 13), (12, 15), (12, 17), (12, 18), (12, 20), (13, 14), (13, 15), (13, 16), (13, 17), (13, 18), (13, 19), (13, 22), (13, 23), (13, 24), (14, 17), (14, 21), (14, 24), (15, 17), (15, 18), (16, 18), (16, 21), (16, 23), (16, 24), (17, 19), (17, 20), (17, 21), (18, 22), (19, 23), (20, 21), (20, 24), (21, 22), (22, 23), (22, 24)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 ModelSense.MIN 1.0 -inf ?\n",
      "bnp-solve:  1.0\n",
      "4\n",
      "5\n",
      "mip-solve: 2.0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(0.020459066000057646, 0.00032024000006458664, 0.0015295260000129929)"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAEiklEQVR4nO3VMQEAIAzAMMC/5+ECjiYK+nXPzCwAiDi/AwDgJeMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AFOMDIMX4AEgxPgBSjA+AlAvcsAZYWWSZ3AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "ta = timer()\n",
    "m1 = solve_bnp(N, edges)\n",
    "tb = timer()\n",
    "\n",
    "print(m1.numCols)\n",
    "\n",
    "cols = all_ind_set(N, edges)\n",
    "\n",
    "print(len(cols))\n",
    "\n",
    "tc = timer()\n",
    "m2 = solve_MIP(N, edges, cols)\n",
    "td = timer()\n",
    "\n",
    "tb-ta, tc-tb, td-tc\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAOMUlEQVR4nO3dfYxddZ3H8c+0dNpOH5iVWnE3iCSIrUXA0mLiH5bqoomBpBTjAxu0YJTgZmgbg4RmgyRbWEGIBoyV/uMTGivRKIKauhFNSgIq4iqtDUZbbUxaJVqBzpR2OrN/XMTSzvTxnrnDfF+vZJLmnnNvv/+98zvn3vPrGh4eHg4AFDGp0wMAwFgSPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+AEoRPgBKET4AShE+gInsL39JbrstmT8/Of30ZO7c5HWvS264IfnDHzo9XUd0DQ8PD3d6CADabMeOZNWq5HvfS7q6koGBlx7v7k4mTUre8pbkM59J3vjGzszZAcIHMNH86lfJ0qXJ3/+eHDhw9PNnzEi+/e3k3/+9+dnGAeEDmEi2bUsWLkx27z6+9/X0JA8/nFx0UTNzjSPu8QFMJO95T/LMM4e9/Nkki5JMTbJipPf19yeXXXZsK8SXOeEDmCiefDLZvDkZGjrs0L8m+a8k1xzp/QMDyUMPNTTc+CF8ABPFpz+d7Ns34qHlSZYlOe1I73/22eT22xsYbHwRPoCJYHg4+drXTv5S5eOPJ3/+c3tmGqeED2Ai2LMnGRw8+c+ZOjXZufPkP2ccEz6AieD555PJk9vzWXv3tudzxinhA5gIZs8e9f7ecRkaSnp7T/5zxjHhA5gIpkxJzj571MODSfYmOfDC394XXjtMV1dy5plNTDhuCB/ARPHxjyczZ454aG2S6Uk+meS+F/699tCTuruTj3ykdZ9vAvPkFoCJYs+e1kOo+/tP7P3TpiW/+U3y2te2dazxxooPYKKYMSO58cbW48eO1/TpyfLlEz56iRUfwMQyPJxceWXywAPHvvKbPj05//zkJz9pXe6c4Kz4ACaSrq7kq19NPvShVtCO8BOHoa6u7OnqyuDSpa0HVBeIXiJ8ABPPpEnJ3Xcnjz2WfOADrQDOnt26BDp9ejJrVjJtWiYtW5Zb3/rW/M+b39y6v1eES50AE90zzyQ/+lHy9NOtR5q94hXJkiXJ3LnZvn17LrzwwjzxxBN5zWte0+lJx4TwARR3yy23ZMuWLfnGN77R6VHGhPABFNff3583vOEN+cIXvpClS5d2epzGuccHUFxPT0/uuuuuXH/99Rlsx4OuxznhAyDLly/P3Llzs27duk6P0jiXOgFIkmzevDkXX3xxtmzZkle+8pWdHqcxwgfAi1avXp09e/Zk/fr1nR6lMcIHwIt2796d+fPn57vf/W4WLVrU6XEa4R4fAC/q7e3Nrbfemr6+vgwNDXV6nEYIHwAvsWLFihw4cCD33Xdfp0dphEudABzmsccey+WXX56tW7dm9uzZnR6nrYQPgBFdffXVmTNnTj71qU91epS2Ej4ARrRr164sWLAgmzZtyrx58zo9Ttu4xwfAiF71qldlzZo1WblyZSbSGkn4ABhVX19fduzYkQceeKDTo7SNS50AHNEPf/jDXHvttdmyZUumTYB9+6z4ADiiSy65JBdccEHuvPPOTo/SFlZ8ABzVtm3bsmjRovzyl7/MGWec0elxTorwAXBMPvGJT2Tr1q3ZsGFDp0c5KcIHwDHp7+/P/Pnz86UvfSkXX3xxp8c5Ye7xAXBMJsqGtcIHwDG74oorMmfOnHz+85/v9CgnzKVOAI7Lk08+maVLl75sN6wVPgCO28qVK7N3797ce++9nR7luAkfAMdt9+7dmTdvXh566KFceOGFnR7nuLjHB8Bx6+3tzdq1a9PX1/eye46n8AFwQq655prs37//ZbdhrUudAJywRx99NFdccUW2bt2aWbNmdXqcYyJ8AJyUFStWZO7cubnjjjs6PcoxET4ATsrOnTtz7rnn5pFHHsnrX//6To9zVO7xAXBSTj/99Nx0001ZtWrVy+KLLsIHwEnr6+vL9u3b8+CDD3Z6lKNyqROAtti4cWOuu+66bN68eVxvWGvFB0BbvOMd78h5552Xu+66q9OjHJEVHwBt8/vf/z6LFy8e1xvWCh8AbXXzzTfnqaeeyte//vVOjzIi4QOgrf6xYe2Xv/zlLFmypNPjHMY9PgDaqqenJ3feeWf6+vrG5Ya1wgdA27373e/OnDlzxuW2RS51AtCIX//613n729+eLVu2ZM6BA8n69cmmTcnf/pb09CRnn51ce22yePGYziV8ADTmjve9L+989NGcv3Nn0tWV7N37z4OTJiXTpiVnnJGsWZNcdVXrnIYJHwDN2LAhw1dfneGBgaPfV+vpSS69NPnKV5Lu7kbHEj4A2u8730ne//5kYODY3zN9evKudyX339/oys+XWwBorz/9KbnyyhGj99cklyeZkeTMJF87+ODAQPKDHyTr1jU6nvAB0F6f+1xy4MCIh/4zSXeSXUm+muS6JJsPPmHPnuS225IGL0a61AlA++zfn8ydm+zefdihPUn+JcmTSc554bWrkvxbkk8efOLMma1LpW97WyMjWvEB0D7f//6oq72nkkzOP6OXJOfnkBVfkjz3XHL33Y2MlwgfAO20bVuyb9+Ih55Lcuohr52a5NmRTv7tb9s710GED4D22bMnGeUxZTOTPHPIa88kmTXSyf397Z3rIMIHQPvMnp1MmTLioXOSDCY5eC33f0kWjHTyrBFz2BbCB0D7LFiQnHLKiIdmJFme5Oa0vujySJLvpPUFl5eYPDl505saG1H4AGifJUtaq75RfC7JQJK5Sd6fZF1GWPFNnZqsXNnUhMIHQBtNmpR87GOtR5CN4BVJvp3Wiu+PSa4c6aSzzkoWLmxuxMY+GYCarrmmtWo7ET09ydq17Z3nEMIHQHv19iYbNyYzZhzf+3p6ktWrk2XLmpnrBZ7cAkAzfvrT5J3vbG1FdPB2RIf6x/ZEa9a0/hremkj4AGjOrl2th07fc0/rcWbPHvRz9Z6eZGgoueyy5IYbxmxDWuEDoHmDg8mDDya/+EXy9NOt3+mdeWby3vcmp502pqMIHwCl+HILAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApQgfAKUIHwClCB8ApYx9+H73u2TVquSCC5Kzzkrmz08uuST51reSwcExHweAWrqGh4eHx+R/euSR5MYbk8cfTw4cSPbvf+nxWbOSKVOS669Pbrop6e4ek7EAqGVswvfFLyYf/WgyMHD0c6dPT849N9m4MentbXw0AGppPnz335988IPHFr1/6O5Ozjsv2bQpmTq1udkAKKfZe3w7d44YveeTfCjJmUlmJXlTku8ffMK+fcnmzcnNNzc6HgD1NBu+9euTERaUg0nOSPKTJH9P8t9J3pNk+8EnDQwk69Ylzz/f6IgA1NJc+AYHk7vvTvbuPezQjCS3JHntCwNcmuSsJI8feuLwcPLNbzY2IgD1NBe+H/+4dcnyGOxK8lSSBYceeO655J572jsXAKU1F74dO5KhoaOetj/JfyT5YJJ5o30OALRJc+Hr7z9q+IaSXJWkO8lnRzvJPT4A2uiUxj751FOTyZNHPTyc1jc7dyX5XpIpo504c2bbRwOgrubCt3Bh6wkto7guyW+S/G+S6aOdNGlSsnhx+2cDoKxmf8C+cGHyxBOHvfyHtL7ROTUvLe+9ad3ve1FPT/Lww8lFFzU2IgC1NBu+DRuSD384efbZE3v/OeckW7cmXV3tnQuAspr9AfvllyennXbEe32j6ulJbr9d9ABoq2bD193d+j1fb2/rft2x6ulp7eSwbFljowFQ09jszrB9e7JkSfLXv7Z+lD6aU05pbU10663J6tWNjwVAPWO3H9/AQOue3+23J3/8Y+txZPv2tS6DTp3a+gboVVe1NqmdN+JP2QHgpI1d+A72858nP/tZsnt3a/+9V786ufTSZMaMMR8FgFo6Ez4A6JBmv9wCAOOM8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUIrwAVCK8AFQivABUMr/AyRxKZBUNe3yAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "for node in m1.nodes:\n",
    "    if node.status == NodeStatus.GLOBAL_OPT:\n",
    "        plot_sol(N, edges, sol=node.solution, helper=GCPHelper((N, edges)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# for x in range(1000):\n",
    "#     N = 10\n",
    "#     M = int(N*N * 0.25)\n",
    "#     edges = set() \n",
    "#     for i in range(M):\n",
    "#         a = random.randint(0, N-1)\n",
    "#         b = random.randint(0, N-1)\n",
    "#         if a == b:\n",
    "#             continue\n",
    "#         edges.add((min(a, b), max(a, b)))\n",
    "#     gcpBnP = BnP(name=\"GCP\", data=(N, edges), modelClass=GurobiModel, modelSense=GRB.MINIMIZE,\n",
    "#                 masterClass=GCPMaster, pricingClass=GCPPricing, helperClass=GCPHelper,\n",
    "#                 muteColGened=True, muteBranchBegin=True, muteBranchSolved=True, muteNewBranchAdded=True)\n",
    "#     gcpBnP.branchAndPrice()\n",
    "   \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}