Combinatorial optimization, a technology serving performance

Some historical reminders on Optimization

Combinatorial optimization is a field of Artificial Intelligence¹ which mainly aims to help make the best decisions in a complex environment. Having reached its productivity plateau for several years, it is considered less hype today than automatic learning (Machine Learning) or deep learning (Deep Learning), but it was just as popular in the 1960s and 1970s. with algorithmic innovations such as the Simplex method (1947) or Branch-and-Bound (1960), and the resolution of the traveling salesman problem on 48 cities (1954).

Illustration of the traveling salesman problem (source).
The objective is to identify the shortest circuit (blue) which passes through each city (red) once and only once.

These techniques allowed, for example, oil companies to save millions of dollars in the 1960s, and commercial implementations of these techniques were well accepted because they were easily usable on the computers available at the time. Despite some disillusionment and difficulties in putting into production on large instances between the 1990s and 2000s, this technology is today mature and widely adopted by many sectors of activity (eg supply chain, logistics, energy production and distribution, planning, scheduling, vehicle tours, etc.). The following figure illustrates the evolution of interest in the mixed variable optimization technique (with integer and non-integer variables) also called MIP.

The hype cycle (Gurobi, 2020).
MIP stands for Mixed Integer Programming.

Optimization, what for?

Optimization, Operational Research, or simply OR algorithms use various modeling techniques both on a mathematical and computer level and for the transcription of a business problem. While machine learning algorithms require a significant amount of data to extract knowledge, the main added value of an optimization algorithm consists of efficiently exploring the solution space to solve a given problem. Some would say that all these approaches are complementary and this is often the case: for example, a machine learning model can be used to predict the data of an instance of a combinatorial optimization problem, or inverse a continuous optimization strategy is included in a neural network in order to minimize its cost function. In particular, learning a neural network minimizes its cost function usually according to a stochastic gradient descent which updates the network parameters by iteration; the method Adam has the advantage of automatically adjusting the updated quantity at each iteration of this descent.

Formally, an optimization algorithm aims to minimize or maximize an objective function under certain constraints, and such an approach is generally appropriate when a “combinatorial explosion” occurs; that is, when the number of solutions increases combinatorially as the size of the problem increases. For example, it would be necessary to list 60 solutions to solve the traveling salesman problem for six cities and more than  4.10³º solutions for thirty cities²! The following figure describes this phenomenon.

Linear, exponential and combinatorial growth of the number of solutions
depending on the size of the instance (medium.com)

Which optimization method to choose?

This article is not intended to list all combinatorial optimization methods³ exhaustively. However, we distinguish, for example, so-called “exact” methods such as integer linear programming (ILLP) and so-called “approximate” methods based on heuristics. The former guarantee to reach an optimal solution but the execution time can prove prohibitive while the latter make it possible to obtain admissible solutions often without guarantee of reaching the optimum while reducing the algorithmic complexity. Choosing one approach or the other a priori is not necessarily desirable and this choice essentially depends on the problem to be solved and the size of the instance to be treated. In any case, an exact MIP type approach is interesting to test at first glance. But if the execution takes too long, stopping the resolution of the MIP before the complete resolution is also a way to obtain an approximate solution. Otherwise, other approximate methods should be tested, which execute very quickly with solutions of excellent quality and close to the optimum.

A case study for Purchasing: minimization of the overall allocation

Optimization solutions, for example, find their full value in corporate purchasing functions. Indeed, in many companies, purchasing departments are regularly confronted with a specific optimization problem: to which supplier should my request be optimally allocated? In other words, this problem is used to allocate each purchase request to the best supplier. This allocation problem (or assignment) does not only aim to minimize the total cost of purchases but it must also respect a certain number of business constraints, such as:

• Respect of market shares negotiated with suppliers
• Price reductions obtained in the event of sufficiently large orders
• Respecting the manufacturing capabilities of certain suppliers

Failure to comply with these constraints can cause significant financial penalties.
Let's take the case of 250 requests to be allocated to 4 suppliers with market share constraints including penalties and price reductions depending on certain quantities of products purchased. A first approximate method called greedy was used to incrementally allocate each request to the cheapest supplier, with an execution time of less than 1 second; that is, this approach assigns the supplier with the lowest price (discounted or not) request after request. The second exact MILP type method was launched for 1.2 seconds and the solution obtained has the advantage of respecting more market shares and reducing the overall cost by almost 50% compared to the glutton's solution. The following figure illustrates this case study:

Comparison between greedy and MILP approaches
for a resource allocation problem.

For further…

There is an active French-speaking community united around the company ROADEF (French Society for Operational Research and Decision Support), created in 1998. ROADEF organizes each year a congress bringing together the French operational research community, and the association puts a lot of content online (books, links, announcements, forums, news, training) on its site.

______________________________________________________

¹ Optimization aims to respond to decision or assignment problems (prescriptive) while the other branches of AI often intervene more upstream (source).
² For the traveling salesman problem, the number of solutions is (n-1)!/2, where n is the number of cities to visit
³ A hierarchy of optimization techniques is notably available here.

______________________________________________________

Do you have an idea for a use case involving combinatorial optimization but are facing a combinatorial explosion?
Contact us to identify how OR could benefit you.