AI Techniques for Combinatorial Optimization

Carlos A. S. Oliveira ()
Additional contact information
Carlos A. S. Oliveira: AT&T Labs Inc.

Chapter Chapter 7 in Handbook of Artificial Intelligence and Data Sciences for Routing Problems, 2025, pp 123-135 from Springer

Abstract: Abstract Optimization problems are prevalent across various industrial sectors such as agriculture, transportation, and administration, where the goal is to efficiently allocate resources to achieve specific objectives. These problems often involve minimizing or maximizing a function subject to constraints, and they can be mathematically formalized as a set of equalities and inequalities. Depending on the nature of the objective function and constraints, optimization problems can be classified into different categories, including linear programming and combinatorial optimization. This paper introduces the fundamental concepts of optimization problems, provides examples of real-world applications, and delves into specific problem types such as the Traveling Salesman Problem (TSP) and the Knapsack Problem. The TSP, a well-known combinatorial optimization problem, seeks the shortest possible route that visits a set of cities exactly once and returns to the origin, with applications ranging from circuit design to logistics. The Knapsack Problem, another classic example, involves selecting items with maximum value within a given capacity, with practical applications in resource allocation and investment decisions. Despite their simple formulations, both problems pose significant computational challenges, particularly when finding optimal solutions for large instances.

Keywords: Optimization; Metatheuristics; TSP; Tabu search; Genetic algorithms (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-78262-6_7

Ordering information: This item can be ordered from
http://www.springer.com/9783031782626

DOI: 10.1007/978-3-031-78262-6_7

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().