Analogies of classical problems in operations research

The science of operations research (OR) is intended to be an alternative with enormous potential for solving complex problems. Traditionally, different types of problems are presented using playful contexts, for instance:

 

• Traveling Salesman Problem: find the shortest route in which the salesman visits all cities only once;
• Coloring problem: find the lowest number of colors to color a map, with neighboring countries not being painted with the same color;
• Queen's problem: position the most number of queens on a chess board in such a way that they cannot attack each other;
• Knapsack problem: maximize the value of a knapsack in such a way that the quantity of items loaded in it does not exceed its weight limit.

 

Contextualizing such problems is efficient to understand their concepts and challenges; however, for many students, this contextualization distances itself from the reality of a problem in the market. 

 

In order to appreciate these classic problems, we will show how the Knapsack Problem can serve as a basis for more complex problems.

 

Classic Knapsack Problem

 

As previously described, the problem involves maximizing the value of a knapsack in such a way that the quantity of items loaded in it does not exceed its weight limit. To make the decision that maximizes the value of the knapsack, it is necessary to know:

 

• The list of items;
• The weight of each item;
• The value of each item;
• The knapsack weight limit.

 

From them, we can define for each item if it is part of the knapsack or not, being that:

 

• The value of the knapsack is calculated by adding the individual values of each item in the knapsack;
• The weight of the knapsack is calculated by adding the individual weights of each item inside the backpack.

 

This problem, at first, appears to be directly applicable only to a seller who needs to travel by plane and comply with the hand luggage limit. How could it assist an industry?

 

Context 1

 

In its classic format, the Knapsack Problem is already capable of supporting the board's decision in investment planning. For that, we only need to (re)contextualize our concepts:

 

• List of items becomes the list of projects of the company;
• Each item's weight becomes the cost of project implementation;
• The value of each item becomes the expected financial return of the project;
• The weight limit of the knapsack becomes the available budget.

 

From this perspective, it is clear how an optimization model like the Knapsack Problem would help. It can show the ideal set of projects to be authorized to increase the return to the company. This is a problem of resource allocation!

 

Context 2

 

Another context it could be applied to is the definition of customer supply. Imagine that a company has to rent a fleet of vehicles to distribute its products. For the company, it is important to define how to load the vehicles (intended for different customers) in order to maximize its profit. In this case:

 

• List of items becomes the list of products;
• The weight of each item becomes the weight of each product;
• Each item's value becomes the price of each product;
• The weight limit of the knapsack becomes the weight limit of the vehicle.

 

In this scenario, it is important to note that it is essential to define:

• How many vehicles to rent (the cost might be greater than the revenue);
• Which vehicle serves which customer (the limit of each vehicle in the fleet may differ);
• Which product will be loaded on which vehicle (the price paid may vary per customer).

Note that the weight of the product does not vary by vehicle or by customer.

 

Context 2.1

 

The most common in industries would be to find Context 2 with additional restrictions. For example, teams can load the fleet with different rates and this should be considered when planning customer supply.

As much as the operational character of the load is emphasized, the core of the problem remains the Knapsack Problem! Operational restrictions will only exclude some of the Product-Vehicle-Customer combinations that would have previously been considered possible solutions in the model.

 

Discernment about the classification of a real problem into a classic problem by experience, however, is of great value in speeding up its resolution. Such problems already have a great theoretical basis and different technological possibilities to find the best solution.

 

For operations research enthusiasts, a tip: invest your time in understanding the classics to generate value in the future!

 

Author: Guilherme Martino - Senior Consultant at Cassotis Consulting

                                      Co-author: Fabio Silva - Senior Manager at Cassotis Consulting