About The Solution Of Combinatorical Problems With Problem Solving Methods

TL;DR

This paper presents a problem-solving framework for combinatorial optimization problems, particularly relevant to electrical and mechanical engineering design. They adapt artificial intelligence search techniques, specifically state-space search with heuristic operators, to efficiently find near-optimal solutions for complex design tasks like component placement on circuit boards.

What Problem Does This Paper Address?

The paper tackles the challenge of solving large-scale combinatorial problems that arise frequently in engineering design. These problems involve selecting a subset of elements with specific properties from a vast set of possibilities, aiming to optimize a particular objective function (e.g., minimizing connections). Traditional brute-force methods are computationally infeasible for these problems. The authors highlight the need for efficient, intelligent search strategies that can navigate the enormous state space of potential solutions. They focus on problems where solutions are characterized by partitions of sets and where the goal is to find partitions that minimize or maximize a cost function.

Methods

The core of the paper lies in applying the state-space approach from artificial intelligence problem-solving to combinatorial optimization. They define:

  • State Space: The set of all possible solution objects.
  • Operators: Rules or actions that transform one state (solution) into another.
  • Heuristic Rules: "Rules of thumb" or weights assigned to operators to guide the search towards more promising states.

They introduce several sets of operators (O1-O5) tailored for different types of combinatorial problems, particularly decomposition and selection problems. For instance, operators can interchange elements within subsets, join subsets, or combine subsets with other elements. The novelty lies in defining specific heuristic weights for these operators. These weights are derived from the cost function of the problem, aiming to prioritize operators that are likely to lead to better solutions. The search process involves iteratively selecting an operator based on its weight, applying it to the current state, and repeating until a break-off point is reached.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic framework and provides examples of problem types rather than specific datasets.

Key Insights and Ideas

  • Bridging AI and Engineering Design: The paper demonstrates a practical application of AI problem-solving techniques to real-world engineering design challenges, moving beyond theoretical applications in robotics or question-answering systems.
  • Heuristic Operator Selection is Key: The effectiveness of the search heavily relies on well-defined heuristic rules (weights) for operator selection. These rules, derived from the problem's cost function, guide the search efficiently.
  • Decomposition and Selection Problems as Core Examples: The authors frame a broad class of combinatorial problems into two main categories: decomposition (partitioning a set) and selection (choosing elements based on relationships).
  • Iterative Refinement: The algorithms are designed for iterative refinement, where an initial admissible solution is generated and then improved through further operator applications.
  • Trade-off Between Solution Quality and Search Time: The paper implicitly discusses the trade-off between finding the absolute optimal solution (which is computationally expensive) and finding a "good enough" solution quickly using heuristics.

Key Results

The paper presents statistical results from applying their algorithms to practical problems:

  • Decomposition Problem (with restrictions): For partitioning sets of size 72, their algorithm generated partitions with costs approximately 10% lower than random partitions, with a significantly lower variability coefficient (3.5% vs. unspecified for random).
  • Decomposition Problem (with restrictions) on a smaller set: For a set of size 24, their algorithm achieved costs 18% lower than random partitions, with a variability coefficient of 3%.
  • Placement of Logical Elements: The developed program for placing logical elements on circuit boards enabled routing of connections with 96-98% success.

Limitations and Future Work

  • Probabilistic Optimality: The algorithms do not guarantee finding the absolute optimal solution with probability 1. They aim for efficient generation of good solutions.
  • Focus on Structural Relationships: Current investigations are limited to problems with structural relationships between elements (e.g., connections, information flow).
  • Future Work: The authors express interest in:
  • Developing methods to estimate the probability of reaching extremal cost values.
  • Incorporating functional features of elements (beyond structural relationships) into the problem-solving process.
  • Automating synthesis problems as part of design processes.

Summary updated

BibTeX
@inproceedings{1975about,
  title = {{About The Solution Of Combinatorical Problems With Problem Solving Methods}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1975},
}
Figure