Nonlinear_Integer_Prob.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Subproblem_Quad_IP():\n",
    "    def __init__(self, obj_coeff, constraints_coeff):\n",
    "        self.n_dim = len(obj_coeff)\n",
    "        self.obj_coeff = obj_coeff\n",
    "        self.constraints_coeff = constraints_coeff\n",
    "        \n",
    "    def compute_obj(self, lamd):\n",
    "        self.relaxed_obj_coeff = []\n",
    "        for i in range(self.n_dim):\n",
    "            self.relaxed_obj_coeff.append({'quad': obj_coeff[i], 'linear': (lamd * constraints_coeff[:,i]).sum()})\n",
    "            \n",
    "    def solve(self):\n",
    "        self.opt_solution = np.zeros(self.n_dim)\n",
    "        for i in range(self.n_dim):\n",
    "            coeff = self.relaxed_obj_coeff[i]\n",
    "            self.opt_solution[i] = round(-1 * coeff['linear']/ (2 *coeff['quad']))\n",
    "        self.opt_solution = np.maximum(0, self.opt_solution)\n",
    "    \n",
    "    def solve_surrogate(self, dualproblem):\n",
    "        self.compute_costfun(dualproblem)\n",
    "        for i in range(self.n_dim):\n",
    "            coeff = self.relaxed_obj_coeff[i]\n",
    "            self.opt_solution[i] = round(-1 * coeff['linear'] / (2 *coeff['quad']))\n",
    "            new_obj_value \n",
    "    \n",
    "    def compute_costfun(self, dualproblem):\n",
    "        costfun_orig = np.dot((self.opt_solution * self.opt_solution).T, obj_coeff)\n",
    "        cost_constraints = 0\n",
    "        for i in range(len(dualproblem.lamd)):\n",
    "            cost_constraints += self.lamd[i] * (np.dot(self.opt_solution.T, self.constraints_coeff[i,:]) - rhs[i])\n",
    "        return costfun_orig + cost_constraints\n",
    "    \n",
    "    def report(self, i):\n",
    "        print(\"iteration times:\", i)\n",
    "        print(\"current solution:\", self.opt_solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Dual_Problem():\n",
    "    def __init__(self, n_constraints):\n",
    "        self.lamd = np.zeros(n_constraints)\n",
    "        self.m, self.r, self.alpha = 10, 0.01, 1.0\n",
    "        self.step_init, self.step, self.iteration_time = 0.0, 0.0, 0\n",
    "        self.subgradients_init = np.zeros(n_constraints)\n",
    "        self.subgradients = np.zeros(n_constraints)\n",
    "        self.subg_norm_iterations, self.step_iterations, self.costfun_iterations = [], [], []\n",
    "    \n",
    "    def compute_subgradients(self, subproblem_qip):\n",
    "        for i in range(len(self.lamd)):\n",
    "            self.subgradients[i] = np.dot(subproblem_qip.opt_solution.T, subproblem_qip.constraints_coeff[i,:]) - rhs[i]\n",
    "        if self.iteration_time == 0:\n",
    "            self.subgradients_init = self.subgradients.copy()\n",
    "                 \n",
    "    def compute_stepsize(self, subproblem_qip):\n",
    "        if self.iteration_time == 0:\n",
    "            self.step_init = (417 - self.compute_costfun(subproblem_qip))/ np.linalg.norm(self.subgradients_init)**2\n",
    "        else:\n",
    "            p = 1 - 1/(self.iteration_time ** self.r)\n",
    "            self.alpha = self.alpha * (1 - 1/(self.m * self.iteration_time ** p))\n",
    "            if np.linalg.norm(self.subgradients) != 0:\n",
    "                self.step = self.alpha * self.step_init * np.linalg.norm(self.subgradients_init) / np.linalg.norm(self.subgradients)\n",
    "            else:\n",
    "                self.step = 0\n",
    "                print(\"subgradients = 0\")\n",
    "        self.step_iterations.append(self.step)\n",
    "        \n",
    "    def compute_stepsize_simple(self, subproblem_qip):\n",
    "        self.step = (417 - self.compute_costfun(subproblem_qip))/ np.linalg.norm(self.subgradients)**2\n",
    "        self.step_iterations.append(self.step)\n",
    "        if self.iteration_time == 0:\n",
    "            self.step_init = self.step\n",
    "        \n",
    "    def update_lamd(self):\n",
    "        if self.iteration_time == 0:\n",
    "            self.lamd = self.lamd + self.step_init * self.subgradients_init\n",
    "        else:\n",
    "            self.lamd = self.lamd + self.step * self.subgradients\n",
    "        self.lamd = np.maximum(self.lamd, 0)\n",
    "        self.iteration_time += 1\n",
    "        \n",
    "    def compute_costfun(self, subproblem):\n",
    "        costfun_orig = np.dot((subproblem.opt_solution * subproblem.opt_solution).T, obj_coeff)\n",
    "        cost_constraints = 0\n",
    "        for i in range(len(self.lamd)):\n",
    "            cost_constraints += self.lamd[i] * (np.dot(subproblem.opt_solution.T, subproblem.constraints_coeff[i,:]) - rhs[i])\n",
    "        return costfun_orig + cost_constraints    \n",
    "    \n",
    "    def report(self, subproblem):\n",
    "        print(\"subgradients:\", self.subgradients)\n",
    "        print(\"lamd: \", self.lamd)\n",
    "        print(\"step:\", self.step, \"  dual problem cost function:\", self.compute_costfun(subproblem))\n",
    "        print(\"\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the dimension of decision variables: 6\n",
      "coefficients of objective function: [0.5 0.1 0.5 0.1 0.5 0.1]\n",
      "coefficients of constraints: [[-1.   0.2 -1.   0.2 -1.   0.2]\n",
      " [-5.   1.  -5.   1.  -5.   1. ]]\n",
      "relaxed problem objective coefficients: [{'quad': 0.5, 'linear': 0.0}, {'quad': 0.1, 'linear': 0.0}, {'quad': 0.5, 'linear': 0.0}, {'quad': 0.1, 'linear': 0.0}, {'quad': 0.5, 'linear': 0.0}, {'quad': 0.1, 'linear': 0.0}]\n",
      "optimal solution: [0. 0. 0. 0. 0. 0.]\n"
     ]
    }
   ],
   "source": [
    "n_constraints = 2\n",
    "lamd = np.zeros(n_constraints)\n",
    "obj_coeff = np.array([0.5, 0.1, 0.5, 0.1, 0.5, 0.1])\n",
    "constraints_coeff = np.array([[-1, 0.2, -1, 0.2, -1, 0.2], [-5, 1, -5, 1, -5, 1]])\n",
    "rhs = [-48, -250]\n",
    "subproblem = Subproblem_Quad_IP(obj_coeff, constraints_coeff)\n",
    "subproblem.compute_obj(lamd)\n",
    "print(\"the dimension of decision variables:\", subproblem.n_dim)\n",
    "print(\"coefficients of objective function:\", subproblem.obj_coeff)\n",
    "print(\"coefficients of constraints:\", subproblem.constraints_coeff)\n",
    "print(\"relaxed problem objective coefficients:\", subproblem.relaxed_obj_coeff)\n",
    "subproblem.solve()\n",
    "print(\"optimal solution:\", subproblem.opt_solution)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "subgradients =  [ 48. 250.]\n",
      "step size =  0.0\n",
      "the cost function of dual problem: 0.0\n",
      "lamd =  [0.30886982 1.60869699]\n"
     ]
    }
   ],
   "source": [
    "dualproblem = Dual_Problem(n_constraints)\n",
    "dualproblem.compute_subgradients(subproblem)\n",
    "print(\"subgradients = \", dualproblem.subgradients_init)\n",
    "dualproblem.compute_stepsize(subproblem)\n",
    "print(\"step size = \", dualproblem.step)\n",
    "print(\"the cost function of dual problem:\", dualproblem.compute_costfun(subproblem))\n",
    "dualproblem.update_lamd()\n",
    "print(\"lamd = \", dualproblem.lamd)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "iteration times: 0\n",
      "current solution: [8. 0. 8. 0. 8. 0.]\n",
      "subgradients: [ 24. 130.]\n",
      "lamd:  [0.57652021 3.05846994]\n",
      "step: 0.011152099606251643   dual problem cost function: 507.4375776889173\n",
      "\n",
      "iteration times: 1\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.57652021 4.38601905]\n",
      "step: 0.13275491057053726   dual problem cost function: 427.860190485308\n",
      "\n",
      "iteration times: 2\n",
      "current solution: [23.  0. 23.  0. 23.  0.]\n",
      "subgradients: [-21. -95.]\n",
      "lamd:  [0.3182915  3.21784154]\n",
      "step: 0.012296605353891887   dual problem cost function: 481.1209321881044\n",
      "\n",
      "iteration times: 3\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.3182915 4.2968436]\n",
      "step: 0.10790020647193525   dual problem cost function: 426.96843604630425\n",
      "\n",
      "iteration times: 4\n",
      "current solution: [22.  0. 22.  0. 22.  0.]\n",
      "subgradients: [-18. -80.]\n",
      "lamd:  [0.10452194 3.34675668]\n",
      "step: 0.011876086557484162   dual problem cost function: 456.378070624652\n",
      "\n",
      "iteration times: 5\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         2.59258738]\n",
      "step: 0.1508338603591606   dual problem cost function: 420.5370631088206\n",
      "\n",
      "iteration times: 6\n",
      "current solution: [13.  0. 13.  0. 13.  0.]\n",
      "subgradients: [ 9. 55.]\n",
      "lamd:  [0.12834975 3.37694693]\n",
      "step: 0.014261082778073923   dual problem cost function: 440.3872289116715\n",
      "\n",
      "iteration times: 7\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         2.76071661]\n",
      "step: 0.12324606470114713   dual problem cost function: 419.6964169623789\n",
      "\n",
      "iteration times: 8\n",
      "current solution: [14.  0. 14.  0. 14.  0.]\n",
      "subgradients: [ 6. 40.]\n",
      "lamd:  [0.09644038 3.40365247]\n",
      "step: 0.0160733966834144   dual problem cost function: 430.7247412750347\n",
      "\n",
      "iteration times: 9\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         2.89907314]\n",
      "step: 0.10091586769338569   dual problem cost function: 419.00463431803064\n",
      "\n",
      "iteration times: 10\n",
      "current solution: [14.  0. 14.  0. 14.  0.]\n",
      "subgradients: [ 6. 40.]\n",
      "lamd:  [0.07904203 3.42601998]\n",
      "step: 0.01317367103203818   dual problem cost function: 431.51505126416913\n",
      "\n",
      "iteration times: 11\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.01209928]\n",
      "step: 0.08278413988511067   dual problem cost function: 418.4395036087508\n",
      "\n",
      "iteration times: 12\n",
      "current solution: [15.  0. 15.  0. 15.  0.]\n",
      "subgradients: [ 3. 25.]\n",
      "lamd:  [0.05212306 3.44645807]\n",
      "step: 0.017374351796285697   dual problem cost function: 423.8178209950911\n",
      "\n",
      "iteration times: 13\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.10634767]\n",
      "step: 0.0680220806933682   dual problem cost function: 417.9682616515493\n",
      "\n",
      "iteration times: 14\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.46608614]\n",
      "step: 0.035973847239638305   dual problem cost function: 418.6608614208652\n",
      "\n",
      "iteration times: 15\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.18620799]\n",
      "step: 0.05597563104653451   dual problem cost function: 417.5689600657307\n",
      "\n",
      "iteration times: 16\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.48244371]\n",
      "step: 0.029623571915969687   dual problem cost function: 418.8244370601355\n",
      "\n",
      "iteration times: 17\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.25181771]\n",
      "step: 0.04612519842114796   dual problem cost function: 417.240911430461\n",
      "\n",
      "iteration times: 18\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.49607849]\n",
      "step: 0.024426077611069456   dual problem cost function: 418.96078490018505\n",
      "\n",
      "iteration times: 19\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.30579946]\n",
      "step: 0.03805580537959983   dual problem cost function: 416.9710026843975\n",
      "\n",
      "iteration times: 20\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.13288813]\n",
      "step: 0.03458226563279269   dual problem cost function: 417.8355593252173\n",
      "\n",
      "iteration times: 21\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.31618157]\n",
      "step: 0.018329343969610064   dual problem cost function: 417.16181574652643\n",
      "\n",
      "iteration times: 22\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.17327609]\n",
      "step: 0.028581097597151838   dual problem cost function: 417.6336195666656\n",
      "\n",
      "iteration times: 23\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.32484266]\n",
      "step: 0.015156657047077884   dual problem cost function: 417.2484265713766\n",
      "\n",
      "iteration times: 24\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.20661227]\n",
      "step: 0.023646077157579187   dual problem cost function: 417.4669386432512\n",
      "\n",
      "iteration times: 25\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.33207088]\n",
      "step: 0.012545860395682566   dual problem cost function: 417.3207087530659\n",
      "\n",
      "iteration times: 26\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.23415874]\n",
      "step: 0.01958242702638845   dual problem cost function: 417.3292062991268\n",
      "\n",
      "iteration times: 27\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.        3.3381058]\n",
      "step: 0.01039470582336909   dual problem cost function: 417.3810579840834\n",
      "\n",
      "iteration times: 28\n",
      "current solution: [17.  0. 17.  0. 17.  0.]\n",
      "subgradients: [-3. -5.]\n",
      "lamd:  [0.         3.25694489]\n",
      "step: 0.016232182327586744   dual problem cost function: 417.21527556614797\n",
      "\n",
      "iteration times: 29\n",
      "current solution: [16.  0. 16.  0. 16.  0.]\n",
      "subgradients: [ 0. 10.]\n",
      "lamd:  [0.         3.34314659]\n",
      "step: 0.008620170785293467   dual problem cost function: 417.4314659462334\n",
      "\n",
      "optimal solution =  [16.  0. 16.  0. 16.  0.]\n",
      "subgradients =  [ 0. 10.]\n"
     ]
    }
   ],
   "source": [
    "max_itertimes = 30\n",
    "for i in range(max_itertimes):\n",
    "    subproblem.compute_obj(dualproblem.lamd)\n",
    "    subproblem.solve()\n",
    "    subproblem.report(i)\n",
    "    dualproblem.compute_subgradients(subproblem)\n",
    "    dualproblem.compute_stepsize(subproblem)\n",
    "    dualproblem.update_lamd()\n",
    "    dualproblem.report(subproblem)\n",
    "print(\"optimal solution = \", subproblem.opt_solution)\n",
    "print(\"subgradients = \", dualproblem.subgradients)"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}