lp_models_and_examples/two_matching_model.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.linear_solver import pywraplp as OR\n",
    "import itertools\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tsp_6_node = pd.read_csv('tsp_6_node.csv', index_col=0).astype(int)\n",
    "tsp_6_node.columns = tsp_6_node.columns.astype(int)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def two_matching(graph, cuts, integer=False):\n",
    "    \"\"\"A model to solve tsp problems with two-matching.\"\"\"\n",
    "    NODES = list(graph)                      # nodes\n",
    "    cost = {}                                # costs\n",
    "    for i in NODES:\n",
    "        for j in NODES:\n",
    "            if i < j:\n",
    "                cost[(i,j)] = graph.at[i,j]\n",
    "    EDGES = list(cost)                       # edges\n",
    "    \n",
    "    # define model\n",
    "    m = OR.Solver('two_matching', OR.Solver.CBC_MIXED_INTEGER_PROGRAMMING)\n",
    "    \n",
    "    # decision variables\n",
    "    if integer:\n",
    "        x = {(i,j) : m.IntVar(0, 1, ('(%s,%s)' % (i,j))) for (i,j) in EDGES}\n",
    "    else:\n",
    "        x = {(i,j) : m.NumVar(0, 1, ('(%s,%s)' % (i,j))) for (i,j) in EDGES}\n",
    "    \n",
    "    # objective function\n",
    "    m.Minimize(sum(cost[i,j]*x[i,j] for (i,j) in EDGES))\n",
    "    \n",
    "    # subject to: degree of every node is 2\n",
    "    for k in NODES:\n",
    "        m.Add(sum(x[i,j] for (i,j) in EDGES if i == k) + \n",
    "              sum(x[i,j] for (i,j) in EDGES if j == k) == 2)\n",
    "    \n",
    "    # subject to: provided cuts\n",
    "    for S in cuts:\n",
    "        m.Add(sum(x[i,j] for (i,j) in EDGES if (i in S and j not in S) or \n",
    "                                               (j in S and i not in S)) >= 2)\n",
    "        \n",
    "    return m,x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(m):\n",
    "    m.Solve()\n",
    "    print('Solution:')\n",
    "    print('Objective value =', m.Objective().Value())\n",
    "    for var in m.variables():\n",
    "        print(var.name(), ':',  var.solution_value())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,x = two_matching(tsp_6_node, [])\n",
    "solve(m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "m,x = two_matching(tsp_6_node, [[1,2,3]])\n",
    "solve(m)"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}