Optimisation
Houcem
Combinatorial optimization: a mature technology for performance
This article explores combinatorial optimization, an AI field for optimal decision-making in complex contexts. While it receives less media attention than machine learning, it offers mature applications. This text presents methods such as linear programming, heuristics, and includes a case study on procurement optimization.
Combinatorial optimization is a field of Artificial Intelligence¹ primarily aimed at helping make the best decisions in complex environments. Having reached its plateau of productivity several years ago, it is considered less "hyped" today than machine learning or deep learning. However, it was just as popular in the 1960s and 1970s, driven by algorithmic innovations like the Simplex method (1947), Branch-and-Bound (1960), and the resolution of the traveling salesperson problem for 48 cities (1954).
These techniques allowed oil companies, for example, to save millions of dollars in the 1960s, and commercial implementations were well-received because they were easily usable on the computers available at the time. Despite some disappointments and difficulties in deploying large-scale instances between the 1990s and 2000s, this technology is now mature and widely adopted across many industries (e.g., supply chain, logistics, energy production and distribution, planning, scheduling, vehicle routing, etc.). The following figure illustrates the evolution of interest in Mixed-Integer Programming, also known as MIP.
Optimization algorithms, or Operations Research (OR), rely on various modeling techniques, both in terms of mathematics and computer science, as well as in translating business problems. While machine learning algorithms require a significant amount of data to extract knowledge, the primary added value of an optimization algorithm lies in efficiently exploring the solution space to solve a given problem. Some might say that all these approaches are complementary, and that is very often the case: for example, a machine learning model can be used to predict data for an instance of a combinatorial optimization problem, or conversely, a continuous optimization strategy can be included in a neural network to minimize its cost function. In particular, training a neural network usually minimizes its cost function using stochastic gradient descent, which updates the network's parameters iteratively; the method Adam has the advantage of automatically adjusting the update amount 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, you would need to enumerate 60 solutions to solve the traveling salesperson problem for six cities, and more than 4.10³º solutions for thirty cities²! The following figure describes this phenomenon.
This article is not intended to be an exhaustive list of all combinatorial optimization methods³. Nevertheless, we can distinguish, for example, between "exact" methods such as Mixed-Integer Linear Programming (MILP) and "approximate" methods based on heuristics. The former guarantee reaching an optimal solution, but the execution time can prove prohibitive, while the latter allow for obtaining feasible solutions, often without a guarantee of reaching the optimum, while reducing algorithmic complexity. Choosing one approach over the other a priori is not necessarily desirable, and this choice depends essentially on the problem to be solved and the size of the instance to be processed. In any case, an exact MIP-type approach is worth testing first. But if execution takes too long, stopping the MIP resolution before it is complete is also a way to obtain an approximate solution. Otherwise, other approximate methods should be tested, which run very quickly and provide excellent, near-optimal solutions.
Optimization solutions find their full value in corporate procurement functions for instance. Indeed, in many companies, procurement departments are regularly faced with a specific optimization problem: to which supplier should I optimally allocate my demand? In other words, this problem is used to allocate each purchase request to the best supplier. This allocation (or assignment) problem does not only aim to minimize the total cost of purchases, but it must also respect a certain number of business constraints, such as:
Failure to comply with these constraints can result in significant financial penalties.
Consider the case of 250 requests to be allocated to 4 suppliers with market share constraints, including penalties and price discounts based on certain quantities of products purchased. A first, approximate "greedy" method 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 assigns the supplier with the lowest price (discounted or not) request by request. The second, exact MILP-type method was run for 1.2 seconds, and the resulting solution has the advantage of meeting more market share requirements and reducing the overall cost by nearly 50% compared to the greedy solution. The following figure illustrates this case study:
There is an active French-speaking community centered around the ROADEF (French Operations Research and Decision Support Society), founded in 1998. ROADEF organizes an annual congress that brings together the French operations research community, and the association provides a wealth of content (books, links, announcements, forums, news, training) on its website.
______________________________________________________
¹ Optimization aims to address decision or allocation problems (prescriptive), whereas other branches of AI often intervene further upstream (source).
² For the traveling salesperson problem, the number of solutions is (n-1)!/2, where n is the number of cities to visit
³ A hierarchy of optimization techniques is available here.
______________________________________________________
Do you have a use case in mind involving combinatorial optimization, but you are facing a combinatorial explosion?
Contact us to identify how O.R. could be useful to you.
Lorem ipsum dolor sit amet consectetur. Ipsum penatibus viverra feugiat amet varius pharetra porta risus lectus. Turpis enim massa non tincidunt in faucibus.
