{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Laboratorium: trasa ciężarówki z Qiskit\n",
    "\n",
    "Ciężarówka wyjeżdża z **centrum dystrybucyjnego (DC)**, rozwozi towar do salonów i wraca do DC.\n",
    "W jakiej kolejności odwiedzić salony, żeby przejechać **jak najmniej kilometrów**?\n",
    "Rozwiążemy to klasycznie, a potem algorytmem kwantowym **QAOA** na symulatorze komputera kwantowego.\n",
    "\n",
    "| Część | Temat |\n",
    "|---|---|\n",
    "| 1 | Dane i rozwiązanie klasyczne |\n",
    "| 2 | Problem jako zmienne 0/1 – **zadanie 1** |\n",
    "| 3 | Od modelu do kubitów |\n",
    "| 4 | Rozwiązanie algorytmem QAOA |\n",
    "| 5 | Większy problem: 16 salonów – **zadania 2a i 2b** |\n",
    "| 6 | Dodanie drugiej ciężarówki – **zadanie 3** |\n",
    "\n",
    "W komórkach **✏️ ZADANIE** piszesz kod sam, od zera. Komórka **✅ Sprawdzenie** pod spodem powie, czy działa.\n",
    "\n",
    "Przed rozpoczęciem laboratorium skonfiguruj środowisko: **environment.yml**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "from docplex.mp.model import Model\n",
    "from qiskit.primitives import StatevectorSampler\n",
    "from qiskit_optimization.algorithms import MinimumEigenOptimizer\n",
    "from qiskit_optimization.converters import QuadraticProgramToQubo\n",
    "from qiskit_optimization.minimum_eigensolvers import QAOA, NumPyMinimumEigensolver\n",
    "from qiskit_optimization.optimizers import COBYLA\n",
    "from qiskit_optimization.translators import from_docplex_mp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Część 1. Dane i rozwiązanie klasyczne\n",
    "\n",
    "DC i trzy salony na uproszczonej mapie (km, odległości w linii prostej)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PUNKTY = {\"DC\": (0, 0), \"A\": (2, 6), \"B\": (7, 5), \"C\": (6, 1)}\n",
    "SALONY = [\"A\", \"B\", \"C\"]\n",
    "ODL = {(p, q): round(float(np.hypot(PUNKTY[p][0] - PUNKTY[q][0], PUNKTY[p][1] - PUNKTY[q][1])), 1)\n",
    "       for p in PUNKTY for q in PUNKTY}\n",
    "\n",
    "\n",
    "def rysuj(trasy=(), tytul=\"\"):\n",
    "    \"\"\"Rysuje mapę; trasy to lista tras, np. [[\"A\", \"B\", \"C\"]] – każda zaczyna i kończy się w DC.\"\"\"\n",
    "    fig, ax = plt.subplots(figsize=(5, 4))\n",
    "    for nazwa, (px, py) in PUNKTY.items():\n",
    "        ax.scatter(px, py, s=300 if nazwa == \"DC\" else 150, c=\"#142138\" if nazwa == \"DC\" else \"#14BBB8\", zorder=3)\n",
    "        ax.annotate(nazwa, (px, py), textcoords=\"offset points\", xytext=(10, 8), fontsize=11)\n",
    "    for k, trasa in enumerate(trasy):\n",
    "        pelna = [\"DC\", *trasa, \"DC\"]\n",
    "        ax.plot([PUNKTY[p][0] for p in pelna], [PUNKTY[p][1] for p in pelna],\n",
    "                color=[\"#E94A16\", \"#087D79\"][k % 2], lw=2, zorder=2)\n",
    "    ax.set_title(tytul)\n",
    "    ax.set_aspect(\"equal\")\n",
    "    ax.margins(0.15)\n",
    "    ax.grid(alpha=0.3)\n",
    "    plt.show()\n",
    "\n",
    "\n",
    "def dlugosc_trasy(trasa):\n",
    "    pelna = [\"DC\", *trasa, \"DC\"]\n",
    "    return round(sum(ODL[skad, dokad] for skad, dokad in zip(pelna, pelna[1:])), 1)\n",
    "\n",
    "\n",
    "# Klasycznie: sprawdzamy wszystkie 3! = 6 kolejności\n",
    "for trasa in sorted(itertools.permutations(SALONY), key=dlugosc_trasy):\n",
    "    print(\" → \".join([\"DC\", *trasa, \"DC\"]), f\"{dlugosc_trasy(trasa):5.1f} km\")\n",
    "rysuj([[\"A\", \"B\", \"C\"]], \"Najkrótsza trasa\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Trasa przejechana w odwrotną stronę ma tę samą długość, więc najlepsze są **dwie**.\n",
    "Dla 10 salonów tras jest już 10! = 3,6 mln, a dla 20 – ponad 10^18."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Część 2. Problem jako zmienne 0/1\n",
    "\n",
    "Komputer kwantowy rozumie tylko **zmienne 0/1**: `x[i, t] = 1`, jeśli salon `i` odwiedzamy w kroku `t`.\n",
    "3 salony × 3 kroki = **9 zmiennych**. Trasa DC → A → B → C → DC:\n",
    "\n",
    "| | krok 0 | krok 1 | krok 2 |\n",
    "|---|---|---|---|\n",
    "| **A** | 1 | 0 | 0 |\n",
    "| **B** | 0 | 1 | 0 |\n",
    "| **C** | 0 | 0 | 1 |\n",
    "\n",
    "Model zapisujemy w bibliotece **docplex**. Funkcja celu jest gotowa: iloczyn `x[i, t] * x[j, t + 1]` jest równy 1\n",
    "tylko wtedy, gdy z salonu `i` jedziemy prosto do `j` – wtedy doliczamy `ODL[i, j]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "KROKI = range(len(SALONY))\n",
    "\n",
    "model = Model(\"trasa\")\n",
    "x = model.binary_var_dict([(i, t) for i in SALONY for t in KROKI], name=\"x\")\n",
    "model.minimize(\n",
    "    model.sum(ODL[\"DC\", i] * x[i, 0] for i in SALONY)                      # DC → pierwszy salon\n",
    "    + model.sum(ODL[i, j] * x[i, t] * x[j, t + 1]                           # przejazdy między salonami\n",
    "                for i in SALONY for j in SALONY if i != j for t in range(len(SALONY) - 1))\n",
    "    + model.sum(ODL[i, \"DC\"] * x[i, len(SALONY) - 1] for i in SALONY))     # ostatni salon → DC"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Zadanie 1 – ograniczenia\n",
    "\n",
    "Bez ograniczeń najkrótsza „trasa” to same zera – nigdzie nie jedziemy. Dodaj do modelu dwa rodzaje ograniczeń:\n",
    "1. każdy salon odwiedzamy **dokładnie raz** – dla każdego salonu `i` suma `x[i, t]` po krokach jest równa 1,\n",
    "2. w każdym kroku jesteśmy **w dokładnie jednym** salonie – dla każdego kroku `t` suma `x[i, t]` po salonach jest równa 1.\n",
    "\n",
    "Przydatne: `model.sum(wyrażenie for ... in ...)` oraz `model.add_constraint(wyrażenie == 1)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✏️ ZADANIE\n",
    "# Twój kod:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✅ Sprawdzenie\n",
    "assert model.number_of_constraints == 6, f\"Model ma {model.number_of_constraints} ograniczeń, a powinien mieć 6\"\n",
    "problem = from_docplex_mp(model)\n",
    "najkrotsza = MinimumEigenOptimizer(NumPyMinimumEigensolver()).solve(problem)  # dokładne rozwiązanie Twojego modelu\n",
    "wzorzec = min(dlugosc_trasy(p) for p in itertools.permutations(SALONY))       # najkrótsza trasa z części 1\n",
    "assert abs(najkrotsza.fval - wzorzec) < 0.05, \\\n",
    "    f\"Najlepsza „trasa” w Twoim modelu ma {najkrotsza.fval:.1f} km zamiast {wzorzec} km – sprawdź ograniczenia\"\n",
    "print(\"✅ Dobrze!\\n\")\n",
    "print(problem.prettyprint())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Część 3. Od modelu do kubitów\n",
    "\n",
    "1. **QUBO** – algorytmy kwantowe nie znają ograniczeń, więc zamieniamy je na **kary**: za trasę łamiącą ograniczenie\n",
    "   doliczamy dużą liczbę. Najlepsze rozwiązanie QUBO jest wtedy zawsze poprawną trasą.\n",
    "2. **Model Isinga** – ten sam problem w języku fizyki: każda zmienna 0/1 to **jeden kubit**, a funkcja celu to\n",
    "   „energia” kubitów. Najkrótsza trasa = stan o **najniższej energii**.\n",
    "\n",
    "Symulator kwantowy przechowuje 2^kubity liczb po 16 bajtów: 9 kubitów to 8 KB, a 30 kubitów to już 16 GB."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "converter = QuadraticProgramToQubo()\n",
    "qubo = converter.convert(problem)\n",
    "hamiltonian, _ = qubo.to_ising()\n",
    "\n",
    "print(\"Zmienne w QUBO:\", qubo.get_num_vars(), \"| ograniczenia:\", qubo.get_num_linear_constraints())\n",
    "print(\"Kara dobrana automatycznie:\", converter.penalty)\n",
    "print(\"Liczba kubitów:\", hamiltonian.num_qubits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Część 4. Rozwiązanie algorytmem QAOA\n",
    "\n",
    "QAOA to algorytm **hybrydowy**:\n",
    "1. buduje z Hamiltonianu **obwód kwantowy** z kilkoma pokrętłami (parametrami),\n",
    "2. uruchamia go wiele razy – każdy pomiar kubitów daje jedną trasę (ciąg 0/1),\n",
    "3. klasyczny optymalizator (COBYLA) kręci pokrętłami tak, żeby obwód częściej dawał krótkie trasy.\n",
    "\n",
    "`reps` to liczba warstw obwodu. `MinimumEigenOptimizer` sam wykonuje konwersję do QUBO i Isinga z części 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "qaoa = QAOA(sampler=StatevectorSampler(seed=7), optimizer=COBYLA(maxiter=200), reps=1)\n",
    "wynik = MinimumEigenOptimizer(qaoa).solve(problem)\n",
    "\n",
    "# x[i, t] = 1 → salon i w kroku t; sortujemy wybrane salony po krokach\n",
    "trasa = [i for (i, t), v in sorted(zip(x.keys(), wynik.x), key=lambda k: k[0][1]) if v > 0.5]\n",
    "print(\"QAOA:\", \" → \".join([\"DC\", *trasa, \"DC\"]), f\"({wynik.fval:.1f} km)\")\n",
    "rysuj([trasa], f\"QAOA: {wynik.fval:.1f} km\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Część 5. Większy problem: 16 salonów\n",
    "\n",
    "**Planowanie dni dostaw:** 16 salonów leży wzdłuż jednej trasy. Każdy dostaje towar **w poniedziałek (0) albo\n",
    "w czwartek (1)** – czyli **1 salon = 1 kubit**.\n",
    "- każdy salon ma określony **koszt dostawy w czwartek, względem dostawy w poniedziałek** (liczba ujemna = tańsza dostawa w czwartek),\n",
    "- jeśli **sąsiednie salony** mają różne dni, ciężarówka jedzie odcinek między nimi dwa razy – płacimy **odległość**.\n",
    "\n",
    "Każdy ciąg 0/1 jest poprawnym planem, więc nie ma ograniczeń. Model jest gotowy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 16\n",
    "rng = np.random.default_rng(5)\n",
    "KOSZT_CZWARTKU = np.round(rng.uniform(-3, 3, N), 1)  # Koszt czwartku względem poniedziałku\n",
    "ODL_SASIEDZI = np.round(rng.uniform(0.5, 2, N - 1), 1)  # km między salonem i a i + 1\n",
    "\n",
    "model_dni = Model(\"dni_dostaw\")\n",
    "z = model_dni.binary_var_list(N, name=\"z\")  # z[i] = 1 → dostawa w czwartek\n",
    "model_dni.minimize(\n",
    "    model_dni.sum(KOSZT_CZWARTKU[i] * z[i] for i in range(N))\n",
    "    # z[i] + z[i+1] - 2·z[i]·z[i+1] = 1 dokładnie wtedy, gdy sąsiedzi mają różne dni\n",
    "    + model_dni.sum(ODL_SASIEDZI[i] * (z[i] + z[i + 1] - 2 * z[i] * z[i + 1]) for i in range(N - 1)))\n",
    "problem_dni = from_docplex_mp(model_dni)\n",
    "print(\"Zmiennych (kubitów):\", problem_dni.get_num_vars())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Zadanie 2a – rozwiąż plan dostaw QAOA\n",
    "\n",
    "Na wzór części 4 rozwiąż `problem_dni` algorytmem QAOA z ustawieniami:\n",
    "`reps=2`, `initial_point=[0.1, 0.1, 0.4, 0.4]` (punkt startowy pokręteł), `StatevectorSampler(seed=7)`,\n",
    "`COBYLA(maxiter=200)`.\n",
    "Wynik zapisz w zmiennej `wynik_dni` i wypisz numery salonów z dostawą w czwartek (`wynik_dni.x[i] == 1`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✏️ ZADANIE\n",
    "# Twój kod:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✅ Sprawdzenie + wykres: słupek = koszt czwartku dla salonu, kolor = wybrany dzień\n",
    "assert len(wynik_dni.x) == N, \"wynik_dni powinien zawierać decyzję dla każdego z 16 salonów\"\n",
    "print(f\"✅ Dobrze! Koszt planu: {wynik_dni.fval:.1f}\")\n",
    "plan = wynik_dni.x.astype(int)\n",
    "fig, ax = plt.subplots(figsize=(9, 3.5))\n",
    "for dzien, kolor, nazwa in ((0, \"#142138\", \"poniedziałek\"), (1, \"#14BBB8\", \"czwartek\")):\n",
    "    ax.bar(np.flatnonzero(plan == dzien), KOSZT_CZWARTKU[plan == dzien], color=kolor, label=nazwa)\n",
    "ax.axhline(0, color=\"#5D6774\", lw=0.8)\n",
    "ax.set_xticks(range(N))\n",
    "ax.set_xlabel(\"salon (kolejność wzdłuż trasy)\")\n",
    "ax.set_ylabel(\"koszt dostawy w czwartek\")\n",
    "ax.legend(loc=\"upper center\", bbox_to_anchor=(0.5, -0.22), ncol=2)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Zadanie 2b – wpływ parametrów\n",
    "\n",
    "Pozmieniaj definicje parametrów KOSZT_CZWARTKU i ODL_SASIEDZI i zobacz jak będą zmieniać się wyniki."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Część 6. Dodanie drugiej ciężarówki"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### ✏️ Zadanie 3 – dwie ciężarówki\n",
    "\n",
    "Dochodzi salon **D**, a towar wiozą **dwie ciężarówki**; każda obsługuje **dokładnie 2 salony** i wraca do DC.\n",
    "Zmienne: `y[k, i, t] = 1`, jeśli ciężarówka `k` odwiedza salon `i` w swoim kroku `t` – razem 2 × 4 × 2 = 16 kubitów.\n",
    "\n",
    "Funkcja celu jest gotowa. Dodaj ograniczenia:\n",
    "1. każdy salon odwiedza dokładnie jedna ciężarówka, dokładnie raz (suma po `k` i `t` równa 1),\n",
    "2. każda ciężarówka w każdym kroku jest w dokładnie jednym salonie (suma po `i` równa 1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "PUNKTY[\"D\"] = (-4, 3)\n",
    "SALONY_VRP, CIEZAROWKI, KROKI_VRP = [\"A\", \"B\", \"C\", \"D\"], [1, 2], [0, 1]\n",
    "ODL = {(p, q): round(float(np.hypot(PUNKTY[p][0] - PUNKTY[q][0], PUNKTY[p][1] - PUNKTY[q][1])), 1)\n",
    "       for p in PUNKTY for q in PUNKTY}\n",
    "\n",
    "model_vrp = Model(\"dwie_ciezarowki\")\n",
    "y = model_vrp.binary_var_dict([(k, i, t) for k in CIEZAROWKI for i in SALONY_VRP for t in KROKI_VRP], name=\"y\")\n",
    "model_vrp.minimize(\n",
    "    model_vrp.sum(ODL[\"DC\", i] * y[k, i, 0] + ODL[i, \"DC\"] * y[k, i, 1] for k in CIEZAROWKI for i in SALONY_VRP)\n",
    "    + model_vrp.sum(ODL[i, j] * y[k, i, 0] * y[k, j, 1]\n",
    "                    for k in CIEZAROWKI for i in SALONY_VRP for j in SALONY_VRP if i != j))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✏️ ZADANIE\n",
    "# Twój kod:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ✅ Sprawdzenie + rozwiązanie dokładne (klasyczne przeszukanie 2^16 stanów)\n",
    "assert model_vrp.number_of_constraints == 8, f\"Model ma {model_vrp.number_of_constraints} ograniczeń, a powinien mieć 8\"\n",
    "wynik_vrp = MinimumEigenOptimizer(NumPyMinimumEigensolver()).solve(from_docplex_mp(model_vrp))\n",
    "wzorzec_vrp = min(dlugosc_trasy(p[:2]) + dlugosc_trasy(p[2:]) for p in itertools.permutations(SALONY_VRP))\n",
    "assert abs(wynik_vrp.fval - wzorzec_vrp) < 0.05, \\\n",
    "    f\"Najlepsze rozwiązanie Twojego modelu ma {wynik_vrp.fval:.1f} km zamiast {wzorzec_vrp:.1f} km – sprawdź ograniczenia\"\n",
    "trasy_vrp = [[i for (kk, i, t), v in sorted(zip(y.keys(), wynik_vrp.x), key=lambda e: e[0][2]) if kk == k and v > 0.5]\n",
    "             for k in CIEZAROWKI]\n",
    "print(\"✅ Dobrze!\", *[f\"Ciężarówka {k}: \" + \" → \".join([\"DC\", *tr, \"DC\"]) for k, tr in zip(CIEZAROWKI, trasy_vrp)], sep=\"\\n\")\n",
    "rysuj(trasy_vrp, f\"Dwie ciężarówki: {wynik_vrp.fval:.1f} km\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "qiskit_lab",
   "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.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
