RL and Mathematical Programming: Optimization of Business Tasks

Optimization: Bridging Mathematical Programming and Reinforcement Learning

For decades, classical mathematical programming methods have served as the bedrock for automating and optimizing business processes such as routing, production planning, and logistics. However, with the advancements in artificial intelligence, particularly in Reinforcement Learning (RL), a critical question arises: Can these new paradigms surpass or at least complement traditional approaches in solving complex optimization problems? This article explores RL's potential in combinatorial optimization, analyzing both integrated strategies and standalone solutions, and delves into a specific logistics example.

RL in Combinatorial Optimization: Hybrid and Autonomous Approaches

Progress in Reinforcement Learning is largely attributed to iterative testing, where each task becomes a proving ground for model refinement. This trial-and-error approach has enabled RL to adapt to Combinatorial Optimization (CO) problems, which are characterized by a vast space of possible solutions. In CO, RL is utilized in two primary ways: as a component to enhance existing algorithms and as a standalone technology for finding solutions. This opens new horizons for overcoming computational complexities and improving system adaptability.

Integrating RL with Traditional Optimization Methods

Integrating RL with classical optimization methods allows for leveraging the strengths of each approach. RL brings adaptability and the ability to learn from experience, while classical algorithms offer guaranteed convergence and proven heuristics. This hybrid approach effectively tackles problems where purely classical methods encounter exponential complexity growth.

Key integration strategies include:

RL as an Initial Solution Generator: An RL agent learns to create high-quality initial solutions, which are then refined by exact methods, such as the branch and bound method or linear programming. This significantly reduces the search time for an optimal solution, for example, in the Traveling Salesperson Problem (TSP), where RL can quickly suggest a near-optimal route.
Hybrid Algorithms with Local Search: RL identifies promising directions for improvement, while local heuristics (e.g., 2-opt, 3-opt) perform specific modifications. The agent learns to select the most effective operations in the current state, thereby reducing computational load and accelerating convergence.
RL for Metaheuristic Parameter Adaptation: Metaheuristic algorithms (e.g., genetic algorithms, simulated annealing) have numerous tunable parameters. An RL agent can dynamically adjust these parameters during the solution process, optimizing, for instance, crossover and mutation probabilities in a genetic algorithm based on current progress.
Hierarchical RL for Problem Decomposition: Complex problems are broken down into sub-problems, each solved by an individual RL agent or a classical algorithm. For example, at the top level, RL might cluster cities in a TSP, while at the lower level, exact methods optimize routes within each cluster.
RL in Branch and Bound: In this method, RL can be used to select the next branch to explore, evaluate the potential of nodes, or prune the search space by predicting bounds, thereby increasing algorithm efficiency.

Neural Combinatorial Optimization (NCO): Modern Implementations and Limitations

Neural Combinatorial Optimization (NCO) represents a field that merges neural networks with the demands of combinatorial optimization. NCOs are particularly effective for dynamic problems requiring rapid solution generation and in scenarios where traditional methods prove too slow. However, current NCO capabilities are still limited, and they are not a universal solver for all problems. Their successful application is often associated with academic settings or small-scale problems with specific constraints.

Examples of problems that can theoretically be solved using NCO (with caveats regarding size and conditions):

Traveling Salesperson Problem (TSP): Finding the shortest route that visits a given set of cities exactly once. NCOs can utilize Pointer Networks or Graph Neural Networks (GNNs) to generate permutations.
Vehicle Routing Problem (VRP): Optimizing routes for a fleet of vehicles, considering capacity or time window constraints.
Knapsack Problem: Selecting items with maximum value under weight/volume constraints.
Set Cover Problem: Choosing a minimum set of sets that cover all elements.
Job-Shop Scheduling: Allocating operations to machines to minimize total completion time.
Graph Coloring: Minimizing the number of colors for adjacent vertices, used in scheduling.
Facility Location Problem: Optimal placement of warehouses or charging stations.
Supply Chain Optimization: Planning procurement, production, and delivery while accounting for uncertainties.
Assignment Problem: Optimal matching of agents to tasks, such as taxis to passengers.
SAT Problem: Determining the satisfiability of Boolean formulas.

Despite these examples, a significant gap exists between the theoretical capabilities of RL in classical formulations and their practical application. Bridging this gap requires further research and development.

Practical Example: Fuel Stop Optimization in Freight Transportation with RL

Let's consider a practical problem from the logistics domain: optimizing fuel costs in freight transportation. Fuel expenses constitute a significant portion of operational costs, often reaching up to a third of total expenses. Strategic planning of fuel stops along a route can substantially reduce these costs, given the price variations at different gas stations. Often, this process is delegated to drivers who are not always focused on cost minimization, creating significant potential for optimization.

Business Task: Determine optimal fuel stop locations (gas stations) and fuel volumes along a route, minimizing total costs while adhering to several constraints:

Minimum Fuel Level: At any point on the route, the fuel tank level must not drop below a specified threshold.
Tank Capacity: The fuel volume must not exceed the maximum tank capacity.
Final Fuel Level: At the end of the route, the tank must contain at least a threshold amount of fuel.
Minimum Refueling Volume: Refueling must be economically viable, meaning the volume must exceed a set minimum.

For RL application, the continuous solution space of refueling volume is discretized. For example, five refueling options are considered: 0%, 25%, 50%, 75%, and 100% of the available tank space. This simplifies state management in RL without significantly distorting results for research purposes.

Formulating the Problem as Nonlinear Programming

The problem of optimizing gas station selection and refueling volumes can be formalized as a nonlinear programming problem. The following components are introduced:

Indices:

i — indices of gas stations.

Constants:

c_i — fuel consumption volume between gas stations i-1 and i.
p_i — cost of refueling at gas station i.
v_min — minimum refueling volume at a gas station.
s_0, s_n — fuel volume in the tank at the start and end of the route.
s_lb, s_ub — minimum and maximum fuel volume in the tank.
w — penalty size for violating the minimum fuel level.

Variables:

s_i — fuel volume in the tank at the i-th gas station after refueling (real).
v_i — refueling volume at the i-th gas station (real).
q_i — refueling percentage at the i-th gas station (integer, from 0 to 4 for 0%, 25%, 50%, 75%, 100%).
b_i — indicator of refueling at the i-th gas station (binary).
z_i — magnitude of minimum fuel level violation (real).

Objective Function: Minimize total fuel costs and penalties for minimum fuel level violations:

min Σ (p_i v_i + w z_i) for all i in the set of gas stations.

Constraints:

Fuel Balance: s_i = s_{i-1} - c_i + v_i for all i. This equation reflects the change in fuel volume in the tank after driving to the next gas station and refueling.
Refueling Multiplicity: v_i = 0.25 q_i (s_ub - s_{i-1} + c_i) for all i. Defines the refueling volume as a fraction of the available tank space.
Minimum Fuel Level: s_{i-1} - c_i + z_i >= s_lb for all i. Ensures that there is enough fuel to reach the next gas station, allowing for a penalty z_i for violations.
End-of-Route Fuel: s_{|I|} - c_{|I|+1} >= s_n. Requires a certain fuel volume at the end of the route.
Minimum Refueling: v_i >= v_min * b_i for all i. Ensures that refueling only occurs for a sufficient volume.
Refueling Indicator: q_i <= 4 * b_i for all i. Links the refueling percentage to a binary indicator, showing whether refueling occurred.

In this formulation, a "soft" constraint is used for the minimum fuel volume, allowing the model to adapt to real-world conditions where strict adherence to all constraints might be impossible. This enhances the operational reliability of the model. Applying reinforcement learning to such a complex problem with a discrete action space and penalties for violations allows for finding effective strategies that might be difficult to achieve with purely classical methods, especially when scaling to hundreds of gas stations and dynamically changing prices.

Key Takeaways

RL Complements, Not Replaces, Classical Methods: Reinforcement Learning does not aim to completely displace traditional optimization methods but rather integrates with them, improving their efficiency or solving problems where classical approaches face limitations.
Hybrid Strategies are Key: The most promising approaches are hybrid algorithms where RL generates initial solutions, adapts metaheuristic parameters, or decomposes problems, while exact methods refine the details.
NCO Expands Capabilities but Has Limitations: Neural Combinatorial Optimization shows potential in solving complex problems but is currently limited by problem size and specificity, requiring further research for generalization.
Practical Applicability in Logistics: Fuel stop optimization for freight transportation is a prime example of how RL can be applied to reduce operational costs, offering more flexible and economically advantageous strategies compared to manual management.
Discretization for RL: Converting continuous variables into discrete ones (e.g., refueling volumes) is an effective method for adapting real-world business problems for reinforcement learning algorithms, simplifying the management of agent states and actions.

— Editorial Team