with linear optimization problems at work and for some personal projects, I have always been intrigued by seeing the log messages during solver iterations. It’s fascinating how modern solvers can solve optimization problems with decision variables and constraints in the order of thousands and millions within the time frame of only minutes or hours. It could take days or years if a human were solving such processes manually. Nevertheless, I wanted to better understand the terminologies used in linear programming and the ones I see in the solver log messages.
In my 2021 post, which I published with Towards Data Science (time flies!), I discussed techniques to solve linear problems in Python and Julia, respectively. In another post, I discussed the steps undertaken by solvers for optimizing, solving, and post-processing linear problems which are packaged in the form of a mathematical programming system. This post is going to be a more theoretical one. I am going to break down different optimization terminologies such as primal, dual, dualness, duality gap, basic solution, and put forward the three optimality conditions that need to be satisfied for linear problems. Let’s get started.
Duality of optimization problem
Every optimization problem could be viewed from two different perspectives. This concept is referred to as dualness of the optimization problem. For example, if our original objective is to maximize the revenue of a company within the given resource constraints, the same problem could also be formulated in a way to minimize the resource constraints while aiming to sell a certain number of products. The original form of the linear optimization problem that is provided is referred to as the primal problem. For every primal problem, there is a corresponding dual problem. If the primal is a maximization problem, then the dual is a minimization problem, and vice versa. As such, the dual of a dual problem is a primal problem itself. This fundamental dualness in the characterization of optimization problems is referred to as duality.
As stated above, the sense of the objective functions is just opposite in primal and dual problems. Besides, the decision variables used in primal problems are formulated as constraints in dual problems, and the constraints in the primal problem are formulated as decision variables. This duality has a multitude of advantages in solving linear optimization problems. When a solver solves an optimization problem, both the primal and dual feasibility conditions need to be met. If the primal problem has many variables but fewer constraints, in that case, the dual problem might be easier to solve. Furthermore, duality provides deeper insights into the structure of the optimization problem.
Let’s assume we have a primal problem in the following form:
Where A, b, and c all belong to real numbers. Say we have m number of constraints, and n number of decision variables. A is the constraint coefficient matrix with the order m*n, x is the decision variable vector with n variables, b is the RHS vector with m elements, and c is the cost vector comprising cost coefficients of each decision variable.
The corresponding dual problem is given in the form:
We can see that the transpose of b, which is the resource limit defined in the primal problem, comes in the objective function of the dual problem. y is the decision variable in the dual problem and is hence referred to as dual variables. Dual variables show the sensitivity of the primal objective function with respect to every constraint in the optimal point. In economic interpretation, dual values are also referred to as shadow prices or fair prices.
Steps for conversion of primal problem to dual problem
The steps for converting a primal problem into a dual problem can be summarized below. This is inspired by this video.
- First, convert the problem to canonical form. If the problem is maximization, the constraints should be in the form of less than or equal to. And if the problem is minimization, then the constraint should be in the form of greater than or equal to
- Change the sense of the objective function. Maximization problem becomes minimization, and vice versa.
- The number of variables in the primal problem will be the number of constraints in the dual problem, and vice versa.
- Cost constraints in the objective function in the primal problem will be RHS constant of the constraints in the dual problem, and vice versa.
- For formulating the constraints in the dual problem, use the transpose of the constrain matrix in the primal problem.
Example of primal to dual conversion
Primal problem
Assume we want to maximize the revenue of a furniture company. x and y are the number of sales of chairs and tables at a particular period, and their unit sales price is 90 and 75, respectively.
Say we have resource constraints in terms of energy, number of labor and working hours. Each chair needs 3 units and each table needs 2 units of energy, and overall, they cannot consume more than 66 units of energy. Each chair needs 9 units and each table needs 4 units of manpower and overall, it should be less than or equal to 180 units of manpower. Each chair needs 2 units and each table needs 10 units of working hours and overall it should be less than or equal to 200 units of working hours. This problem is written in canonical form as follows:
maximize z = 90x + 75y
s.t. 3x+2y ≤ 66 (energy)
9x+4y ≤ 180 (manpower)
2x+10y ≤ 200 (time)
x, y ≥ 0
(chairs, tables)
Dual problem
In the above-mentioned problem, I have two decision variables, and three constraints in the primal problem. Accordingly, the dual problem will have three variables and two constraints. Let w1, w2 and w3 be the three variables in the dual problem based on each constraint in the primal problem. In this case, w1, w2, and w3 can be considered as the shadow prices associated with energy, manpower, and time constraints, respectively. Shadow prices refer to the amount by which the solution to the primal objective function would change at the optimal point, if the primal RHS constraint is changed by one unit.
We get:
min 66w1+180w2+200w3
s.t. 3w1+9w2+2w3 ≥ 90 (chairs)
2w1+4w2+10w3 ≥ 75 (tables)
w1, w2, w3 ≥ 0
(energy, manpower, time)
Converting the problem to standard form
To convert the primal and dual problem to standard form means to convert the inequality constraints to equations by adding some variables. This is useful for determining the optimality conditions, which is discussed further in the succeeding section.
In the primal problem, I add slack variables to convert the less than inequality constraint to an equality constraint as shown below. h1, h2, and h3 are slack variables for energy, manpower and time constraints, respectively.
maximize z = 90x+75y
s.t. 3x+2y+h1 = 66 (energy)
9x+4y+h2 = 180 (manpower)
2x+10y+h3 = 200 (time)
x, y, h1, h2, h3 ≥ 0
In the dual problem, I use surplus variables to convert greater than inequality constraint into an equality constraints. s1 and s2 are surplus variables.
min 66w1+180w2+200w3
s.t. 3w1+9w2+2w3-s1 = 90 (chairs)
2w1+4w2+10w3-s2 = 75 (tables)
w1, w2, w3, s1, s2 ≥ 0
As we have used equality constraints in the standard form, the constraints are always binding, meaning we are using all the resources that are available without leaving any waste. In this condition, in the primal optimal solution, the values of slack variables become equal to zero. And in the dual optimal solution, the values of surplus variables also become equal to zero. If the constraint is non-binding (e.g., it has less than or equal to constraint), then the value of these variables could be either greater than or equal to zero in the optimal solution.
Optimality conditions for linear problems
For a linear optimization problem, the solution to primal problem and a solution to dual problem are optimal if and only if the following three conditions are met. (This is inspired by this video lecture by Gurobi Optimization.)
- Primal feasibility
The solution needs to be primal feasible. This implies that the value of the decision variables in the solution to the primal problem should satisfy all its constraints. In our case, the number of chairs and tables (x and y) should be within the resource constraints for energy, manpower, and time, respectively.
3x+2y ≤ 66 (energy)
9x+4y ≤ 180 (manpower)
2x+10y ≤ 200 (time)
x, y ≥ 0
b. Dual feasibility
This implies that the solution to the dual problem should satisfy all of its constraints. In our case, the shadow prices associated with energy, manpower, and time (w1, w2, and w3) should satisfy the price constraints (cost coefficients) for the chairs and the tables, respectively.
3w1+9w2+2w3-s1 = 90 (chairs)
2w1+4w2+10w3-s2 = 75 (tables)
w1, w2, w3, s1, s2 ≥ 0
c. Complementary (or orthogonal conditions)
Say x* refers to the decision variables in the optimal primal solution and h* refers to the slack variables in the same primal problem. Say s refers to the slack variables in the dual problem, and w refers to the associated shadow prices in the dual problem. At optimality, the product of decision variables in the primal problem and the surplus variables associated with dual problem should be zero. This is referred to as being cost efficient because this condition ensures that we are making the most efficient use of our resources.
x*s = 0
In our problem, x * s1 = 0 and y * s2 = 0 implies:
x*(3w1+9w2+2w3-90) = 0
y*(2w1+4w2+10w3-75) = 0
Also, at optimality, the product of slack variables in the primal problem and the shadow prices in the dual problem should be equal to zero. This implies that we are being resource efficient and leaving no waste of resources.
h*w = 0
h1*w1 = 0; h2*w2 = 0; h3*w3 = 0;
Basic Solution, Duality gap, Strong duality and weak duality
Basic Solution
As per this nice definition from HiGHS documentation, if a linear problem is feasible and has bounded feasible region in the direction of optimization, then it has an optimal solution at a vertex. “At this vertex, the decision variables can be partitioned into as many basic variables as there are constraints, and the non-basic variables. In the given solution, basic variables are the ones having non-zero values, and non-basic variables are the ones having zero values. This set of solutions is referred to as basic solution, and the partition is referred to as basis.
(If a linear problem is solved using simplex algorithm, the set of basic and non-basic solutions can change over time. During iterations, some slack variables will become non-basic, and other variables will become basic. The simplex moves from one basis to another improving the objective function, until it reaches the optimal point and cannot improve the objective function further.)
Duality gap
The difference between the optimal primal value p* and the optimal dual value d* is referred to as the duality gap p*–d*. This value is always greater than or equal to zero.
Strong duality
Strong duality holds if the primal objective value (solution) and the dual objective value is the same, implying that the duality gap is zero. Strong duality implies that the problem is “often” convex and satisfies certain constraint conditions. The dual problem in this case is a tight approximation of the primal problem.
For example, if the maximum revenue in a furniture factory composed of sales of chairs and tables is equal to the minimum cost of resource use, including energy, labour, and hours, this condition is referred to as strong duality.
Weak duality
If the duality gap is greater than or equal to zero, then the condition is referred to as weak duality. This implies that the dual solution is less than or equal to the primal solution.
In case of weak duality, the dual solution rather provides bounds on the primal objective value. If the primal is a minimization problem, then the dual feasible solution gives the lower bound on the primal objective value. And if the primal is a maximization problem, then the dual feasible solution gives the upper bound on the primal objective value.
Conclusion
This is my first article in Towards Data Science where I describe some mathematical optimization concepts without using any code. In this post, I explain with examples the duality concepts in mathematical optimization, including primal to dual form conversion, canonical and standard forms of the problems, the conditions for optimality, basic solution, duality gap, strong and weak duality. When I started to learn about these concepts, they were quite abstract to me. Therefore, I tried to learn about these concepts on my own, as well as package them together since all these concepts are interrelated. I hope you find them useful. You can refer to some notebooks of my previous optimization-related blogs in this GitHub repository. Thank you for reading!
