Latent Optimization

Latent optimization is an optimization paradigm pioneered by Lokad that targets hard, complex combinatorial problems. It also handles stochastic problems, which emerge whenever uncertainty is present. Latent optimization represents a breakthrough for challenges such as scheduled resource allocation. Unlike classic solvers, which operate in the solution space, latent optimization operates in the strategy space. This approach enables rapid re-optimization as conditions evolve.

Technology overview

Latent optimization, introduced in 2024, is the second generation of general-purpose optimization technologies developed by Lokad. It tackles harder combinatorial problems than those addressed by stochastic discrete descent, though it comes with a slightly reduced level of scalability.

Conceptually, the Supply Chain Scientists at Lokad design a data processing pipeline that includes the following steps:

1. Prepare the historical data.
2. Generate probabilistic forecasts.
3. Produce a robust decision-making strategy.
4. Re-optimize at the last minute, under modified conditions.

Historical data is prepared using Envision’s general data engineering capabilities; Envision is Lokad’s domain-specific language. Probabilistic forecasts are then produced using differentiable programming, a paradigm ideally suited for probabilistic modeling and treated as a first-class citizen in Envision.

Next, latent optimization is employed to generate a decision-making strategy. In essence, the outcome of latent optimization is a specialized solver narrowly tailored to the specific problem. Finally, this strategy can be run—and possibly re-run—under the final, slightly changing conditions to produce the required decisions. Because the strategy runs quickly, it can be used interactively by people in the loop.

All four steps—(1), (2), (3), and (4)—are carried out within Envision.

Limits of traditional solvers

Mathematical optimization is a mature segment of computer science. A wide range of solvers—both proprietary and open-source—are available on the market. Unfortunately, none of these existing technologies meet our requirements, particularly when dealing with tight scheduling problems.

Branch-and-bound algorithms (and all their variants) rely on partitioning the feasible region into smaller subproblems (branching) and using relaxations (bounding) to prune large sections of the search space. This approach works poorly for supply chain problems because they remain too open-ended. While the solution space is strictly constrained, it is still enormous. Merely satisfying the constraints is far from sufficient to produce a good solution, which undermines the core premise of partitioning.

Local search algorithms (and all their variants) revolve around iterating over one or several current solutions, examining nearby variants. Unfortunately, this method also performs poorly because the concept of “locality” is not well-defined in these problems. Given how strictly constrained these scenarios are, most local adjustments to a solution violate so many constraints that the search process cannot recover an improved solution.

At Lokad, we set a scalability target of a few million variables for hard combinatorial problems, along with the ability to re-optimize within a few seconds when conditions change—even if those changes completely invalidate the original solution through cascading effects.

Under the hood

Lokad uses an unorthodox approach to combinatorial optimization. Rather than offering a standard solver, we address the problem through a specialized programming paradigm called latent optimization. This method is critical for integrating the insights and expertise of our Supply Chain Scientists.

The latent optimization introduce an alternative representation of the original problem. This alternative representation is a high-dimensional parameterization of a simple solver tailored for the problem at hand. Those parameters are then learned by iteratively appplying the parameterized solver over the original problem (which many include stochastic variants). At its core, latent optimization is a learning process.

The output of latent optimization is a well-parameterized, simple solver that produces high-quality solutions for the original problem as well as for its variants.

Example: Scheduling an aviation production site

Consider an aviation manufacturer and one of its production sites. This site assembles a critical aircraft component. The overall goal is to maximize the site’s throughput given the available resources (people and industrial assets).

This assembly process involves around 100 distinct operations. There are also about 20 available slots for carrying out these operations, each slot having different attributes. Certain operations can only be performed in specific slots. A complex dependency graph connects the operations, but unlike an automotive production line, this graph does not form a straight sequence; there is considerable flexibility in the final ordering of tasks.

Additionally, some operations require specific pieces of equipment, which exist in limited quantities at the site. Many operations also depend on having the necessary inventory on hand; sometimes essential parts are delayed. Operations vary in how many people can work on them simultaneously to accelerate completion, ranging from 1 to as many as 5 individuals.

A workforce of roughly 100 technicians operates the site in shifts of 20 to 30 people. Each technician has one of three qualification levels for every operation. The highest level allows the technician to perform an operation and verify work done by others. The intermediate level enables a technician to perform and self-verify their own work. The lowest level allows a technician to perform an operation, but requires verification by a peer with the highest qualification.

Management at the production site wants a minute-by-minute job schedule for the next few weeks, specifying exactly which technician will work on each operation for each component (with each component individually identified by serial number). This level of detail is essential for ensuring confidence in the schedule’s soundness.

However, conditions can evolve at the start of every shift. An employee may be absent due to illness, or a part may be delayed and thus unavailable. If these issues are not promptly addressed, they quickly cascade into a series of inefficiencies, leaving technicians and assets idle while problems are resolved.

With latent optimization, site management can produce a detailed job schedule encompassing tens of thousands of tasks over the coming weeks. They can also re-run the tool at the last moment to account for unexpected changes. Moreover, the newly generated solution is not a massive random reshuffle of the original plan, but a schedule that closely resembles the initial version, requiring only minor adjustments to accommodate the latest conditions.