Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Discrete/combinatorial optimization has been an interesting and challenging area to researchers belonging to development of algorithms and OR techniques for real-world applications. Most such problems abstracted/taken from graph theory are NP-complete in single objective, and NP-hard for multiple objectives. There are many applications of such problems in communication topology and VLSI design.

For most such problems, there do not exist good heuristics/algorithms, therefore, black-box optimization techniques, e.g., EAs are usually preferred for getting effective solutions. In this tutorial, we will do a quick review of some of the standard combinatorial optimization problems, and then include the techniques and design of operators to effectively solve EMCO problems taken from real-world applications. This would be followed by some case-studies taken from standard problems. This interdisciplinary tutorial provides a practical foundation for -- (i) an introduction to combinatorial problems and their multiobjective versions, (ii) problem challenges and solution through EMO techniques, (iii) need of designing specialized genetic operators, representation and techniques for embedding of (limited) problem specific knowledge, (iv) few case studies taken form well known EMCO, and comparison of EMO results with the existing heuristics/approximation algorithms, and (v) improvement of the EMO solutions through hybridization using local search and others.

Key design considerations to designing operators/ representations so as to effectively explore the search space will be looked into. In general, the tutorial is aimed at quickly laying a foundation that can be used as the basis for further study, research and development in this emerging area.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation

Keywords:
combinatorial optimization, evolutionary algorithm, genetic algorithm, heuristics, multi-objective optimization, optimization methods