Problems that have been solved using CCM

Combinatorial problems as temporary target

Although the aim of CCM is to solve real-world problems, it cannot be achieved in a short period. Our first goal has been solving combinatorial problems, such as the N queens problem, graph or map coloring problem, integer programming problems, and so on. Combinatorial problems are classified to NP-complete or NP-hard problems, which is not believed to be solved by algorithms whose time complexity is in a polynomial order.

Constraint satisfaction and optimization problems

Combinatorial problems such as the N queens or coloring problems are called constraint satisfaction problems (CSP), and those such as the integer programming problems or traveling salesperson problems are called optimization problems. CSP are problems to find a solution that satisfy all the constraints specified, and optimization problems are to find a solution, in which the objective function takes the optimal value. There are complex problems that are combination of a CSP and optimization problem. Real world problems are often formalized as constraint satisfaction and/or optimization problems.


Y. Kanada (yasusi @ kanadas.com)
Created: 11/21/95, Modified: 5/6/2002.