Method for solving optimization problems in structured combinatorial objects

A method, implemented on one or more processors, of solving the problem of decision, searching, counting and optimizing, the method comprising the following steps:

• a pre-processing step including decomposing an input in sub inputs of pairs of generators;
• a first step (step 1) including classifying a given sub input in one of several classes by testing if one to one of three possible relations holds;
• a second step (step 2) including determining a number of possible ending vertices in a hamiltonian cycle or path of the sub input and determining which are the possible ending vertices in the hamiltonian cycle or path of the sub input;
• a third step (step 3) including discarding the possible ending vertices of the sub input that cannot be the hamiltonian cycle or path end based on a value of two parameters;
• a fourth step (step 4) including testing a structural property on a sub digraph of the sub input and classifying it according to its expected hardness;
• a fifth step (step 5) including testing another structural property on a sub digraph of the sub input based on an intersection of sets generated by sequences of generators;
• a sixth step (step 6) including testing another structural property on a sub digraph of the sub input;
• a seventh step (step 7) including first reducing, by a reduction transformation, the sub input into an object of a same kind but of a reduced size, and second deciding about a hamiltonian property based on two parameters of the reduced object;
• an eighth step (step 8) including detecting 1-compact or n-compact sub inputs by activation of several non-contradictory one-generator cycles;
• a ninth step (step 9) including selecting a given vertex in the sub input as an ending vertex and then applying a propagation including an arc-forcing subroutine and a starting- to ending-vertex-non-hamiltonian path checking plus a non hamiltonian-cycle checking by an iterative marking of a list of specified sub digraphs until no more changes happens;
• and
• a tenth step (step 10) including an iteration of:
• selecting a given arc of the sub input according to specified criteria, including the greedy criteria, the random criteria and the specific criteria for obtaining an upper bound on a number of hamiltonian cycles and paths, and
• applying a propagation consisting in an arc-forcing subroutine and a starting- to ending-vertex-non-hamiltonian path checking plus a non hamiltonian-cycle checking by the iterative marking of the list of specified sub digraphs until no more changes happens,
• until the hamiltonian cycle or path is found or a conclusion that the sub input and/or input has no hamiltonian cycle or path is reached.