{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "n = 10\n",
    "r = 4\n",
    "meja = floor(sqrt((n * (n + 1) * (2*n + 1)) / (r * 6)))\n",
    "p = MixedIntegerLinearProgram(maximization=True)\n",
    "\n",
    "w = p.new_variable(binary=True)\n",
    "y = p.new_variable(binary=True)\n",
    "z = p.new_variable(binary=True)\n",
    "p.set_objective(sum(z[l] for l in range(1, meja + 1))) ##ciljna funkcija\n",
    "p.add_constraint(z[0] == 1) ## robni pogoj, kvadrat velikosti 0 lahko vedno pokrijemo\n",
    "for i in range(1, n + 1):\n",
    "    p.add_constraint(sum(w[i,u,v] for u in range(1, meja + 1) for v in range(1, meja + 1)) == 1) ##pogoj, da imamo največ en kvadrat dolžine i\n",
    "for j in range(1, meja + 1):\n",
    "    for k in range(1, meja + 1):\n",
    "        p.add_constraint(r*y[j,k] <= sum(sum(sum\n",
    "                           (w[i,u,v] for v in range(max(1, k - i + 1), k + 1)) ## pogoj, da je kvadratek (j,k) pokrit vsaj r-krat\n",
    "                               for u in range(max(1, j - i + 1), j + 1))\n",
    "                                  for i in range(1, n + 1))\n",
    "                        )\n",
    "for l in range(1, meja + 1):\n",
    "    p.add_constraint(2*l*z[l] <= (z[l-1] + y[l,l] + sum((y[m,l] +y[l,m]) for m in range(1, l)))) ## pogoj, da je kvadrat lxl pokrit\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8.0"
      ]
     },
     "execution_count": 40,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "p.solve()  ##vrne velikost največjega kvadrata, ki ga dobimo s pokrivanjem.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
   ],
   "source": [
    "resw = p.get_values(w)\n",
    "resy = p.get_values(y)\n",
    "resz = p.get_values(z)\n",
    "kvadratki = []\n",
    "for (x,y) in resy.items():\n",
    "    if y == 1:\n",
    "        kvadratki.append(x)\n",
    "KVADRATI = []\n",
    "for (x,y) in resw.items():\n",
    "    if y == 1:\n",
    "        KVADRATI.append(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 8, 8),\n",
       " (2, 8, 6),\n",
       " (3, 1, 1),\n",
       " (4, 1, 1),\n",
       " (5, 5, 1),\n",
       " (6, 4, 1),\n",
       " (7, 1, 3),\n",
       " (8, 1, 2),\n",
       " (9, 1, 1),\n",
       " (10, 1, 1)]"
      ]
     },
     "execution_count": 42,
     "metadata": {
     },
     "output_type": "execute_result"
    }
   ],
   "source": [
    "KVADRATI  ## vrne izhodišča kvadratov v optimalni rešitvi"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.7",
   "language": "sagemath",
   "metadata": {
    "cocalc": {
     "description": "Open-source mathematical software system",
     "priority": 10,
     "url": "https://www.sagemath.org/"
    }
   },
   "name": "sage-9.7",
   "resource_dir": "/ext/jupyter/kernels/sage-9.7"
  },
  "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}