This article explores thecombinatorial optimization, an AI domain for optimal decisions In complex contexts. Less publicized than machine learning, it offers mature applications. The text introduces methods such as the linear programming, the Heuristics, with a case study on the optimization of purchases.

Some historical reminders about Optimization

Combinatorial optimization is a field of Artificial Intelligence¹ that primarily aims to help make the best decisions in a complex environment. Having reached its productivity plateau in recent years, it is now considered less hyped than Machine Learning or Deep Learning, but it was just as hyped in the years 1960-1970 with algorithmic innovations such as the Simplex method (1947) or the Branch-and-Bound method (1947) or Branch-and-Bound (1960), and the resolution of the commercial traveller problem in 48 cities (1954).

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

For example, these techniques allowed 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 computers available at the time. Despite some disappointments and difficulties in setting up production on large instances between the years '90 and 2000, this technology is now mature and widely adopted by many sectors of activity (e.g. supply chain, logistics, energy production and distribution, 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, for what?

Optimization, Operational Research, or simply R.O. algorithms, use a variety of modeling techniques both mathematically and computationally and for the transcription of a business problem. While machine learning algorithms require a large amount of data to extract knowledge, the main added value of an optimization algorithm is to effectively explore 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 conversely, 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 that updates the network parameters by iteration; the method adam has the advantage of automatically adjusting the quantity updated 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 there is a “combinatorial explosion”; that is, when the number of solutions increases combinatorially as the size of the problem increases. For example, 60 solutions to solve the commercial traveller problem should be listed for six cities and more than 4.10³º solutions for thirty cities²! The following figure describes this phenomenon.

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

What optimization method should you choose?

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

A case study for Purchasing: minimizing the overall allocation

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

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

Failure to comply with these constraints can cause significant financial penalties.
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 gluttony was used to incrementally allocate each request to the cheapest supplier, with an execution time of less than 1 second; in other words, this approach affects the supplier with the lowest price (reduced or not) the lowest request after request. The second exact MILP 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 glutton and MILP approaches
for a resource allocation problem.

To go further...

There is an active French-speaking community federated around the company ROADEF (French Society for Operational Research and Decision Support), created in 1998. Each year, ROADEF organizes a conference 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 earlier (stream).
² For the traveling salesman problem, the number of solutions is (n-1)! /2, where n is the number of cities to visit
³ In particular, a hierarchy of optimization techniques is available hither.

______________________________________________________

Do you have an idea of use cases involving combinatorial optimization but are you facing a combinatorial explosion?
Contact us to find out how R.O. could be useful to you.

Latest blog posts

Discover our articles on the latest trends, advances, or applications of AI today.

Diane
Business Developer
Aqsone
Squad Com'
Innovation

Artificial Intelligence in Industrial Procurement

Learn more
Nicolas
Data Scientist
Aqsone
Squad Com'
Portrait

Discover Nicolas with his Chinese portrait

Learn more
Paul
Data Scientist
Aqsone
Squad Com'
Technical

The ethics of Artificial Intelligence

Learn more