METHOD FOR SOLVING OPTIMIZATION PROBLEMS IN STRUCTURED COMBINATORIAL OBJECTS

• US 20120303574A1
• Filed: 08/09/2012
• Published: 11/29/2012
• Est. Priority Date: 06/18/2008
• Status: Active Grant

• Current Assignee: Reneses Ajenjo Ignacio
• Original Assignee: Reneses Ajenjo Ignacio
• Inventors: IGNACIO, RENESES AJENJO
• Granted Patent: US 9,697,464 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181

Abstract

The present invention is a method of solving the decision, for example, testing if, given a finite number of transformations which can be applied to a finite number of elements, the corresponding n-generated discrete object has a hamiltonian cycle and/or path, searching, for example, obtaining the explicit construction of one several or all the hamiltonian cycles and or paths of the given input, counting, for example, obtaining an upper bound of the number of Hamiltonian cycles and/or paths of the given input and optimization, for example, selecting one of several hamiltonian cycles and/or paths solutions according to an specified criterion, versions of the hamiltonian traversal (cycle and/or path) problem in class of combinatorial discrete objects.

Claims

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

decomposing an input into sub inputs as pairs of generators; and

classifying the sub inputs in one of several classes by testing if one to one of three possible relations holds.

7. The method of claim 1 further comprising:

determining a number of possible ending vertices in a hamiltonian cycle or path of the sub inputs and determining which are possible ending vertices in the hamiltonian cycle or path of the sub inputs; and

testing a structural property on a sub digraph of the sub inputs and classifying it according to its expected hardness.

8. The method of claim 1 further comprising:

determining a number of possible ending vertices in a hamiltonian cycle or path of the sub inputs and determining which are possible ending vertices in the hamiltonian cycle or path of the sub inputs; and

testing a structural property on a sub digraph of the sub inputs based on an intersection of sets generated by sequences of generators.

9. The method of claim 1 further comprising:

determining a number of possible ending vertices in a hamiltonian cycle or path of the sub inputs and determining which are possible ending vertices in the hamiltonian cycle or path of the sub inputs; and

testing a structural property on a sub digraph of the sub inputs, the structural property including cycle entanglement.

10. The method of claim 9, further comprising:

first reducing, by a reduction transformation, the sub inputs into an object of a same kind but of a reduced size, and second deciding a hamiltonian property based on two parameters of the reduced object.

11. The method of claim 1, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

12. The method of claim 1, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

13. The method of claim 1, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

14. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 1.

15. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 1.

41. The method of claim 7, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

42. The method of claim 7, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

43. The method of claim 1, for any finite number of generators starting from 7, when a number of elements of the input is infinite or its construction will take unlimited time.

44. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 7.

45. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 7.

46. The method of claim 8, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

47. The method of claim 8, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

48. The method of claim 8, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

49. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 8.

50. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 8.

51. The method of claim 9, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

52. The method of claim 9, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

53. The method of claim 9, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

54. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 9.

55. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 9.

56. The method of claim 10, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

57. The method of claim 10, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

58. The method of claim 10, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

59. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 10.

60. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 10.

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

decomposing an input into sub inputs as pairs of generators; and

determining a number of possible ending vertices in a hamiltonian cycle or path of the sub inputs and determining which are possible ending vertices in the hamiltonian cycle or path of the sub inputs.

16. The method of claim 2, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

17. The method of claim 2, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

18. The method of claim 2, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

19. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 2.

20. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 2.

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

decomposing an input into sub inputs as pairs of generators; and

testing a structural property on a sub digraph of the sub inputs and classifying it according to its expected hardness.

21. The method of claim 3, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

22. The method of claim 3, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

23. The method of claim 3, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

24. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 3.

25. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 3.

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

decomposing an input into sub inputs as pairs of generators; and

testing a structural property on a sub digraph of the sub inputs based on an intersection of sets generated by sequences of generators.

26. The method of claim 4, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

27. The method of claim 4, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

28. The method of claim 4, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

29. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 4.

30. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 4.

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

decomposing an input into sub inputs as pairs of generators; and

testing a structural property on a sub digraph of the sub inputs, the structural property including cycle entanglement.

31. The method of claim 5, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

32. The method of claim 5, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

33. The method of claim 5, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

34. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 5.

35. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 5.

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

decomposing an input into sub inputs as pairs of generators; and

first reducing, by a reduction transformation, the sub inputs into an object of a same kind but of a reduced size, and second deciding a hamiltonian property based on two parameters of the reduced object.

36. The method of claim 6, wherein

the input and its elements are represented as lists and sub lists;

the input and its elements are represented as sets and subsets;

the input and its elements are represented as graphs and sub graphs;

or

input and its elements are represented as digraphs and sub digraphs.

37. The method of claim 6, wherein

elements of the input are permutations of a finite set of numbers as elements and permutation transformations as generators;

elements of the input are permutations of a finite set of symbols of any kind and permutation transformations as generators;

elements of the input are matrices over finite fields and matrices transformations as generators;

elements of the input are integer numbers and arithmetic operations as generators;

elements of the input are finite-dimensional vectors and lineal transformations as generators;

elements of the input are words or strings over finite alphabets and symbolic transformations as generators;

or

elements and generators are relabeled with any kind of input, symbol or physical feature independently of data structures that represent inputs of the method.

38. The method of claim 6, for any finite number of generators starting from 2, when a number of elements of the input is infinite or its construction will take unlimited time.

39. Computer executable software code stored on a non-transitory computer readable medium, the code for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem, the code comprising code to execute the method of claim 6.

40. A programmed computer system for solving the decision, searching, counting or optimization versions of the hamiltonian cycle or path problem comprising at least one memory having at least one region storing computer executable program code and at least one processor for executing the program code stored in said memory, wherein the program code includes code to execute the method of claim 6.