Hexaly Max Clique Benchmarking

import numpy as np
import os
import time
import hexaly.optimizer

def read_dimacs_clq(file_path):
    """Read a DIMACS ascii .clq graph and return the adjacency matrix A.
    A[i, j] == 1 iff (i+1, j+1) is an edge (vertices in the file are 1-indexed).
    Lines: 'c ...' comments, 'p edge <n> <m>' header, 'e <u> <v>' edges.
    """
    n = None
    edges = []
    with open(file_path, 'r') as f:
        for line in f:
            parts = line.split()
            if not parts:
                continue
            tag = parts[0]
            if tag == 'c':
                continue
            elif tag == 'p':
                # p edge n m   (some files use 'p col n m' / 'p clq n m')
                n = int(parts[2])
                m = int(parts[3])
            elif tag == 'e':
                edges.append((int(parts[1]), int(parts[2])))
    if n is None:
        raise ValueError(f"no 'p' header found in {file_path}")
    A = np.zeros((n, n), dtype=np.uint8)
    for u, v in edges:
        if u == v:
            continue  # ignore self-loops
        A[u - 1, v - 1] = 1
        A[v - 1, u - 1] = 1  # undirected -> symmetric
    return A, n, m
def build_clique_hamiltonian(A):
    A = np.asarray(A, dtype=float)
    return -A

def clique_number_from_energy(energy, sum_constraint=1.0):
    R = float(sum_constraint)
    return 1.0 / (1.0 + energy / (R * R))
def extract_clique(x, A, tol=1e-6, scale=None):
    """Read a vertex set off the support of x and check it really is a clique.
    `tol` is RELATIVE: v is in the support when x[v] > tol * scale, with scale
    defaulting to max(x). 
    
    Returns (vertices, is_clique). Vertices are 0-indexed into A; add 1 to get
    the labels used in the DIMACS file.
    """
    x = np.asarray(x, dtype=float)
    if scale is None:
        scale = x.max() if x.size else 0.0
    if scale <= 0.0:
        return np.array([], dtype=int), False
    vertices = np.flatnonzero(x > tol * scale)
    k = len(vertices)
    if k == 0:
        return vertices, False
    sub = np.asarray(A, dtype=bool)[np.ix_(vertices, vertices)]
    # A clique on k vertices has k*(k-1) ones in its (symmetric, zero-diagonal) block.
    is_clique = bool(sub.sum() == k * (k - 1))
    return vertices, is_clique
def _extend_to_maximal(chosen, cand, Ab, x):
    """Grow `chosen` while candidates remain, highest weight first.
    """
    while True:
        idx = np.flatnonzero(cand)
        if idx.size == 0:
            return chosen
        w = x[idx]
        best = w.max()
        ties = idx[w >= best - 1e-12 * max(1.0, abs(best))]
        if ties.size > 1:
            deg = Ab[np.ix_(ties, idx)].sum(1)
            v = int(ties[np.argmax(deg)])
        else:
            v = int(ties[0])
        chosen.append(v)
        cand &= Ab[v]
        cand[v] = False
def greedy_clique_from_weights(x, A):
    """Repair step: greedily grow a genuine clique, taking vertices in order of x.
    """
    Ab = np.asarray(A, dtype=bool)
    x = np.asarray(x, dtype=float)
    cand = np.ones(Ab.shape[0], dtype=bool)
    return np.array(sorted(_extend_to_maximal([], cand, Ab, x)), dtype=int)

def hexaly_solver(Q,c,sum_constraint, time_limit= 1800):
    n = len(np.squeeze(c))
    def external_xTQx(x):
        return x @ Q @ x
    def external_2Qx(x):
        return 2 * Q @ x
    
    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        model = optimizer.model
        x = [model.float(0.0,100.0) for _ in range(n)]
        linear_term = model.sum(c[i]*x[i] for i in range(n))
        xTQx_func = model.create_double_external_function(external_xTQx, external_2Qx)
        objective = linear_term + xTQx_func(x)
        model.constraint(model.sum(x) == sum_constraint)
        model.minimize(objective)
        model.close()
        optimizer.param.time_limit = time_limit
        print("Starting Hexaly solver...")
        optimizer.solve()
        solution = [x[i].value for i in range(n)]
        objective_val = objective.value
        print(f"Status: {optimizer.solution.status}")
        return solution, objective_val

instance_dir = "Instances/"
instance_name = "keller4.clq"
instance_path = os.path.join(instance_dir, instance_name)
try:
    A, n, m = read_dimacs_clq(instance_path)
    print("file loaded sucessfully")
except FileNotFoundError:
    print(f"{instance_path} does not exist")

file loaded sucessfully

name = os.path.splitext(instance_name)[0]
print(f"{name}: n = {n} vertices, m = {m} edges (declared)")
print(f"A shape: {A.shape}")
print(f"edges in A: {int(A.sum()) // 2}")
print(f"symmetric: {np.array_equal(A, A.T)}")
print(f"self-loops: {int(np.trace(A))}")
print(f"density: {A.sum() / (n * (n - 1)):.5f}")

keller4: n = 171 vertices, m = 9435 edges (declared)
A shape: (171, 171)
edges in A: 9435
symmetric: True
self-loops: 0
density: 0.64912

c = np.zeros(n)
H = build_clique_hamiltonian(A)
sum_constraint = 1
time_limit = 300

hexaly_start = time.time()
hex_sol_list, hex_obj = hexaly_solver(Q=H,
                                      c=c,
                                      sum_constraint=sum_constraint,
                                      time_limit=time_limit)
hexaly_end = time.time()
hexaly_time = hexaly_end-hexaly_start
omega = clique_number_from_energy(hex_obj, sum_constraint)
support, isclique = extract_clique(hex_sol_list, A)
greedy = greedy_clique_from_weights(hex_sol_list, A)
print(f"{'energy':>16}{'omega_est':>12}{'clique':>9}{'time (s)':>12}")
print(f"{hex_obj:>16.6f}{omega:>12.3f}{len(greedy):>9}{hexaly_time:>12.3f}")

Preprocess model 100%Starting Hexaly solver...
Push initial solution 100%
Model:  expressions = 351, decisions = 171, constraints = 1, objectives = 1
Param:  time limit = 300 sec, no iteration limit

[objective direction ]:     minimize

[  0 sec,       0 itr]: No feasible solution found (infeas = 1)
[  1 sec,       0 itr]:    -0.857131
[  2 sec,    3325 itr]:    -0.857131
[  3 sec,    3325 itr]:    -0.857131
[  4 sec,    4314 itr]:    -0.857131
[  5 sec,    5223 itr]:    -0.857131
[  6 sec,    6774 itr]:    -0.857131
[  7 sec,    7867 itr]:    -0.857131
[  8 sec,    9437 itr]:    -0.857131
[  9 sec,   10994 itr]:    -0.862687
[ 10 sec,   13238 itr]:    -0.876333
[ optimality gap     ]:      100.00%
[ 11 sec,   15235 itr]:    -0.877773
[ 12 sec,   17245 itr]:      -0.8859
[ 13 sec,   19343 itr]:     -0.90005
[ 14 sec,   21370 itr]:    -0.903539
[ 15 sec,   21370 itr]:    -0.903539
[ 16 sec,   25828 itr]:    -0.905469
[ 17 sec,   25828 itr]:    -0.905469
[ 18 sec,   30851 itr]:    -0.908167
[ 19 sec,   33644 itr]:    -0.908375
[ 20 sec,   36420 itr]:    -0.908466
[ optimality gap     ]:      100.00%
[ 21 sec,   39307 itr]:    -0.908483
[ 22 sec,   42065 itr]:    -0.908614
[ 23 sec,   44570 itr]:    -0.908686
[ 24 sec,   47388 itr]:    -0.908952
[ 25 sec,   50274 itr]:    -0.908987
[ 26 sec,   53110 itr]:    -0.908994
[ 27 sec,   53110 itr]:    -0.908994
[ 28 sec,   58835 itr]:    -0.909018
[ 29 sec,   61408 itr]:    -0.909066
[ 30 sec,   64024 itr]:    -0.909066
[ optimality gap     ]:      100.00%
[ 31 sec,   66500 itr]:    -0.909069
[ 32 sec,   69205 itr]:    -0.909069
[ 33 sec,   71527 itr]:    -0.909069
[ 34 sec,   73792 itr]:    -0.909076
[ 35 sec,   76270 itr]:    -0.909076
[ 36 sec,   78746 itr]:    -0.909077
[ 37 sec,   81392 itr]:    -0.909078
[ 38 sec,   81392 itr]:    -0.909078
[ 39 sec,   87222 itr]:    -0.909078
[ 40 sec,   90126 itr]:    -0.909078
[ optimality gap     ]:      100.00%
[ 41 sec,   93269 itr]:    -0.909078
[ 42 sec,   96385 itr]:    -0.909078
[ 43 sec,   99380 itr]:    -0.909078
[ 44 sec,  102426 itr]:    -0.909078
[ 45 sec,  105433 itr]:    -0.909078
[ 46 sec,  108424 itr]:    -0.909078
[ 47 sec,  111565 itr]:    -0.909078
[ 48 sec,  114603 itr]:    -0.909078
[ 49 sec,  117391 itr]:    -0.909079
[ 50 sec,  120108 itr]:    -0.909079
[ optimality gap     ]:      100.00%
[ 51 sec,  122474 itr]:    -0.909079
[ 52 sec,  125205 itr]:    -0.909079
[ 53 sec,  128084 itr]:    -0.909079
[ 54 sec,  130626 itr]:    -0.909079
[ 55 sec,  133176 itr]:    -0.909079
[ 56 sec,  135706 itr]:    -0.909079
[ 57 sec,  138314 itr]:    -0.909079
[ 58 sec,  140833 itr]:    -0.909079
[ 59 sec,  143378 itr]:    -0.909079
[ 60 sec,  146050 itr]:    -0.909081
[ optimality gap     ]:      100.00%
[ 61 sec,  148770 itr]:    -0.909081
[ 62 sec,  151631 itr]:    -0.909082
[ 63 sec,  154618 itr]:    -0.909082
[ 64 sec,  157286 itr]:    -0.909082
[ 65 sec,  157286 itr]:    -0.909082
[ 66 sec,  163217 itr]:    -0.909083
[ 67 sec,  166242 itr]:    -0.909084
[ 68 sec,  169382 itr]:    -0.909084
[ 69 sec,  172338 itr]:    -0.909085
[ 70 sec,  175170 itr]:    -0.909085
[ optimality gap     ]:      100.00%
[ 71 sec,  178125 itr]:    -0.909085
[ 72 sec,  178125 itr]:    -0.909085
[ 73 sec,  183973 itr]:    -0.909085
[ 74 sec,  186766 itr]:    -0.909085
[ 75 sec,  189673 itr]:    -0.909085
[ 76 sec,  192778 itr]:    -0.909085
[ 77 sec,  195773 itr]:    -0.909085
[ 78 sec,  198713 itr]:    -0.909085
[ 79 sec,  201803 itr]:    -0.909085
[ 80 sec,  201803 itr]:    -0.909085
[ optimality gap     ]:      100.00%
[ 81 sec,  207190 itr]:    -0.909085
[ 82 sec,  207190 itr]:    -0.909085
[ 83 sec,  212949 itr]:    -0.909085
[ 84 sec,  215715 itr]:    -0.909085
[ 85 sec,  218655 itr]:    -0.909085
[ 86 sec,  221951 itr]:    -0.909085
[ 87 sec,  221951 itr]:    -0.909085
[ 88 sec,  227496 itr]:    -0.909086
[ 89 sec,  230516 itr]:    -0.909086
[ 90 sec,  230516 itr]:    -0.909086
[ optimality gap     ]:      100.00%
[ 91 sec,  236513 itr]:    -0.909086
[ 92 sec,  236513 itr]:    -0.909086
[ 93 sec,  242486 itr]:    -0.909086
[ 94 sec,  245408 itr]:    -0.909086
[ 95 sec,  248126 itr]:    -0.909086
[ 96 sec,  250778 itr]:    -0.909086
[ 97 sec,  253330 itr]:    -0.909086
[ 98 sec,  256054 itr]:    -0.909086
[ 99 sec,  258489 itr]:    -0.909086
[100 sec,  260968 itr]:    -0.909086
[ optimality gap     ]:      100.00%
[101 sec,  263513 itr]:    -0.909086
[102 sec,  265726 itr]:    -0.909086
[103 sec,  268275 itr]:    -0.909086
[104 sec,  270733 itr]:    -0.909086
[105 sec,  273060 itr]:    -0.909086
[106 sec,  275552 itr]:    -0.909086
[107 sec,  278392 itr]:    -0.909086
[108 sec,  281008 itr]:    -0.909086
[109 sec,  283671 itr]:    -0.909086
[110 sec,  286086 itr]:    -0.909086
[ optimality gap     ]:      100.00%
[111 sec,  288670 itr]:    -0.909086
[112 sec,  291137 itr]:    -0.909086
[113 sec,  293909 itr]:    -0.909086
[114 sec,  296409 itr]:    -0.909086
[115 sec,  299091 itr]:    -0.909086
[116 sec,  299091 itr]:    -0.909086
[117 sec,  304908 itr]:    -0.909086
[118 sec,  307728 itr]:    -0.909086
[119 sec,  310999 itr]:    -0.909086
[120 sec,  314277 itr]:    -0.909086
[ optimality gap     ]:      100.00%
[121 sec,  317349 itr]:    -0.909086
[122 sec,  320296 itr]:    -0.909086
[123 sec,  320296 itr]:    -0.909086
[124 sec,  326113 itr]:    -0.909086
[125 sec,  329092 itr]:    -0.909086
[126 sec,  329092 itr]:    -0.909086
[127 sec,  335396 itr]:    -0.909086
[128 sec,  338640 itr]:    -0.909086
[129 sec,  341200 itr]:    -0.909086
[130 sec,  344078 itr]:    -0.909086
[ optimality gap     ]:      100.00%
[131 sec,  347110 itr]:    -0.909086
[132 sec,  349953 itr]:    -0.909086
[133 sec,  352184 itr]:    -0.909086
[134 sec,  354731 itr]:    -0.909086
[135 sec,  357419 itr]:    -0.909087
[136 sec,  360095 itr]:    -0.909087
[137 sec,  362806 itr]:    -0.909087
[138 sec,  365352 itr]:    -0.909087
[139 sec,  365352 itr]:    -0.909087
[140 sec,  370533 itr]:    -0.909087
[ optimality gap     ]:      100.00%
[141 sec,  373308 itr]:    -0.909087
[142 sec,  376101 itr]:    -0.909087
[143 sec,  378685 itr]:    -0.909087
[144 sec,  381251 itr]:    -0.909087
[145 sec,  383659 itr]:    -0.909087
[146 sec,  386149 itr]:    -0.909087
[147 sec,  388738 itr]:    -0.909087
[148 sec,  391655 itr]:    -0.909087
[149 sec,  394462 itr]:    -0.909087
[150 sec,  397000 itr]:    -0.909087
[ optimality gap     ]:      100.00%
[151 sec,  399642 itr]:    -0.909087
[152 sec,  402699 itr]:    -0.909087
[153 sec,  402699 itr]:    -0.909087
[154 sec,  405756 itr]:    -0.909087
[155 sec,  411971 itr]:    -0.909087
[156 sec,  415034 itr]:    -0.909087
[157 sec,  418239 itr]:    -0.909087
[158 sec,  421513 itr]:    -0.909087
[159 sec,  424656 itr]:    -0.909087
[160 sec,  424656 itr]:    -0.909087
[ optimality gap     ]:      100.00%
[161 sec,  428216 itr]:    -0.909087
[162 sec,  435060 itr]:    -0.909087
[163 sec,  435060 itr]:    -0.909087
[164 sec,  441929 itr]:    -0.909087
[165 sec,  441929 itr]:    -0.909087
[166 sec,  445216 itr]:    -0.909087
[167 sec,  451503 itr]:    -0.909087
[168 sec,  451503 itr]:    -0.909087
[169 sec,  457912 itr]:    -0.909087
[170 sec,  457912 itr]:    -0.909087
[ optimality gap     ]:      100.00%
[171 sec,  464551 itr]:    -0.909087
[172 sec,  468029 itr]:    -0.909087
[173 sec,  471306 itr]:    -0.909087
[174 sec,  474419 itr]:    -0.909087
[175 sec,  477327 itr]:    -0.909087
[176 sec,  480514 itr]:    -0.909087
[177 sec,  483620 itr]:    -0.909087
[178 sec,  487032 itr]:    -0.909087
[179 sec,  490056 itr]:    -0.909087
[180 sec,  493497 itr]:    -0.909087
[ optimality gap     ]:      100.00%
[181 sec,  496608 itr]:    -0.909087
[182 sec,  499848 itr]:    -0.909087
[183 sec,  499848 itr]:    -0.909087
[184 sec,  506299 itr]:    -0.909087
[185 sec,  508972 itr]:    -0.909087
[186 sec,  511789 itr]:    -0.909088
[187 sec,  514667 itr]:    -0.909089
[188 sec,  517385 itr]:    -0.909089
[189 sec,  520268 itr]:    -0.909089
[190 sec,  522836 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[191 sec,  525872 itr]:    -0.909089
[192 sec,  528784 itr]:    -0.909089
[193 sec,  531608 itr]:    -0.909089
[194 sec,  534616 itr]:    -0.909089
[195 sec,  537383 itr]:    -0.909089
[196 sec,  539954 itr]:    -0.909089
[197 sec,  542632 itr]:    -0.909089
[198 sec,  545570 itr]:    -0.909089
[199 sec,  548398 itr]:    -0.909089
[200 sec,  551297 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[201 sec,  554429 itr]:    -0.909089
[202 sec,  557175 itr]:    -0.909089
[203 sec,  559759 itr]:    -0.909089
[204 sec,  562694 itr]:    -0.909089
[205 sec,  565547 itr]:    -0.909089
[206 sec,  568237 itr]:    -0.909089
[207 sec,  571176 itr]:    -0.909089
[208 sec,  574735 itr]:    -0.909089
[209 sec,  577673 itr]:    -0.909089
[210 sec,  580642 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[211 sec,  583653 itr]:    -0.909089
[212 sec,  586598 itr]:    -0.909089
[213 sec,  589442 itr]:    -0.909089
[214 sec,  592326 itr]:    -0.909089
[215 sec,  595230 itr]:    -0.909089
[216 sec,  598029 itr]:    -0.909089
[217 sec,  598029 itr]:    -0.909089
[218 sec,  603715 itr]:    -0.909089
[219 sec,  606305 itr]:    -0.909089
[220 sec,  609060 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[221 sec,  611936 itr]:    -0.909089
[222 sec,  614688 itr]:    -0.909089
[223 sec,  617409 itr]:    -0.909089
[224 sec,  620560 itr]:    -0.909089
[225 sec,  620560 itr]:    -0.909089
[226 sec,  627321 itr]:    -0.909089
[227 sec,  630493 itr]:    -0.909089
[228 sec,  630493 itr]:    -0.909089
[229 sec,  636469 itr]:    -0.909089
[230 sec,  639521 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[231 sec,  642689 itr]:    -0.909089
[232 sec,  645602 itr]:    -0.909089
[233 sec,  648842 itr]:    -0.909089
[234 sec,  648842 itr]:    -0.909089
[235 sec,  654819 itr]:    -0.909089
[236 sec,  657917 itr]:    -0.909089
[237 sec,  661048 itr]:    -0.909089
[238 sec,  663917 itr]:    -0.909089
[239 sec,  666937 itr]:    -0.909089
[240 sec,  669565 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[241 sec,  672445 itr]:    -0.909089
[242 sec,  675220 itr]:    -0.909089
[243 sec,  677982 itr]:    -0.909089
[244 sec,  677982 itr]:    -0.909089
[245 sec,  680901 itr]:    -0.909089
[246 sec,  687001 itr]:    -0.909089
[247 sec,  690170 itr]:    -0.909089
[248 sec,  693084 itr]:    -0.909089
[249 sec,  695904 itr]:    -0.909089
[250 sec,  698985 itr]:    -0.909089
[ optimality gap     ]:      100.00%
[251 sec,  701848 itr]:     -0.90909
[252 sec,  704659 itr]:     -0.90909
[253 sec,  707834 itr]:     -0.90909
[254 sec,  710728 itr]:     -0.90909
[255 sec,  710728 itr]:     -0.90909
[256 sec,  716856 itr]:     -0.90909
[257 sec,  716856 itr]:     -0.90909
[258 sec,  723045 itr]:     -0.90909
[259 sec,  725923 itr]:     -0.90909
[260 sec,  728868 itr]:     -0.90909
[ optimality gap     ]:      100.00%
[261 sec,  731867 itr]:     -0.90909
[262 sec,  731867 itr]:     -0.90909
[263 sec,  737897 itr]:     -0.90909
[264 sec,  740925 itr]:     -0.90909
[265 sec,  744052 itr]:     -0.90909
[266 sec,  744052 itr]:     -0.90909
[267 sec,  750594 itr]:     -0.90909
[268 sec,  753786 itr]:     -0.90909
[269 sec,  756901 itr]:     -0.90909
[270 sec,  760374 itr]:     -0.90909
[ optimality gap     ]:      100.00%
[271 sec,  763595 itr]:     -0.90909
[272 sec,  766603 itr]:     -0.90909
[273 sec,  766603 itr]:     -0.90909
[274 sec,  772846 itr]:     -0.90909
[275 sec,  776058 itr]:     -0.90909
[276 sec,  779054 itr]:     -0.90909
[277 sec,  782206 itr]:     -0.90909
[278 sec,  785332 itr]:     -0.90909
[279 sec,  788585 itr]:     -0.90909
[280 sec,  791469 itr]:     -0.90909
[ optimality gap     ]:      100.00%
[281 sec,  794388 itr]:     -0.90909
[282 sec,  797754 itr]:     -0.90909
[283 sec,  801253 itr]:     -0.90909
[284 sec,  804441 itr]:     -0.90909
[285 sec,  807556 itr]:     -0.90909
[286 sec,  810862 itr]:     -0.90909
[287 sec,  814195 itr]:     -0.90909
[288 sec,  817451 itr]:     -0.90909
[289 sec,  817451 itr]:     -0.90909
[290 sec,  823387 itr]:     -0.90909
[ optimality gap     ]:      100.00%
[291 sec,  826679 itr]:     -0.90909
[292 sec,  829774 itr]:     -0.90909
[293 sec,  832929 itr]:     -0.90909
[294 sec,  836069 itr]:     -0.90909
[295 sec,  839404 itr]:     -0.90909
[296 sec,  842945 itr]:     -0.90909
[297 sec,  846194 itr]:     -0.90909
[298 sec,  846194 itr]:     -0.90909
[299 sec,  852288 itr]:     -0.90909
[300 sec,  855388 itr]:     -0.90909
[ optimality gap     ]:      100.00%
[300 sec,  855388 itr]:     -0.90909
[ optimality gap     ]:      100.00%

855388 iterations performed in 300 seconds

Feasible solution: 
  obj    =     -0.90909
  gap    =      100.00%
  bounds =         -inf
Status: HxSolutionStatus.FEASIBLE
          energy   omega_est   clique    time (s)
       -0.909090      11.000       11     299.713