Linear Programming in Petroleum Refining

       Linear programming is the foundation of modern refinery optimization and is widely used for rrefinery optimization, crude oil selection, product blending, refinery scheduling, and supply chain optimization. This article is intended for engineers, refinery professionals, and process specialists who work with optimization problems but are not specialists in mathematical optimization. Rather than focusing on mathematical theory, it explains the principles of linear programming from an engineering perspective. Mathematical concepts are intentionally simplified and illustrated with practical examples from the refining industry to show how optimization is applied in real industrial systems. Linear programming is one of the core technologies used for refinery process optimization.

       Optimization begins with a simple question: what does "best" mean? In engineering, there is no universal definition of the best solution. Instead, every optimization problem is evaluated using a specific criterion that reflects its objective.
       Depending on the application, the goal may be to:

• maximizing refinery gross margin;
• maximizing gasoline, diesel, or jet fuel production;
• selecting the most profitable crude oil slate;
• minimizing crude processing costs;
• minimizing hydrogen, steam, fuel gas, and utility consumption;
• maximizing utilization of FCC, hydrocracker, reformer, and distillation units;
• minimizing giveaway of product quality properties;
• minimizing blending cost while satisfying product specifications;
• optimizing refinery logistics and tank farm operations.

       In petroleum refining, optimization is applied at every planning level, from long-term crude selection and refinery optimization to daily refinery scheduling, gasoline blending, diesel blending, tank farm management, and refinery logistics. In mathematics, the best solution is therefore defined as the one that produces the maximum or minimum value of the selected criterion. This criterion is represented by the function called objective function. Optimization is the process of finding the best feasible solution to a problem. Mathematically, it is defined as the search for the maximum or minimum value of an objective function while satisfying a set of constraints. Many engineering problems can be formulated as optimization tasks. Regardless of the application, the objective is always to determine the values of the decision variables that produce the best possible result.
       In practice, optimization is always performed under constraints. Equipment capacities, material availability, product quality specifications, safety requirements, and operating rules all restrict the set of feasible solutions. Any solution that violates one or more constraints is considered infeasible, even if it provides a better objective value.
       Optimization is therefore not simply the search for the largest or smallest number. It is the process of finding the best solution among all feasible alternatives. This mathematical framework forms the foundation of modern optimization methods, including Linear Programming (LP), Integer Linear Programming (ILP), and Mixed-Integer Linear Programming (MILP), which are widely used in refinery planning, product blending, production scheduling, and supply chain optimization. Linear programming is one of the most widely used linear optimization methods in engineering and industrial planning. LP is widely applied to blend optimization for gasoline, diesel, and jet fuel production.

       Every optimization problem consists of four fundamental components: decision variables, input parameters, an objective function, and constraints. Together, they define the mathematical optimization model that an optimization algorithm solves. The resulting refinery optimization model is then solved using an LP solver.

       Decision variables are the quantities whose values can be changed by the optimization algorithm. They represent the decisions that must be made to achieve the best objective value. In a refinery, decision variables may include crude oil processing rates, crude allocation between CDU trains, vacuum residue routing, FCC feed rates, hydrocracker feed allocation, reformer operating severity, gasoline blending component flow rates, diesel blending component flow rates, hydrogen allocation, fuel gas distribution, intermediate stream routing, production rates, blending ratios, tank-to-tank transfers, storage allocation, pumping schedules, pipeline shipment rates, loading terminal schedules, product distribution volumes, refinery export flows, and utility allocation.

       Input parameters are values that are known before optimization begins and cannot be changed by the optimizer. They describe the operating conditions and available resources. Typical input parameters include crude assay data, API gravity, sulfur content, true boiling point (TBP) curves, density, viscosity, octane numbers, cetane index, Reid Vapor Pressure (RVP), flash point, distillation curves, product quality specifications, crude oil availability, market prices, customer demand, available inventories, refinery unit capacities, pipeline capacities, tank capacities, hydrogen production limits, utility availability, energy costs, and environmental regulations.

       The objective function defines the optimization goal by assigning a numerical value to every feasible solution. Typical objective functions include maximizing refinery gross margin, maximizing refinery profitability, maximizing gasoline production, maximizing diesel production, maximizing jet fuel production, maximizing product yield, maximizing throughput, maximizing equipment utilization, minimizing crude processing costs, minimizing blending costs, minimizing hydrogen consumption, minimizing utility consumption, minimizing energy costs, minimizing transportation costs, minimizing emissions, and minimizing product giveaway while satisfying quality specifications. The optimizer searches for the combination of decision variables that produces the best value of the objective function.

       Constraints define the limits within which the optimization must operate. They ensure that every solution is technically feasible and satisfies all physical, operational, and economic requirements. Typical constraints include material balances, crude unit capacities, vacuum distillation capacities, FCC capacities, hydrocracker capacities, reformer capacities, coker capacities, blending quality specifications, octane number requirements, cetane index requirements, Reid Vapor Pressure (RVP) limits, sulfur specifications, density limits, flash point requirements, distillation curve specifications, hydrogen balance, fuel gas balance, steam availability, utility capacities, storage tank capacities, pipeline capacities, product demand, crude availability, environmental regulations, operational limits, and shipment requirements. Together, these four components define a complete optimization model. Linear programming is often the first optimization method engineers encounter. Understanding its principles makes it easier to work with advanced optimization techniques such as MILP, nonlinear optimization, and refinery blending models.

       The previous sections introduced the concepts informally. They can now be expressed mathematically. An optimization problem can be expressed mathematically as the search for the values of the decision variables that optimize an objective function while satisfying a set of constraints.
       The general form of an optimization problem is:

where:
       x - is the vector of decision variables;
       f(x) is the objective function;
       gi(x) are inequality constraints;
       hj(x) are equality constraints.
       In refinery applications, each variable usually represents a material flow, production rate, or blend component. Every constraint corresponds to a physical limitation such as equipment capacity, product specification, or material balance. Typical refinery LP models include thousands of material balance equations connecting process units, storage tanks, blending systems, and logistics infrastructure into one optimization model. The optimizer searches for the values of x that produce the best objective value while satisfying all constraints. The set of all feasible solutions is called the feasible region, and the optimal solution always lies within this region. The mathematical form of the objective function and constraints determines the optimization method. When they are linear, the problem is solved using Linear Programming (LP). If some decision variables must be integers, the problem becomes Integer Linear Programming (ILP) or Mixed-Integer Linear Programming (MILP). When nonlinear relationships are present, nonlinear optimization methods are required. Linear Programming is the most widely used optimization method in engineering because many industrial problems can be approximated by linear relationships.

       Linear Programming (LP) is a mathematical optimization technique used to find the best solution to a problem whose objective function and constraints are both linear. In a linear programming model, every relationship is represented by a linear equation or inequality. The optimizer adjusts the decision variables to maximize or minimize the objective function while satisfying all constraints. The general form of a linear programming problem is

where:
       x — vector of decision variables;
       c — objective function coefficients;
       A — constraint coefficient matrix;
       b — constraint limits.
       Refinery LP models often contain several thousand decision variables and constraints. A single optimization model may simultaneously represent crude distillation units, conversion units, blending systems, storage tanks, pipelines, utilities, and product distribution networks.
       Because both the objective function and constraints are linear, the feasible region forms a convex polyhedron. This property allows efficient algorithms, such as the Simplex Method and Interior-Point Methods, to reliably find the global optimum, even for large industrial optimization problems. Linear programming is widely used in refinery optimization, product blending, production scheduling, logistics, transportation, and supply chain optimization, where many engineering relationships can be approximated as linear models.

Example
       Each line on the graph represents a constraint. Together, the constraints form the shaded feasible region—the set of all solutions that satisfy every constraint. Any point inside the shaded region is a feasible solution. Any point outside violates at least one constraint and is therefore infeasible. The objective of linear programming is to find the best feasible solution, not just any feasible one. In this example, the red point is the optimal solution because it satisfies all constraints and provides the highest value of the objective function. A fundamental property of linear programming is that, if an optimal solution exists, at least one optimal solution is always located at a vertex (corner point) of the feasible region. This property makes LP computationally efficient and forms the basis of the Simplex Method.

       The constraints of a linear programming problem define the feasible region—the set of all solutions that satisfy every constraint simultaneously. Any point within this region is called a feasible solution. The objective of linear programming is to identify the feasible solution that optimizes the objective function. While many feasible solutions may exist, only one or more provide the optimal objective value. A fundamental property of linear programming is that the feasible region is always convex. Consequently, if an optimal solution exists, at least one optimal solution is located at a vertex (corner point) of the feasible region.
This property is one of the main reasons why linear programming is computationally efficient. Rather than evaluating every feasible solution, optimization algorithms search only the vertices of the feasible region to identify the optimum.

       Linear programming is based on several mathematical assumptions that make the optimization problem solvable using linear methods.
       1. Linearity. The objective function and all constraints must be linear. This means that the contribution of each decision variable is directly proportional to its value, and the combined effect of multiple variables is equal to the sum of their individual contributions.
       2. Divisibility. Decision variables are assumed to be continuous and may take any fractional value within their allowable range. If variables must be restricted to integers or binary values, the problem becomes an Integer Linear Programming (ILP) or Mixed-Integer Linear Programming (MILP) problem.
       3. Certainty. All model parameters are assumed to be known and constant during optimization. Coefficients in the objective function, constraint limits, and input data are treated as deterministic values.
       4. Non-Negativity. Decision variables are typically restricted to non-negative values:

       Negative production rates, material flows, or inventories are generally not physically meaningful, so this assumption is satisfied in most engineering applications. Together, these assumptions define the mathematical framework of linear programming and distinguish it from more general optimization methods that can handle nonlinear relationships, uncertainty, or discrete decision variables.

       Solving a linear programming problem follows a well-defined sequence of steps:
       1 Import crude assay data.
       2 Read refinery operating data.
       3 Build material balances.
       4 Add quality specifications.
       5 Add refinery operating constraints.
       6 Solve the LP model.
       7 Generate refinery operating plan.
       The LP solver systematically searches the feasible region and identifies the solution that provides the optimal value of the objective function while satisfying every constraint. In refinery optimization, this process may determine optimal blending ratios, production rates, feed allocation, transportation flows, or operating schedules, depending on how the optimization model is formulated.

       The Simplex Method is the classical algorithm for solving linear programming problems. Instead of searching every feasible solution, the Simplex Method exploits the fact that an optimal solution to a linear programming problem is located at a vertex of the feasible region.The algorithm starts from an initial feasible vertex and moves to a neighboring vertex only if it improves the objective function. Each iteration produces a solution that is at least as good as the previous one while satisfying all constraints.
The search continues until no neighboring vertex offers further improvement. At this point, the algorithm has reached the global optimum. In practice, the Simplex Method typically evaluates only a small fraction of all possible vertices, making it highly efficient even for large optimization models. Although modern LP solvers also incorporate advanced techniques such as interior-point methods, the Simplex Method remains one of the most widely used algorithms due to its speed, reliability, and ability to provide detailed information about the optimal solution and the influence of individual constraints. For a refinery LP model containing several thousand variables, the Simplex Method evaluates only a tiny fraction of all feasible corner points before reaching the optimum.

       A linear programming solver is a software library that automatically finds the optimal solution to a linear programming problem. The user defines the objective function, decision variables, and constraints, while the solver selects an appropriate algorithm and performs the optimization.
       Modern LP solvers implement multiple optimization algorithms, including the Simplex Method, Dual Simplex, and Interior-Point Methods. The choice of algorithm depends on the structure and size of the optimization model, allowing the solver to achieve high performance across a wide range of industrial applications. In addition to the optimal values of the decision variables, LP solvers often provide valuable analytical information, such as objective function value, constraint utilization, shadow prices, reduced costs, and sensitivity analysis. These results help engineers understand not only the optimal solution but also the factors that limit system performance.

       Commercial refinery optimization systems frequently use high-performance LP solvers such as Gurobi, IBM CPLEX, and HiGHS to solve large-scale optimization models containing thousands of variables and constraints. Today, LP solvers are widely used in refinery planning, product blending, production scheduling, logistics, energy systems, manufacturing, transportation, and supply chain optimization. In the Petroleum Refining Library, linear programming models are solved using the open-source lp_solve optimization engine.

       Linear programming is widely used to optimize systems where limited resources must be allocated efficiently while satisfying operational, economic, and technical constraints.
       Common industrial applications include:

• Production planning — determining optimal production rates and operating modes.
• Product blending — selecting blend compositions that satisfy quality specifications at minimum cost or maximum profit.
• Resource allocation — distributing raw materials, equipment capacity, labor, or utilities among competing activities.
• Transportation and logistics — minimizing transportation costs while meeting supply and demand requirements.
• Supply chain optimization — coordinating production, storage, and distribution across multiple facilities.
• Production scheduling — allocating equipment and processing time to maximize throughput and resource utilization.
• Energy optimization — optimizing fuel allocation, power generation, and energy consumption.

       In the refining industry, linear programming is extensively used for refinery optimization, crude selection and crude blending, feedstock allocation, product blending, and production optimization. These problems typically involve hundreds or thousands of decision variables and constraints, making LP an essential tool for supporting operational and strategic decision-making. Although the engineering context varies across industries, every LP application follows the same mathematical framework: define the decision variables, formulate an objective function, specify the constraints, and use an optimization solver to identify the best feasible solution.

       Petroleum refining is one of the largest industrial users of linear programming. A medium-size refinery may process hundreds of material streams while producing dozens of marketable products. Every stream can potentially be routed through multiple processing units or blended into different products. Because every decision influences many downstream units simultaneously, manual optimization quickly becomes impossible. Linear programming enables engineers to evaluate thousands of feasible operating plans within seconds and identify the one that maximizes refinery profitability while satisfying all operating constraints. For this reason, LP has been the industry standard for refinery optimization for more than five decades.
       Most refinery processes are inherently nonlinear. However, for planning purposes, many process units are represented by linear yield vectors generated from rigorous process simulators. Product qualities are also approximated using linear blending equations where appropriate. This allows the entire refinery to be represented as a large linear optimization model that is sufficiently accurate for planning while remaining computationally efficient.

       Linear programming is effective only when the optimization problem satisfies the assumptions of linearity, continuity, and certainty. Many real-world engineering problems violate one or more of these assumptions. Some decisions are discrete, such as starting or stopping a process unit, selecting a transportation route, or assigning a storage tank. These problems require integer or binary decision variables and are formulated as Integer Linear Programming (ILP) or Mixed-Integer Linear Programming (MILP) models. Other processes are inherently nonlinear. Reaction kinetics, thermodynamic properties, heat transfer, and hydraulic behavior often cannot be represented accurately by linear equations, requiring Nonlinear Programming (NLP) methods.
In practice, engineers frequently balance model accuracy and computational efficiency by combining linear approximations with more advanced optimization techniques when necessary. Modern refinery optimization platforms often combine LP, MILP, NLP, and discrete-event simulation to achieve both computational efficiency and engineering accuracy.
       Some refinery phenomena cannot be represented accurately by linear equations, including: nonlinear blending properties; reaction kinetics; catalyst deactivation; vapor-liquid equilibrium; pressure drop calculations; heat exchanger networks; hydraulic limitations; compressor performance; furnace efficiency. These problems often require NLP, MILP, or hybrid optimization methods.

       Linear programming is one of the fundamental methods of mathematical optimization. By combining decision variables, an objective function, and linear constraints, it enables efficient optimization of complex engineering and industrial systems. Its simplicity, computational efficiency, and wide range of applications have made LP the foundation of modern planning, scheduling, logistics, and product blending. While more advanced methods such as ILP, MILP, and NLP extend its capabilities, linear programming remains the starting point for understanding optimization and its practical applications. Today, linear programming remains the core optimization technology used in almost every modern refinery. It supports long-term planning, daily production optimization, crude selection and crude blending, product blending, logistics, and supply chain decision-making. Most commercial refinery planning, refinery scheduling, and refinery optimization systems are ultimately based on large-scale LP or MILP optimization models.

1. What is linear programming?
Linear programming (LP) is a mathematical optimization method used to maximize or minimize an objective function subject to a set of linear constraints.

2. What is the difference between optimization and linear programming?
Optimization is the general process of finding the best feasible solution. Linear programming is a specific optimization technique in which both the objective function and all constraints are linear.

3. What are decision variables?
Decision variables are the unknown values that the optimizer adjusts to achieve the best objective while satisfying all constraints.

4. What is an objective function?
The objective function defines the optimization goal, such as maximizing profit, throughput, or product yield, or minimizing cost, energy consumption, or emissions.

5. What are constraints in linear programming?
Constraints are mathematical equations or inequalities that define the limits within which the solution must remain, such as equipment capacities, product specifications, or material balances.

6. Where is linear programming used?
Linear programming is widely used in refinery planning, product blending, production scheduling, logistics, transportation, energy systems, manufacturing, and supply chain optimization.

7. What is the Simplex Method?
The Simplex Method is the classical algorithm for solving linear programming problems. It searches the vertices of the feasible region until it identifies the global optimum.

8. What is an LP solver?
An LP solver is software that automatically solves linear programming models using algorithms such as the Simplex Method, Dual Simplex, or Interior-Point Methods.

9. What is the difference between LP and MILP?
LP allows continuous decision variables only, whereas Mixed-Integer Linear Programming (MILP) also includes integer and binary variables, enabling the modeling of discrete engineering decisions.

10. What are the limitations of linear programming?
Linear programming assumes linear relationships, continuous decision variables, and deterministic input data. Problems involving discrete decisions or nonlinear behavior require more advanced optimization methods such as MILP or NLP.

11. How is linear programming used in refinery planning?
Linear programming is used in refinery planning to determine the optimal operating strategy by allocating crude oil, intermediate streams, and refinery capacities while satisfying product specifications, market demand, and operational constraints. It helps maximize refinery profitability and improve resource utilization.

12. How does LP optimize gasoline blending?
LP optimizes gasoline blending by determining the optimal proportions of blend components that satisfy quality specifications such as octane number, Reid Vapor Pressure (RVP), density, and sulfur content while minimizing blending cost or maximizing profit.

13. What is a refinery LP model?
A refinery LP model is a mathematical representation of a refinery that includes decision variables, objective functions, material balances, unit capacities, quality constraints, and economic parameters. It is used to identify the optimal operating plan for refinery production and logistics.

14. Why do refineries use LP instead of manual planning?
Modern refineries contain hundreds of process units, material streams, and operational constraints. Linear programming evaluates thousands of feasible operating plans within seconds, allowing engineers to identify the most profitable solution more accurately and efficiently than manual calculations.

15. What data are required for refinery optimization?
Typical refinery optimization requires crude assay data, product quality specifications, refinery unit capacities, market prices, customer demand, available inventories, utility costs, operating constraints, and environmental requirements.

16. Can LP optimize crude oil selection?
Yes. Linear programming is widely used to optimize crude oil selection by identifying the combination of crude oils that maximizes refinery profitability while satisfying processing capacities, product quality specifications, and operational constraints.

17. How many variables does a refinery LP model contain?
The size of a refinery LP model depends on refinery complexity. Small models may contain several hundred decision variables, while large commercial refinery planning models often include tens of thousands of variables and constraints representing process units, material streams, blending operations, storage facilities, and logistics networks.

18. What industries use linear programming besides petroleum refining?
Linear programming is widely used in manufacturing, chemical processing, power generation, mining, transportation, logistics, supply chain management, agriculture, telecommunications, finance, healthcare, and production planning. In all of these industries, LP helps allocate limited resources efficiently while minimizing costs or maximizing profit.

19. Can linear programming be used for supply chain optimization?
Yes. Linear programming is widely used for supply chain optimization, including production planning, inventory management, transportation planning, warehouse allocation, distribution network design, and demand fulfillment. It helps minimize total supply chain costs while satisfying capacity, delivery, and customer demand constraints.

20. Which LP solver is used in the Petroleum Refining Library?
The Petroleum Refining Library uses the open-source lp_solve optimization engine to solve linear programming models. The solver automatically computes the optimal values of decision variables while satisfying all model constraints and is integrated into the library for refinery planning, product blending, production scheduling, and other optimization tasks.