{ "cells": [ { "cell_type": "markdown", "id": "c189881d", "metadata": {}, "source": [ "# Hexaly Max Clique Benchmarking" ] }, { "cell_type": "code", "execution_count": null, "id": "452238eb", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import os\n", "import time\n", "import hexaly.optimizer" ] }, { "cell_type": "markdown", "id": "75f372af", "metadata": {}, "source": [ "### Read data file and build objective functions" ] }, { "cell_type": "code", "execution_count": null, "id": "1e183819", "metadata": {}, "outputs": [], "source": [ "def read_dimacs_clq(file_path):\n", " \"\"\"Read a DIMACS ascii .clq graph and return the adjacency matrix A.\n", "\n", " A[i, j] == 1 iff (i+1, j+1) is an edge (vertices in the file are 1-indexed).\n", " Lines: 'c ...' comments, 'p edge ' header, 'e ' edges.\n", " \"\"\"\n", " n = None\n", " edges = []\n", " with open(file_path, 'r') as f:\n", " for line in f:\n", " parts = line.split()\n", " if not parts:\n", " continue\n", " tag = parts[0]\n", " if tag == 'c':\n", " continue\n", " elif tag == 'p':\n", " # p edge n m (some files use 'p col n m' / 'p clq n m')\n", " n = int(parts[2])\n", " m = int(parts[3])\n", " elif tag == 'e':\n", " edges.append((int(parts[1]), int(parts[2])))\n", "\n", " if n is None:\n", " raise ValueError(f\"no 'p' header found in {file_path}\")\n", "\n", " A = np.zeros((n, n), dtype=np.uint8)\n", " for u, v in edges:\n", " if u == v:\n", " continue # ignore self-loops\n", " A[u - 1, v - 1] = 1\n", " A[v - 1, u - 1] = 1 # undirected -> symmetric\n", "\n", " return A, n, m\n", "\n", "def build_clique_hamiltonian(A):\n", " A = np.asarray(A, dtype=float)\n", " return -A\n", "\n" ] }, { "cell_type": "markdown", "id": "efe93241", "metadata": {}, "source": [ "### Functions to extract clique number from energy and statevector" ] }, { "cell_type": "code", "execution_count": null, "id": "35436462", "metadata": {}, "outputs": [], "source": [ "def clique_number_from_energy(energy, sum_constraint=1.0):\n", " R = float(sum_constraint)\n", " return 1.0 / (1.0 + energy / (R * R))\n", "\n", "def extract_clique(x, A, tol=1e-6, scale=None):\n", " \"\"\"Read a vertex set off the support of x and check it really is a clique.\n", "\n", " `tol` is RELATIVE: v is in the support when x[v] > tol * scale, with scale\n", " defaulting to max(x). \n", " \n", " Returns (vertices, is_clique). Vertices are 0-indexed into A; add 1 to get\n", " the labels used in the DIMACS file.\n", " \"\"\"\n", " x = np.asarray(x, dtype=float)\n", " if scale is None:\n", " scale = x.max() if x.size else 0.0\n", " if scale <= 0.0:\n", " return np.array([], dtype=int), False\n", " vertices = np.flatnonzero(x > tol * scale)\n", " k = len(vertices)\n", " if k == 0:\n", " return vertices, False\n", " sub = np.asarray(A, dtype=bool)[np.ix_(vertices, vertices)]\n", " # A clique on k vertices has k*(k-1) ones in its (symmetric, zero-diagonal) block.\n", " is_clique = bool(sub.sum() == k * (k - 1))\n", " return vertices, is_clique\n", "\n", "def _extend_to_maximal(chosen, cand, Ab, x):\n", " \"\"\"Grow `chosen` while candidates remain, highest weight first.\n", " \"\"\"\n", " while True:\n", " idx = np.flatnonzero(cand)\n", " if idx.size == 0:\n", " return chosen\n", " w = x[idx]\n", " best = w.max()\n", " ties = idx[w >= best - 1e-12 * max(1.0, abs(best))]\n", " if ties.size > 1:\n", " deg = Ab[np.ix_(ties, idx)].sum(1)\n", " v = int(ties[np.argmax(deg)])\n", " else:\n", " v = int(ties[0])\n", " chosen.append(v)\n", " cand &= Ab[v]\n", " cand[v] = False\n", "\n", "def greedy_clique_from_weights(x, A):\n", " \"\"\"Repair step: greedily grow a genuine clique, taking vertices in order of x.\n", " \"\"\"\n", " Ab = np.asarray(A, dtype=bool)\n", " x = np.asarray(x, dtype=float)\n", " cand = np.ones(Ab.shape[0], dtype=bool)\n", " return np.array(sorted(_extend_to_maximal([], cand, Ab, x)), dtype=int)" ] }, { "cell_type": "markdown", "id": "cf0f8e4b", "metadata": {}, "source": [ "### Set up Hexaly solver" ] }, { "cell_type": "code", "execution_count": null, "id": "df033843", "metadata": {}, "outputs": [], "source": [ "def hexaly_solver(Q,c,sum_constraint, time_limit= 1800):\n", " n = len(np.squeeze(c))\n", " def external_xTQx(x):\n", " return x @ Q @ x\n", "\n", " def external_2Qx(x):\n", " return 2 * Q @ x\n", " \n", " with hexaly.optimizer.HexalyOptimizer() as optimizer:\n", " model = optimizer.model\n", " x = [model.float(0.0,100.0) for _ in range(n)]\n", " linear_term = model.sum(c[i]*x[i] for i in range(n))\n", " xTQx_func = model.create_double_external_function(external_xTQx, external_2Qx)\n", " objective = linear_term + xTQx_func(x)\n", "\n", " model.constraint(model.sum(x) == sum_constraint)\n", " model.minimize(objective)\n", " model.close()\n", "\n", " optimizer.param.time_limit = time_limit\n", " print(\"Starting Hexaly solver...\")\n", " optimizer.solve()\n", " solution = [x[i].value for i in range(n)]\n", " objective_val = objective.value\n", " print(f\"Status: {optimizer.solution.status}\")\n", " return solution, objective_val" ] }, { "cell_type": "markdown", "id": "beafde62", "metadata": {}, "source": [ "### load data file" ] }, { "cell_type": "code", "execution_count": 3, "id": "4d2d7c66", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "file loaded sucessfully\n" ] } ], "source": [ "instance_dir = \"Instances/\"\n", "instance_name = \"keller4.clq\"\n", "instance_path = os.path.join(instance_dir, instance_name)\n", "try:\n", " A, n, m = read_dimacs_clq(instance_path)\n", " print(\"file loaded sucessfully\")\n", "except FileNotFoundError:\n", " print(f\"{instance_path} does not exist\")" ] }, { "cell_type": "code", "execution_count": 4, "id": "81ec7e2e", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "keller4: n = 171 vertices, m = 9435 edges (declared)\n", "A shape: (171, 171)\n", "edges in A: 9435\n", "symmetric: True\n", "self-loops: 0\n", "density: 0.64912\n" ] } ], "source": [ "name = os.path.splitext(instance_name)[0]\n", "print(f\"{name}: n = {n} vertices, m = {m} edges (declared)\")\n", "print(f\"A shape: {A.shape}\")\n", "print(f\"edges in A: {int(A.sum()) // 2}\")\n", "print(f\"symmetric: {np.array_equal(A, A.T)}\")\n", "print(f\"self-loops: {int(np.trace(A))}\")\n", "print(f\"density: {A.sum() / (n * (n - 1)):.5f}\")" ] }, { "cell_type": "code", "execution_count": 5, "id": "21bf6a96", "metadata": {}, "outputs": [], "source": [ "c = np.zeros(n)\n", "H = build_clique_hamiltonian(A)\n", "\n", "sum_constraint = 1\n", "time_limit = 300" ] }, { "cell_type": "code", "execution_count": 6, "id": "c155dbbb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\u001b[2KPreprocess model 100%Starting Hexaly solver...\n", "\u001b[2KPush initial solution 100%\n", "\u001b[1m\u001b[4mModel\u001b[0m: expressions = 351, decisions = 171, constraints = 1, objectives = 1\n", "\u001b[1m\u001b[4mParam\u001b[0m: time limit = 300 sec, no iteration limit\n", "\n", "[objective direction ]: minimize\n", "\n", "[ 0 sec, 0 itr]: No feasible solution found (infeas = 1)\n", "[ 1 sec, 0 itr]: -0.857131\n", "[ 2 sec, 3325 itr]: -0.857131\n", "[ 3 sec, 3325 itr]: -0.857131\n", "[ 4 sec, 4314 itr]: -0.857131\n", "[ 5 sec, 5223 itr]: -0.857131\n", "[ 6 sec, 6774 itr]: -0.857131\n", "[ 7 sec, 7867 itr]: -0.857131\n", "[ 8 sec, 9437 itr]: -0.857131\n", "[ 9 sec, 10994 itr]: -0.862687\n", "[ 10 sec, 13238 itr]: -0.876333\n", "[ optimality gap ]: 100.00%\n", "[ 11 sec, 15235 itr]: -0.877773\n", "[ 12 sec, 17245 itr]: -0.8859\n", "[ 13 sec, 19343 itr]: -0.90005\n", "[ 14 sec, 21370 itr]: -0.903539\n", "[ 15 sec, 21370 itr]: -0.903539\n", "[ 16 sec, 25828 itr]: -0.905469\n", "[ 17 sec, 25828 itr]: -0.905469\n", "[ 18 sec, 30851 itr]: -0.908167\n", "[ 19 sec, 33644 itr]: -0.908375\n", "[ 20 sec, 36420 itr]: -0.908466\n", "[ optimality gap ]: 100.00%\n", "[ 21 sec, 39307 itr]: -0.908483\n", "[ 22 sec, 42065 itr]: -0.908614\n", "[ 23 sec, 44570 itr]: -0.908686\n", "[ 24 sec, 47388 itr]: -0.908952\n", "[ 25 sec, 50274 itr]: -0.908987\n", "[ 26 sec, 53110 itr]: -0.908994\n", "[ 27 sec, 53110 itr]: -0.908994\n", "[ 28 sec, 58835 itr]: -0.909018\n", "[ 29 sec, 61408 itr]: -0.909066\n", "[ 30 sec, 64024 itr]: -0.909066\n", "[ optimality gap ]: 100.00%\n", "[ 31 sec, 66500 itr]: -0.909069\n", "[ 32 sec, 69205 itr]: -0.909069\n", "[ 33 sec, 71527 itr]: -0.909069\n", "[ 34 sec, 73792 itr]: -0.909076\n", "[ 35 sec, 76270 itr]: -0.909076\n", "[ 36 sec, 78746 itr]: -0.909077\n", "[ 37 sec, 81392 itr]: -0.909078\n", "[ 38 sec, 81392 itr]: -0.909078\n", "[ 39 sec, 87222 itr]: -0.909078\n", "[ 40 sec, 90126 itr]: -0.909078\n", "[ optimality gap ]: 100.00%\n", "[ 41 sec, 93269 itr]: -0.909078\n", "[ 42 sec, 96385 itr]: -0.909078\n", "[ 43 sec, 99380 itr]: -0.909078\n", "[ 44 sec, 102426 itr]: -0.909078\n", "[ 45 sec, 105433 itr]: -0.909078\n", "[ 46 sec, 108424 itr]: -0.909078\n", "[ 47 sec, 111565 itr]: -0.909078\n", "[ 48 sec, 114603 itr]: -0.909078\n", "[ 49 sec, 117391 itr]: -0.909079\n", "[ 50 sec, 120108 itr]: -0.909079\n", "[ optimality gap ]: 100.00%\n", "[ 51 sec, 122474 itr]: -0.909079\n", "[ 52 sec, 125205 itr]: -0.909079\n", "[ 53 sec, 128084 itr]: -0.909079\n", "[ 54 sec, 130626 itr]: -0.909079\n", "[ 55 sec, 133176 itr]: -0.909079\n", "[ 56 sec, 135706 itr]: -0.909079\n", "[ 57 sec, 138314 itr]: -0.909079\n", "[ 58 sec, 140833 itr]: -0.909079\n", "[ 59 sec, 143378 itr]: -0.909079\n", "[ 60 sec, 146050 itr]: -0.909081\n", "[ optimality gap ]: 100.00%\n", "[ 61 sec, 148770 itr]: -0.909081\n", "[ 62 sec, 151631 itr]: -0.909082\n", "[ 63 sec, 154618 itr]: -0.909082\n", "[ 64 sec, 157286 itr]: -0.909082\n", "[ 65 sec, 157286 itr]: -0.909082\n", "[ 66 sec, 163217 itr]: -0.909083\n", "[ 67 sec, 166242 itr]: -0.909084\n", "[ 68 sec, 169382 itr]: -0.909084\n", "[ 69 sec, 172338 itr]: -0.909085\n", "[ 70 sec, 175170 itr]: -0.909085\n", "[ optimality gap ]: 100.00%\n", "[ 71 sec, 178125 itr]: -0.909085\n", "[ 72 sec, 178125 itr]: -0.909085\n", "[ 73 sec, 183973 itr]: -0.909085\n", "[ 74 sec, 186766 itr]: -0.909085\n", "[ 75 sec, 189673 itr]: -0.909085\n", "[ 76 sec, 192778 itr]: -0.909085\n", "[ 77 sec, 195773 itr]: -0.909085\n", "[ 78 sec, 198713 itr]: -0.909085\n", "[ 79 sec, 201803 itr]: -0.909085\n", "[ 80 sec, 201803 itr]: -0.909085\n", "[ optimality gap ]: 100.00%\n", "[ 81 sec, 207190 itr]: -0.909085\n", "[ 82 sec, 207190 itr]: -0.909085\n", "[ 83 sec, 212949 itr]: -0.909085\n", "[ 84 sec, 215715 itr]: -0.909085\n", "[ 85 sec, 218655 itr]: -0.909085\n", "[ 86 sec, 221951 itr]: -0.909085\n", "[ 87 sec, 221951 itr]: -0.909085\n", "[ 88 sec, 227496 itr]: -0.909086\n", "[ 89 sec, 230516 itr]: -0.909086\n", "[ 90 sec, 230516 itr]: -0.909086\n", "[ optimality gap ]: 100.00%\n", "[ 91 sec, 236513 itr]: -0.909086\n", "[ 92 sec, 236513 itr]: -0.909086\n", "[ 93 sec, 242486 itr]: -0.909086\n", "[ 94 sec, 245408 itr]: -0.909086\n", "[ 95 sec, 248126 itr]: -0.909086\n", "[ 96 sec, 250778 itr]: -0.909086\n", "[ 97 sec, 253330 itr]: -0.909086\n", "[ 98 sec, 256054 itr]: -0.909086\n", "[ 99 sec, 258489 itr]: -0.909086\n", "[100 sec, 260968 itr]: -0.909086\n", "[ optimality gap ]: 100.00%\n", "[101 sec, 263513 itr]: -0.909086\n", "[102 sec, 265726 itr]: -0.909086\n", "[103 sec, 268275 itr]: -0.909086\n", "[104 sec, 270733 itr]: -0.909086\n", "[105 sec, 273060 itr]: -0.909086\n", "[106 sec, 275552 itr]: -0.909086\n", "[107 sec, 278392 itr]: -0.909086\n", "[108 sec, 281008 itr]: -0.909086\n", "[109 sec, 283671 itr]: -0.909086\n", "[110 sec, 286086 itr]: -0.909086\n", "[ optimality gap ]: 100.00%\n", "[111 sec, 288670 itr]: -0.909086\n", "[112 sec, 291137 itr]: -0.909086\n", "[113 sec, 293909 itr]: -0.909086\n", "[114 sec, 296409 itr]: -0.909086\n", "[115 sec, 299091 itr]: -0.909086\n", "[116 sec, 299091 itr]: -0.909086\n", "[117 sec, 304908 itr]: -0.909086\n", "[118 sec, 307728 itr]: -0.909086\n", "[119 sec, 310999 itr]: -0.909086\n", "[120 sec, 314277 itr]: -0.909086\n", "[ optimality gap ]: 100.00%\n", "[121 sec, 317349 itr]: -0.909086\n", "[122 sec, 320296 itr]: -0.909086\n", "[123 sec, 320296 itr]: -0.909086\n", "[124 sec, 326113 itr]: -0.909086\n", "[125 sec, 329092 itr]: -0.909086\n", "[126 sec, 329092 itr]: -0.909086\n", "[127 sec, 335396 itr]: -0.909086\n", "[128 sec, 338640 itr]: -0.909086\n", "[129 sec, 341200 itr]: -0.909086\n", "[130 sec, 344078 itr]: -0.909086\n", "[ optimality gap ]: 100.00%\n", "[131 sec, 347110 itr]: -0.909086\n", "[132 sec, 349953 itr]: -0.909086\n", "[133 sec, 352184 itr]: -0.909086\n", "[134 sec, 354731 itr]: -0.909086\n", "[135 sec, 357419 itr]: -0.909087\n", "[136 sec, 360095 itr]: -0.909087\n", "[137 sec, 362806 itr]: -0.909087\n", "[138 sec, 365352 itr]: -0.909087\n", "[139 sec, 365352 itr]: -0.909087\n", "[140 sec, 370533 itr]: -0.909087\n", "[ optimality gap ]: 100.00%\n", "[141 sec, 373308 itr]: -0.909087\n", "[142 sec, 376101 itr]: -0.909087\n", "[143 sec, 378685 itr]: -0.909087\n", "[144 sec, 381251 itr]: -0.909087\n", "[145 sec, 383659 itr]: -0.909087\n", "[146 sec, 386149 itr]: -0.909087\n", "[147 sec, 388738 itr]: -0.909087\n", "[148 sec, 391655 itr]: -0.909087\n", "[149 sec, 394462 itr]: -0.909087\n", "[150 sec, 397000 itr]: -0.909087\n", "[ optimality gap ]: 100.00%\n", "[151 sec, 399642 itr]: -0.909087\n", "[152 sec, 402699 itr]: -0.909087\n", "[153 sec, 402699 itr]: -0.909087\n", "[154 sec, 405756 itr]: -0.909087\n", "[155 sec, 411971 itr]: -0.909087\n", "[156 sec, 415034 itr]: -0.909087\n", "[157 sec, 418239 itr]: -0.909087\n", "[158 sec, 421513 itr]: -0.909087\n", "[159 sec, 424656 itr]: -0.909087\n", "[160 sec, 424656 itr]: -0.909087\n", "[ optimality gap ]: 100.00%\n", "[161 sec, 428216 itr]: -0.909087\n", "[162 sec, 435060 itr]: -0.909087\n", "[163 sec, 435060 itr]: -0.909087\n", "[164 sec, 441929 itr]: -0.909087\n", "[165 sec, 441929 itr]: -0.909087\n", "[166 sec, 445216 itr]: -0.909087\n", "[167 sec, 451503 itr]: -0.909087\n", "[168 sec, 451503 itr]: -0.909087\n", "[169 sec, 457912 itr]: -0.909087\n", "[170 sec, 457912 itr]: -0.909087\n", "[ optimality gap ]: 100.00%\n", "[171 sec, 464551 itr]: -0.909087\n", "[172 sec, 468029 itr]: -0.909087\n", "[173 sec, 471306 itr]: -0.909087\n", "[174 sec, 474419 itr]: -0.909087\n", "[175 sec, 477327 itr]: -0.909087\n", "[176 sec, 480514 itr]: -0.909087\n", "[177 sec, 483620 itr]: -0.909087\n", "[178 sec, 487032 itr]: -0.909087\n", "[179 sec, 490056 itr]: -0.909087\n", "[180 sec, 493497 itr]: -0.909087\n", "[ optimality gap ]: 100.00%\n", "[181 sec, 496608 itr]: -0.909087\n", "[182 sec, 499848 itr]: -0.909087\n", "[183 sec, 499848 itr]: -0.909087\n", "[184 sec, 506299 itr]: -0.909087\n", "[185 sec, 508972 itr]: -0.909087\n", "[186 sec, 511789 itr]: -0.909088\n", "[187 sec, 514667 itr]: -0.909089\n", "[188 sec, 517385 itr]: -0.909089\n", "[189 sec, 520268 itr]: -0.909089\n", "[190 sec, 522836 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[191 sec, 525872 itr]: -0.909089\n", "[192 sec, 528784 itr]: -0.909089\n", "[193 sec, 531608 itr]: -0.909089\n", "[194 sec, 534616 itr]: -0.909089\n", "[195 sec, 537383 itr]: -0.909089\n", "[196 sec, 539954 itr]: -0.909089\n", "[197 sec, 542632 itr]: -0.909089\n", "[198 sec, 545570 itr]: -0.909089\n", "[199 sec, 548398 itr]: -0.909089\n", "[200 sec, 551297 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[201 sec, 554429 itr]: -0.909089\n", "[202 sec, 557175 itr]: -0.909089\n", "[203 sec, 559759 itr]: -0.909089\n", "[204 sec, 562694 itr]: -0.909089\n", "[205 sec, 565547 itr]: -0.909089\n", "[206 sec, 568237 itr]: -0.909089\n", "[207 sec, 571176 itr]: -0.909089\n", "[208 sec, 574735 itr]: -0.909089\n", "[209 sec, 577673 itr]: -0.909089\n", "[210 sec, 580642 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[211 sec, 583653 itr]: -0.909089\n", "[212 sec, 586598 itr]: -0.909089\n", "[213 sec, 589442 itr]: -0.909089\n", "[214 sec, 592326 itr]: -0.909089\n", "[215 sec, 595230 itr]: -0.909089\n", "[216 sec, 598029 itr]: -0.909089\n", "[217 sec, 598029 itr]: -0.909089\n", "[218 sec, 603715 itr]: -0.909089\n", "[219 sec, 606305 itr]: -0.909089\n", "[220 sec, 609060 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[221 sec, 611936 itr]: -0.909089\n", "[222 sec, 614688 itr]: -0.909089\n", "[223 sec, 617409 itr]: -0.909089\n", "[224 sec, 620560 itr]: -0.909089\n", "[225 sec, 620560 itr]: -0.909089\n", "[226 sec, 627321 itr]: -0.909089\n", "[227 sec, 630493 itr]: -0.909089\n", "[228 sec, 630493 itr]: -0.909089\n", "[229 sec, 636469 itr]: -0.909089\n", "[230 sec, 639521 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[231 sec, 642689 itr]: -0.909089\n", "[232 sec, 645602 itr]: -0.909089\n", "[233 sec, 648842 itr]: -0.909089\n", "[234 sec, 648842 itr]: -0.909089\n", "[235 sec, 654819 itr]: -0.909089\n", "[236 sec, 657917 itr]: -0.909089\n", "[237 sec, 661048 itr]: -0.909089\n", "[238 sec, 663917 itr]: -0.909089\n", "[239 sec, 666937 itr]: -0.909089\n", "[240 sec, 669565 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[241 sec, 672445 itr]: -0.909089\n", "[242 sec, 675220 itr]: -0.909089\n", "[243 sec, 677982 itr]: -0.909089\n", "[244 sec, 677982 itr]: -0.909089\n", "[245 sec, 680901 itr]: -0.909089\n", "[246 sec, 687001 itr]: -0.909089\n", "[247 sec, 690170 itr]: -0.909089\n", "[248 sec, 693084 itr]: -0.909089\n", "[249 sec, 695904 itr]: -0.909089\n", "[250 sec, 698985 itr]: -0.909089\n", "[ optimality gap ]: 100.00%\n", "[251 sec, 701848 itr]: -0.90909\n", "[252 sec, 704659 itr]: -0.90909\n", "[253 sec, 707834 itr]: -0.90909\n", "[254 sec, 710728 itr]: -0.90909\n", "[255 sec, 710728 itr]: -0.90909\n", "[256 sec, 716856 itr]: -0.90909\n", "[257 sec, 716856 itr]: -0.90909\n", "[258 sec, 723045 itr]: -0.90909\n", "[259 sec, 725923 itr]: -0.90909\n", "[260 sec, 728868 itr]: -0.90909\n", "[ optimality gap ]: 100.00%\n", "[261 sec, 731867 itr]: -0.90909\n", "[262 sec, 731867 itr]: -0.90909\n", "[263 sec, 737897 itr]: -0.90909\n", "[264 sec, 740925 itr]: -0.90909\n", "[265 sec, 744052 itr]: -0.90909\n", "[266 sec, 744052 itr]: -0.90909\n", "[267 sec, 750594 itr]: -0.90909\n", "[268 sec, 753786 itr]: -0.90909\n", "[269 sec, 756901 itr]: -0.90909\n", "[270 sec, 760374 itr]: -0.90909\n", "[ optimality gap ]: 100.00%\n", "[271 sec, 763595 itr]: -0.90909\n", "[272 sec, 766603 itr]: -0.90909\n", "[273 sec, 766603 itr]: -0.90909\n", "[274 sec, 772846 itr]: -0.90909\n", "[275 sec, 776058 itr]: -0.90909\n", "[276 sec, 779054 itr]: -0.90909\n", "[277 sec, 782206 itr]: -0.90909\n", "[278 sec, 785332 itr]: -0.90909\n", "[279 sec, 788585 itr]: -0.90909\n", "[280 sec, 791469 itr]: -0.90909\n", "[ optimality gap ]: 100.00%\n", "[281 sec, 794388 itr]: -0.90909\n", "[282 sec, 797754 itr]: -0.90909\n", "[283 sec, 801253 itr]: -0.90909\n", "[284 sec, 804441 itr]: -0.90909\n", "[285 sec, 807556 itr]: -0.90909\n", "[286 sec, 810862 itr]: -0.90909\n", "[287 sec, 814195 itr]: -0.90909\n", "[288 sec, 817451 itr]: -0.90909\n", "[289 sec, 817451 itr]: -0.90909\n", "[290 sec, 823387 itr]: -0.90909\n", "[ optimality gap ]: 100.00%\n", "[291 sec, 826679 itr]: -0.90909\n", "[292 sec, 829774 itr]: -0.90909\n", "[293 sec, 832929 itr]: -0.90909\n", "[294 sec, 836069 itr]: -0.90909\n", "[295 sec, 839404 itr]: -0.90909\n", "[296 sec, 842945 itr]: -0.90909\n", "[297 sec, 846194 itr]: -0.90909\n", "[298 sec, 846194 itr]: -0.90909\n", "[299 sec, 852288 itr]: -0.90909\n", "[300 sec, 855388 itr]: -0.90909\n", "[ optimality gap ]: 100.00%\n", "[300 sec, 855388 itr]: -0.90909\n", "[ optimality gap ]: 100.00%\n", "\n", "855388 iterations performed in 300 seconds\n", "\n", "\u001b[1m\u001b[32mFeasible solution: \u001b[0m\n", " obj = -0.90909\n", " gap = 100.00%\n", " bounds = -inf\n", "Status: HxSolutionStatus.FEASIBLE\n", " energy omega_est clique time (s)\n", " -0.909090 11.000 11 299.713\n" ] } ], "source": [ "hexaly_start = time.time()\n", "hex_sol_list, hex_obj = hexaly_solver(Q=H,\n", " c=c,\n", " sum_constraint=sum_constraint,\n", " time_limit=time_limit)\n", "hexaly_end = time.time()\n", "hexaly_time = hexaly_end-hexaly_start\n", "omega = clique_number_from_energy(hex_obj, sum_constraint)\n", "support, isclique = extract_clique(hex_sol_list, A)\n", "greedy = greedy_clique_from_weights(hex_sol_list, A)\n", "\n", "print(f\"{'energy':>16}{'omega_est':>12}{'clique':>9}{'time (s)':>12}\")\n", "print(f\"{hex_obj:>16.6f}{omega:>12.3f}{len(greedy):>9}{hexaly_time:>12.3f}\")\n" ] } ], "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 }