AILab Howest

Examples of common optimization problems

Some classics from the world of combinatorial optimization:

• Knapsack problemhow do you choose a subset of objects with a certain value and weight, so that you can fit as much value as possible into one backpack without exceeding the weight limit?
• Bin packingHow do you distribute objects into as few bins as possible without exceeding the maximum capacity of a bin?
• Traveling Salesman Problem (TSP)What is the shortest route through a series of cities where each city is visited exactly once?
• Task planningHow do you assign tasks to time slots and resources, taking into account dependencies and constraints?

An example animation for the Traveling Salesman Problem

Bin packing problem with 3 bins

These optimization problems may seem abstract, but they are the foundation of many practical applications. Theknapsack problemyou can apply it, for example, to optimizing the load in a truck or drone: how do you take as many valuable goods as possible without exceeding the weight limit? This is also relevant in marketing, for example, when selecting the most profitable combination of advertisements within a fixed budget. Or when creating a schedule for an operating room, taking into account different operations that each have their own duration, available staff, and varying priority.

Many of these problems are NP-hard. This means that the computational complexity increases exponentially with the size of the problem, making brute force not an option. Instead, we look for smart heuristics that find good solutions in acceptable time. One such technique is the genetic algorithm.

Genetic algorithms: evolution as an optimization strategy

Genetic algorithms (GAs) are inspired by the process of natural selection. Instead of improving a single solution, you work with a population of solutions that evolves over multiple generations.

Each solution is presented as achromosomea series of "genes" that together encode the choices within the problem. For example, think of a list that indicates for each object in a bin packing problem which box it is in. Each combination is a possible solution.

The process proceeds in steps:

1. InitializationA starting population is randomly generated. This group contains a number of different solution candidates.
2. Fitness functionEach solution is evaluated based on afitness scoreIn a bin packing context, this can be based on the number of boxes used, how well the space is utilized, and whether any constraints have been violated. The higher the fitness, the better the solution.
3. SelectionThen we select the most promising solutions — the 'fittest' — as parents for the next generation. This can be done through techniques such astournament selection, where multiple solutions "compete" against each other and the best one wins. It is important that for an optimal final result, even less fit solutions are taken into account.
4. Variation: mutation and recombinationDoormutationwe make small random changes (e.g., swapping two items). This helps to explore the search space and avoid local optima. Throughrecombination(in crossover) we combine properties of two or more parents to form a new child. For example: inuniform crossoverIt is decided for each gene separately whether it comes from parent 1 or parent 2.
5. ReplacementThe new generation of solutions partially replaces the old ones. This can be based on age (the oldest are removed) or based on fitness (the least successful disappear).
6. Stopping criterionThe process stops when the improvement stagnates, a predetermined number of generations has been reached, or the fitness score has reached a desired level.

One of the strengths of genetic algorithms is their flexibility. They can handle complex, non-linear problems with many constraints. Moreover, they are relatively easy to implement and can be easily adapted to the needs of a specific problem.

Google OR-Tools: powerful optimization software

Those who prefer to work with a ready-to-use tool can turn to Google OR-Tools. This is an open-source software package developed by Google, specifically aimed at solving combinatorial optimization problems.

OR-Tools supports among other things:

• Bin packing & knapsack
• Routing problems (such as TSP)
• Planning & scheduling
• Graphs and networks

Although OR-Tools is not necessarily based on genetic algorithms, it includes several powerful solvers such as constraint programming and local search methods. Thanks to the clear APIs in Python, Java, and C++, it is a practical choice for developers who want to quickly get started with real-life optimization problems.