grouping_problem.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "1333671f-180e-443d-8794-4366104425cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pulp\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1d39274b-1e86-45be-9b86-21d12c16ccd9",
   "metadata": {},
   "source": [
    "Source: https://or.stackexchange.com/questions/11342/need-help-writing-a-metaheuristic-problem/11352#11352"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "44c39c3f-8081-4c51-8f35-e2c2008a1d65",
   "metadata": {},
   "source": [
    "# Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "225fbdad-de3a-42df-8116-11109417f2fd",
   "metadata": {},
   "outputs": [],
   "source": [
    "N= 5\n",
    "size_1 = 2\n",
    "size_2 = 3\n",
    "size_3 = 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "5e3f49ea-2eb6-4b35-8603-8dde2fbbdd82",
   "metadata": {},
   "outputs": [],
   "source": [
    "items = [x for x in range(N)]\n",
    "score = {}\n",
    "for u in items:\n",
    "    for v in items:\n",
    "        if u<v:\n",
    "            score[(u,v)]=random.choice([_ for _ in range(20)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "9f9c57db-965d-4111-a7d6-6cda8ab4f5a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "subsets = [tuple(c) for c in pulp.combination(items, size_1)]+[tuple(c) for c in pulp.combination(items, size_2)]#+[tuple(c) for c in pulp.combination(items, size_3)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "aa92bc33-8f67-4099-a87e-70f784acfa08",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 1),\n",
       " (0, 2),\n",
       " (0, 3),\n",
       " (0, 4),\n",
       " (1, 2),\n",
       " (1, 3),\n",
       " (1, 4),\n",
       " (2, 3),\n",
       " (2, 4),\n",
       " (3, 4),\n",
       " (0, 1, 2),\n",
       " (0, 1, 3),\n",
       " (0, 1, 4),\n",
       " (0, 2, 3),\n",
       " (0, 2, 4),\n",
       " (0, 3, 4),\n",
       " (1, 2, 3),\n",
       " (1, 2, 4),\n",
       " (1, 3, 4),\n",
       " (2, 3, 4)]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "subsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "fb123228-85ea-4d0c-99ab-b0a53fc6e7a6",
   "metadata": {},
   "outputs": [],
   "source": [
    "subset_score = {}\n",
    "for s in subsets:\n",
    "    subset_score[s]=sum(score[(u,v)] for u in s for v in s if  (u,v) in score)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c63c424-3afe-45f9-8b95-7292048f801e",
   "metadata": {},
   "source": [
    "# Optimization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "403d33da-68c2-485c-8e66-f878d466a2cd",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = pulp.LpVariable.dicts(\"subset\", subsets, cat=pulp.LpBinary)\n",
    "prob = pulp.LpProblem(\"grouping_problem\", pulp.LpMaximize)\n",
    "prob += pulp.lpSum([subset_score[s] * x[s] for s in subsets])\n",
    "for v in items:\n",
    "    prob += pulp.lpSum(x[s] for s in subsets if v in s)==1, \"subset_for_%s\"%v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "01e85b6c-af22-42da-8157-08fdc742c063",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "grouping_problem:\n",
       "MAXIMIZE\n",
       "5*subset_(0,_1) + 30*subset_(0,_1,_2) + 31*subset_(0,_1,_3) + 26*subset_(0,_1,_4) + 8*subset_(0,_2) + 22*subset_(0,_2,_3) + 12*subset_(0,_2,_4) + 9*subset_(0,_3) + 24*subset_(0,_3,_4) + 3*subset_(0,_4) + 17*subset_(1,_2) + 39*subset_(1,_2,_3) + 36*subset_(1,_2,_4) + 17*subset_(1,_3) + 47*subset_(1,_3,_4) + 18*subset_(1,_4) + 5*subset_(2,_3) + 18*subset_(2,_3,_4) + 1*subset_(2,_4) + 12*subset_(3,_4) + 0\n",
       "SUBJECT TO\n",
       "subset_for_0: subset_(0,_1) + subset_(0,_1,_2) + subset_(0,_1,_3)\n",
       " + subset_(0,_1,_4) + subset_(0,_2) + subset_(0,_2,_3) + subset_(0,_2,_4)\n",
       " + subset_(0,_3) + subset_(0,_3,_4) + subset_(0,_4) = 1\n",
       "\n",
       "subset_for_1: subset_(0,_1) + subset_(0,_1,_2) + subset_(0,_1,_3)\n",
       " + subset_(0,_1,_4) + subset_(1,_2) + subset_(1,_2,_3) + subset_(1,_2,_4)\n",
       " + subset_(1,_3) + subset_(1,_3,_4) + subset_(1,_4) = 1\n",
       "\n",
       "subset_for_2: subset_(0,_1,_2) + subset_(0,_2) + subset_(0,_2,_3)\n",
       " + subset_(0,_2,_4) + subset_(1,_2) + subset_(1,_2,_3) + subset_(1,_2,_4)\n",
       " + subset_(2,_3) + subset_(2,_3,_4) + subset_(2,_4) = 1\n",
       "\n",
       "subset_for_3: subset_(0,_1,_3) + subset_(0,_2,_3) + subset_(0,_3)\n",
       " + subset_(0,_3,_4) + subset_(1,_2,_3) + subset_(1,_3) + subset_(1,_3,_4)\n",
       " + subset_(2,_3) + subset_(2,_3,_4) + subset_(3,_4) = 1\n",
       "\n",
       "subset_for_4: subset_(0,_1,_4) + subset_(0,_2,_4) + subset_(0,_3,_4)\n",
       " + subset_(0,_4) + subset_(1,_2,_4) + subset_(1,_3,_4) + subset_(1,_4)\n",
       " + subset_(2,_3,_4) + subset_(2,_4) + subset_(3,_4) = 1\n",
       "\n",
       "VARIABLES\n",
       "0 <= subset_(0,_1) <= 1 Integer\n",
       "0 <= subset_(0,_1,_2) <= 1 Integer\n",
       "0 <= subset_(0,_1,_3) <= 1 Integer\n",
       "0 <= subset_(0,_1,_4) <= 1 Integer\n",
       "0 <= subset_(0,_2) <= 1 Integer\n",
       "0 <= subset_(0,_2,_3) <= 1 Integer\n",
       "0 <= subset_(0,_2,_4) <= 1 Integer\n",
       "0 <= subset_(0,_3) <= 1 Integer\n",
       "0 <= subset_(0,_3,_4) <= 1 Integer\n",
       "0 <= subset_(0,_4) <= 1 Integer\n",
       "0 <= subset_(1,_2) <= 1 Integer\n",
       "0 <= subset_(1,_2,_3) <= 1 Integer\n",
       "0 <= subset_(1,_2,_4) <= 1 Integer\n",
       "0 <= subset_(1,_3) <= 1 Integer\n",
       "0 <= subset_(1,_3,_4) <= 1 Integer\n",
       "0 <= subset_(1,_4) <= 1 Integer\n",
       "0 <= subset_(2,_3) <= 1 Integer\n",
       "0 <= subset_(2,_3,_4) <= 1 Integer\n",
       "0 <= subset_(2,_4) <= 1 Integer\n",
       "0 <= subset_(3,_4) <= 1 Integer"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c29c441c-08f7-4a0c-ab2c-80430fb645d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "#prob.writeLP(\"myproblem.lp\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "8f4e7974-bd76-488a-b7a8-47816fcc09dc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "prob.solve(pulp.PULP_CBC_CMD(timeLimit=10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "037b33ca-a6d6-44a7-a062-47d061f490cb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 2)\n",
      "(1, 3, 4)\n"
     ]
    }
   ],
   "source": [
    "for s in x:\n",
    "    if x[s].value() > 0.9:\n",
    "        print(s)"
   ]
  }
 ],
 "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}