3
$\begingroup$

Context: I'm trying to solve the longest snake problem. In that question I learned that the problem is called Longest Induced Path problem, and read some papers including https://arxiv.org/pdf/2002.07012 and https://arxiv.org/pdf/2104.09227.

Now I want to implement what these papers call "fractional separation" in PySCIPOpt. A fractional separation algorithm takes fractional LP solutions and tries to find the parts that violate subtour elimination constraints.

So far, my code looks like this. I'm using TSP for demonstration purposes.

import pyscipopt as scip
from random import seed, randint
import networkx as nx

seed(2)

n = 300
dist = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i):
        dist[i][j] = randint(1, 10000)
        dist[j][i] = dist[i][j]
model = scip.Model('TSP')
edges = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(i):
        edges[i][j] = model.addVar(vtype='B', name=f'e{i}_{j}')
        edges[j][i] = edges[i][j]
for i in range(n):
    model.addCons(scip.quicksum(edges[i][j] for j in range(n)) == 2)
model.setObjective(scip.quicksum(edges[i][j] * dist[i][j] for i in range(n) for j in range(i)), 'minimize')

def heavy_cycles(graph):
    mst = nx.maximum_spanning_tree(graph)
    root = list(mst)[0]
    pred, dist = nx.dijkstra_predecessor_and_distance(mst, root)
    cycles = []
    directed_mst = nx.dfs_tree(mst, root)
    for ((u, v), lca) in nx.tree_all_pairs_lowest_common_ancestor(directed_mst, root):
        if pred[u] == [v] or pred[v] == [u] or u == v: continue
        cur_len = dist[u] + dist[v] - dist[lca] * 2 + graph.edges[u, v]['weight']
        u_path = [u]
        while u != lca:
            u = pred[u][0]
            u_path.append(u)
        v_path = [v]
        while v != lca:
            v = pred[v][0]
            v_path.append(v)
        cycle = u_path[:-1] + v_path[::-1]
        if len(cycle) - 1 < cur_len:
            cycles.append(cycle)
    print(len(cycles), 'heavy cycles found')
    return cycles

def cycles(graph):
    return [*nx.simple_cycles(graph)]

class SubtourElim(scip.Conshdlr):
    def createCons(self, name, edges):
        cons = self.model.createCons(self, name)
        cons.data = edges
        return cons
    
    def find_frac_subtours(self, cons, solution = None):
        edges = cons.data
        n = len(edges)
        graph = nx.Graph()
        for i in range(n): graph.add_node(i)
        for i in range(n):
            for j in range(i+1, n):
                graph.add_edge(i, j, weight = self.model.getSolVal(solution, edges[i][j]))
        return heavy_cycles(graph)
    
    def find_subtours(self, cons, solution = None):
        edges = cons.data
        n = len(edges)
        graph = nx.Graph()
        for i in range(n): graph.add_node(i)
        for i in range(n):
            for j in range(i+1, n):
                if self.model.getSolVal(solution, edges[i][j]) > 0.5:
                    graph.add_edge(i, j)
        return cycles(graph)
    
    def conscheck(self, constraints, solution, check_integrality, check_lp_rows, preint_reason, completely, **results):
        for cons in constraints:
            loops = self.find_subtours(cons, solution)
            if len(loops) >= 2:
                return {'result': scip.SCIP_RESULT.INFEASIBLE}
        return {'result': scip.SCIP_RESULT.FEASIBLE}
    
    def consenfolp(self, constraints, n_useful_conss, sol_infeasible):
        consadded = False
        for cons in constraints:
            subtours = self.find_subtours(cons)
            edges = cons.data
            if len(subtours) >= 2:
                for tour in subtours:
                    self.model.addCons(scip.quicksum(edges[i][j] for i in tour for j in tour if i > j) <= len(tour) - 1)
                    consadded = True
        if consadded:
            print('consenfolp: constraint added')
            return {'result': scip.SCIP_RESULT.CONSADDED}
        return {'result': scip.SCIP_RESULT.FEASIBLE}
    
    def conslock(self, constraint, locktype, nlockspos, nlocksneg):
        pass

class SubtourElimFrac(scip.Conshdlr):
    def createCons(self, name, edges):
        cons = self.model.createCons(self, name)
        cons.data = edges
        return cons
    
    def find_frac_subtours(self, cons, solution = None):
        edges = cons.data
        n = len(edges)
        graph = nx.Graph()
        for i in range(n): graph.add_node(i)
        for i in range(n):
            for j in range(i+1, n):
                graph.add_edge(i, j, weight = self.model.getSolVal(solution, edges[i][j]))
        return heavy_cycles(graph)
    
    def find_subtours(self, cons, solution = None):
        edges = cons.data
        n = len(edges)
        graph = nx.Graph()
        for i in range(n): graph.add_node(i)
        for i in range(n):
            for j in range(i+1, n):
                if self.model.getSolVal(solution, edges[i][j]) > 0.5:
                    graph.add_edge(i, j)
        return cycles(graph)
    
    def conscheck(self, constraints, solution, check_integrality, check_lp_rows, preint_reason, completely, **results):
        return {'result': scip.SCIP_RESULT.FEASIBLE}
    
    def consenfolp(self, constraints, n_useful_conss, sol_infeasible):
        consadded = False
        for cons in constraints:
            subtours = self.find_frac_subtours(cons)
            edges = cons.data
            for tour in subtours:
                self.model.addCons(scip.quicksum(edges[i][j] for i in tour for j in tour if i > j) <= len(tour) - 1)
                consadded = True
                break
        if consadded:
            print('Frac: consenfolp: constraint added')
            return {'result': scip.SCIP_RESULT.CONSADDED}
        return {'result': scip.SCIP_RESULT.FEASIBLE}
    
    def conslock(self, constraint, locktype, nlockspos, nlocksneg):
        pass
    
conshdlr = SubtourElim()
conshdlr_frac = SubtourElimFrac()
model.includeConshdlr(conshdlr, 'subtour_elim', 'TSP subtour eliminator',
                      chckpriority = -2000002, enfopriority = -1)
model.includeConshdlr(conshdlr_frac, 'fractour_elim', 'TSP fractional subtour eliminator',
                      chckpriority = -2000001, enfopriority = 1, proptiming = scip.SCIP_PROPTIMING.AFTERLPNODE)
cons = conshdlr.createCons('subtour_elim', edges)
consfrac = conshdlr_frac.createCons('fractour_elim', edges)
model.addPyCons(cons)
model.addPyCons(consfrac)
model.optimize()

The issue is that I can't figure out the correct parameters to model.includeConshdlr when including SubtourElimFrac. In order to generate constraints from fractional LP solution, I understand that enfopriority must be positive. However, when I set it to 1, the LP loop seems to get stuck, repeatedly calling consenfolp of SubtourElimFrac with the same solution:

presolving:
   (1.0s) probing: 51/44850 (0.1%) - 0 fixings, 0 aggregations, 0 implications, 0 bound changes
   (1.0s) probing aborted: 50/50 successive totally useless probings
   (1.0s) symmetry computation started: requiring (bin +, int +, cont +), (fixed: bin -, int -, cont -)
   (1.0s) could not compute symmetry
presolving (1 rounds: 1 fast, 1 medium, 1 exhaustive):
 0 deleted vars, 0 deleted constraints, 0 added constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0 changed coefficients
 0 implications, 0 cliques
presolved problem has 44850 variables (44850 bin, 0 int, 0 impl, 0 cont) and 302 constraints
    300 constraints of type <linear>
      1 constraints of type <fractour_elim>
      1 constraints of type <subtour_elim>
transformed objective value is always integral (scale: 1)
Presolving Time: 1.00

 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl. 
  1.0s|     1 |     0 |   566 |     - |   256M |   0 |  44k| 304 | 300 |   0 |  0 |   2 |   0 | 2.147200e+04 |      --      |    Inf | unknown
2 heavy cycles found
Frac: consenfolp: constraint added
  2.0s|     1 |     0 |   574 |     - |   257M |   0 |  44k| 305 | 301 |   0 |  1 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  2.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 306 | 302 |   0 |  2 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  3.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 307 | 303 |   0 |  3 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  3.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 308 | 304 |   0 |  4 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  3.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 309 | 305 |   0 |  5 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  4.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 310 | 306 |   0 |  6 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  4.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 311 | 307 |   0 |  7 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  5.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 312 | 308 |   0 |  8 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  5.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 313 | 309 |   0 |  9 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  5.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 314 | 310 |   0 | 10 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  6.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 315 | 311 |   0 | 11 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  6.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 316 | 312 |   0 | 12 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  7.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 317 | 313 |   0 | 13 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  7.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 318 | 314 |   0 | 14 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
  7.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 319 | 315 |   0 | 15 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  8.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 320 | 316 |   0 | 16 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  8.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 321 | 317 |   0 | 17 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  9.0s|     1 |     0 |   574 |     - |   308M |   0 |  44k| 322 | 318 |   0 | 18 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  9.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 323 | 319 |   0 | 19 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
  9.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 324 | 320 |   0 | 20 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 10.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 325 | 321 |   0 | 21 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 10.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 326 | 322 |   0 | 22 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 11.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 327 | 323 |   0 | 23 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 11.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 328 | 324 |   0 | 24 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 12.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 329 | 325 |   0 | 25 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 12.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 330 | 326 |   0 | 26 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 12.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 331 | 327 |   0 | 27 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 13.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 332 | 328 |   0 | 28 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 13.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 333 | 329 |   0 | 29 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 13.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 334 | 330 |   0 | 30 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 14.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 335 | 331 |   0 | 31 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 14.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 336 | 332 |   0 | 32 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 15.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 337 | 333 |   0 | 33 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 15.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 338 | 334 |   0 | 34 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 15.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 339 | 335 |   0 | 35 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 16.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 340 | 336 |   0 | 36 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 16.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 341 | 337 |   0 | 37 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 17.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 342 | 338 |   0 | 38 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 17.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 343 | 339 |   0 | 39 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 17.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 344 | 340 |   0 | 40 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 18.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 345 | 341 |   0 | 41 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 18.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 346 | 342 |   0 | 42 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 19.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 347 | 343 |   0 | 43 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 19.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 348 | 344 |   0 | 44 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 19.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 349 | 345 |   0 | 45 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 20.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 350 | 346 |   0 | 46 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 20.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 351 | 347 |   0 | 47 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 20.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 352 | 348 |   0 | 48 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 21.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 353 | 349 |   0 | 49 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 21.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 354 | 350 |   0 | 50 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 22.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 355 | 351 |   0 | 51 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 22.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 356 | 352 |   0 | 52 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 22.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 357 | 353 |   0 | 53 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 23.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 358 | 354 |   0 | 54 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 23.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 359 | 355 |   0 | 55 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 24.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 360 | 356 |   0 | 56 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 24.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 361 | 357 |   0 | 57 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 24.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 362 | 358 |   0 | 58 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 25.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 363 | 359 |   0 | 59 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 25.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 364 | 360 |   0 | 60 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 26.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 365 | 361 |   0 | 61 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 26.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 366 | 362 |   0 | 62 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 26.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 367 | 363 |   0 | 63 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 27.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 368 | 364 |   0 | 64 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 27.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 369 | 365 |   0 | 65 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 28.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 370 | 366 |   0 | 66 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 28.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 371 | 367 |   0 | 67 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 28.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 372 | 368 |   0 | 68 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 29.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 373 | 369 |   0 | 69 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 29.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 374 | 370 |   0 | 70 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 30.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 375 | 371 |   0 | 71 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 30.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 376 | 372 |   0 | 72 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 30.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 377 | 373 |   0 | 73 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 31.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 378 | 374 |   0 | 74 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 time | node  | left  |LP iter|LP it/n|mem/heur|mdpt |vars |cons |rows |cuts |sepa|confs|strbr|  dualbound   | primalbound  |  gap   | compl.
 31.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 379 | 375 |   0 | 75 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 32.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 380 | 376 |   0 | 76 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 32.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 381 | 377 |   0 | 77 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 32.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 382 | 378 |   0 | 78 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 33.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 383 | 379 |   0 | 79 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 33.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 384 | 380 |   0 | 80 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 34.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 385 | 381 |   0 | 81 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
 34.0s|     1 |     0 |   574 |     - |   309M |   0 |  44k| 386 | 382 |   0 | 82 |   2 |   0 | 2.147333e+04 |      --      |    Inf | unknown
76 heavy cycles found
Frac: consenfolp: constraint added
forrtl: error (200): program aborting due to control-C event

I believe I want the constraint handler to be called only once per LP node, when the fractional LP solution is found. How do I achieve it, if possible?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

While writing the question, I tried these changes to SubtourElimFrac:

  • do nothing and simply return FEASIBLE for conscheck and consenfolp
  • add a custom implementation of conssepalp that does the same thing as the previous consenfolp but returns the correct output codes:
    def conssepalp(self, constraints, n_useful_conss):
        consadded = False
        for cons in constraints:
            subtours = self.find_frac_subtours(cons)
            edges = cons.data
            for tour in subtours:
                self.model.addCons(scip.quicksum(edges[i][j] for i in tour for j in tour if i > j) <= len(tour) - 1)
                consadded = True
                break
        if consadded:
            print('Frac: conssepalp: constraint added')
            return {'result': scip.SCIP_RESULT.CONSADDED}
        return {'result': scip.SCIP_RESULT.DIDNOTFIND}
  • set sepapriority and sepafreq to a positive integer
model.includeConshdlr(conshdlr_frac, 'fractour_elim', 'TSP fractional subtour eliminator',
                      chckpriority = -2000001, enfopriority = -1, sepapriority = 1, sepafreq = 1)

The log doesn't look like what I expected (one call per node), but the solver is no longer stuck and intended lazy constraints are being added and solved.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The behaviour "one call per node" is not the default mode, the default is to call the fractional separation until there is no more fractional violated solutions. For instance, if at node $n_i^k$, for the $i$-th node of depth $k$ from the BB tree, the solution $x_i^k$ violates some fractional cut $H(x_i^k) \leqslant 0$ (such cut detected by your separation algorithm) will be added to the current linear problem, and the execution proceeds within the same node, until your separation algorithm is not albe to find some $H(x_i^k) > 0$, and then the BB nodes derivation continues.+ $\endgroup$
    – Matheus Diógenes Andrade
    Commented Oct 11 at 8:14
  • $\begingroup$ So, if you want to impose the "one call per node", you could keep in an outer scope some flag (maybe a dictionary mapping integers to booleans) telling whether a BB node of a given ID (not sure what is the function for this in scip) was already explored by your separation algorithm, if so, simply disable the separation. $\endgroup$
    – Matheus Diógenes Andrade
    Commented Oct 11 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.