{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3eb0337f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3ff6f670",
   "metadata": {},
   "outputs": [],
   "source": [
    "class InputError(Exception):\n",
    "    pass\n",
    "\n",
    "file_path = 'sol_mrr_lp.txt'\n",
    "def read_input(file_path):\n",
    "    try:\n",
    "        with open(file_path, 'r') as file:\n",
    "            lines = file.readlines()\n",
    "            if (lines[0].strip() != \"y\"):\n",
    "                raise InputError(\"File has wrong format, first line should be 'y'.\")\n",
    "            i = 1\n",
    "            y_variables = {}\n",
    "            while (i < len(lines) and lines[i].strip() != \"z\"):\n",
    "                split_line = lines[i].strip().split()\n",
    "                if (len(split_line) != 2):\n",
    "                    raise InputError(\"File has wrong format, lines after 'y' but before 'z' should contain the index of the y variable and its value\")\n",
    "                if int(split_line[0]) in y_variables:\n",
    "                    raise InputError(\"File has wrong format, multiple lines with same index.\")\n",
    "                y_variables[int(split_line[0])] = int(split_line[1])\n",
    "                i += 1\n",
    "            # now lines[i] == \"z\"\n",
    "            i += 1\n",
    "            z_variables = {}\n",
    "            while (i < len(lines) and lines[i].strip() != \"x\"):\n",
    "                split_line = lines[i].strip().split()\n",
    "                if (len(split_line) != 2):\n",
    "                    raise InputError(\"File has wrong format, lines after 'z' but before 'x' should contain the index of the y variable and its value\")\n",
    "                if int(split_line[0]) in z_variables:\n",
    "                    raise InputError(\"File has wrong format, multiple lines with same index.\")\n",
    "                z_variables[int(split_line[0])] = int(split_line[1])\n",
    "                i += 1\n",
    "            # now lines[i] == \"x\"\n",
    "            i += 1\n",
    "            x_variables = {}\n",
    "            while (i < len(lines) and lines[i].strip() != \"v\"):\n",
    "                split_line = lines[i].strip().split()\n",
    "                if (len(split_line) != 2):\n",
    "                    raise InputError(\"File has wrong format, lines after 'x' but before 'v' should contain the index of the y variable and its value\")\n",
    "                if int(split_line[0]) in x_variables:\n",
    "                    raise InputError(\"File has wrong format, multiple lines with same index.\")\n",
    "                x_variables[int(split_line[0])] = int(split_line[1])\n",
    "                i += 1\n",
    "            # now lines[i] == \"v\"\n",
    "            i += 1\n",
    "            v_variables = {}\n",
    "            while (i < len(lines) and lines[i].strip() != \"w\"):\n",
    "                split_line = lines[i].strip().split()\n",
    "                if (len(split_line) != 3):\n",
    "                    raise InputError(\"File has wrong format, lines after 'v' should contain two indices and one value.\")\n",
    "                if int(split_line[0]) not in v_variables:\n",
    "                    v_variables[int(split_line[0])] = {}\n",
    "                v_variables[int(split_line[0])][int(split_line[1])] = int(split_line[2])\n",
    "                i += 1\n",
    "            # now lines[i] == \"w\"\n",
    "            i += 1\n",
    "            w_variables = {}\n",
    "            while (i < len(lines)):\n",
    "                split_line = lines[i].strip().split()\n",
    "                if (len(split_line) != 3):\n",
    "                    raise InputError(\"File has wrong format, lines after 'w' should contain two indices and one value.\")\n",
    "                if int(split_line[0]) not in w_variables:\n",
    "                    w_variables[int(split_line[0])] = {}\n",
    "                w_variables[int(split_line[0])][int(split_line[1])] = int(split_line[2])\n",
    "                i += 1\n",
    "            return [y_variables, z_variables, x_variables, v_variables, w_variables]\n",
    "    except FileNotFoundError:\n",
    "        print(\"File not found.\")\n",
    "    except IOError:\n",
    "        print(\"An error occurred while reading the file.\")\n",
    "    except InputError as error:\n",
    "        print(\"InputError: \" + str(error))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5f698159",
   "metadata": {},
   "outputs": [],
   "source": [
    "def value(variable_dict, *indices):\n",
    "    if indices[0] not in variable_dict:\n",
    "        return 0\n",
    "    if len(indices) == 1:\n",
    "        return variable_dict[indices[0]]\n",
    "    if indices[1] not in variable_dict[indices[0]]:\n",
    "        return 0\n",
    "    return variable_dict[indices[0]][indices[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b05362bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "class InfeasibilityError(Exception):\n",
    "    pass\n",
    "\n",
    "def check_variables(variables):\n",
    "    try:\n",
    "        y_variables, z_variables, x_variables, v_variables, w_variables = variables\n",
    "        N = 4000\n",
    "        beta_inverse = 400 # 1/beta\n",
    "        a = 199\n",
    "        for y in y_variables.values():\n",
    "            if y < 0:\n",
    "                raise InfeasibilityError(\"Negative y variable.\")\n",
    "        for row in v_variables.values():\n",
    "            for v in row.values():\n",
    "                if v < 0:\n",
    "                    raise InfeasibilityError(\"Negative v variable.\")\n",
    "        for i in w_variables.keys():\n",
    "            for j in w_variables[i].keys():\n",
    "                if w_variables[i][j] < 0:\n",
    "                    raise InfeasibilityError(\"Negative w variable: \" + str(w_variables[i][j]) + \", i: \" + str(i) + \", j: \" + str(j))\n",
    "        for x in x_variables.values():\n",
    "            if x < 0:\n",
    "                raise InfeasibilityError(\"Negative x variable.\")\n",
    "                \n",
    "        # checking the dual constraints of type (2)           \n",
    "        for i in range(1, N + 1):\n",
    "            for j in range(1, math.ceil((i % a + i + 1)/a) + 1):\n",
    "                if (value(v_variables, j, i) + value(w_variables, j, i)) * (beta_inverse) < 2 * value(y_variables, i):\n",
    "                    raise InfeasibilityError(\"j: \" + str(j) + \", i: \" + str(i) + \": v_ji + w_ji is less than 2beta*y_i: \" + str((value(v_variables, j, i) + value(w_variables, j, i)) * beta_inverse) + \" < \" + str(2 * value(y_variables, i)))\n",
    "        \n",
    "        # checking the dual constraints of type (3)   \n",
    "        for k in range (-a, N + 1):\n",
    "            sum = 0\n",
    "            for i in range (1, N + 1):\n",
    "                h = i % a\n",
    "                for j in range (1, math.ceil((h + i +1)/a) + 1):\n",
    "                    if k == (j - 1) * a - h:\n",
    "                        sum += value(v_variables, j, i)\n",
    "                    if k == i - j * a + h:\n",
    "                        sum += value(w_variables, j, i)\n",
    "            if sum != value(z_variables, k):\n",
    "                raise InfeasibilityError(\"Equality for z_k doesn't hold\")\n",
    "                \n",
    "        # checking the dual constraints of type (1)   \n",
    "        rhs = 9987507809   # lower bound on e^(-1/2 beta), scaled by 10^10\n",
    "        for i in range(N + 1):\n",
    "            lhs = value(y_variables, i)\n",
    "            for j in range(i - a, i + 1):\n",
    "                lhs += value(z_variables, j)\n",
    "            if i == 1:\n",
    "                for j in range(2, N + 1):\n",
    "                    lhs += j * value(x_variables, j)\n",
    "            if i >= 2 and i <= N:\n",
    "                lhs -= value(x_variables, i)\n",
    "            if (lhs > rhs):\n",
    "                raise InfeasibilityError(\"lhs: \" + str(lhs ) + \", rhs: \" + str(rhs) + \", exact rhs: \" + str(math.exp(-(1/2 + i) / beta_inverse) * pow(10,20)) + \", i: \" + str(i))\n",
    "            rhs *= 9975031223 # lower bound on e^(-beta), scaled by 10^10\n",
    "            rhs = rhs//pow(10,10)\n",
    "            \n",
    "        objective = 0\n",
    "        for i in range(1, N + 1):\n",
    "            objective += i * value(y_variables, i)\n",
    "        print(\"Solution is feasible and has objective value \" + str(objective) + \"/\" + str(pow(10,10) * (beta_inverse) * (beta_inverse)))\n",
    "        scaling_factor = pow(10,10) * beta_inverse * beta_inverse * pow(10,4)\n",
    "        upper_bound_master_route_ratio = scaling_factor//objective + 1\n",
    "        print(\"This yields an upper bound on the master route ratio of less than \" + str(upper_bound_master_route_ratio) + \"/10^4\")\n",
    "    except InfeasibilityError as error:\n",
    "        print(\"Solution not feasible; \" + str(error))\n",
    "    except InputError as error:\n",
    "        print(\"InputError; \" + str(error))                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "486ee304",
   "metadata": {},
   "outputs": [],
   "source": [
    "variables = read_input(file_path)\n",
    "check_variables(variables)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}