with linear optimization issues at work and for some private tasks, I’ve all the time been intrigued by seeing the log messages throughout solver iterations. It’s fascinating how trendy solvers can remedy optimization issues with determination variables and constraints within the order of hundreds and hundreds of thousands inside the timeframe of solely minutes or hours. It may take days or years if a human have been fixing such processes manually. Nonetheless, I wished to raised perceive the terminologies utilized in linear programming and those I see within the solver log messages.
In my 2021 post, which I printed with In direction of Information Science (time flies!), I mentioned strategies to resolve linear issues in Python and Julia, respectively. In one other publish, I mentioned the steps undertaken by solvers for optimizing, fixing, and post-processing linear issues that are packaged within the type of a mathematical programming system. This publish goes to be a extra theoretical one. I’m going to interrupt down completely different optimization terminologies akin to primal, twin, dualness, duality hole, fundamental resolution, and put ahead the three optimality circumstances that must be glad for linear issues. Let’s get began.
Duality of optimization downside
Each optimization downside might be seen from two completely different views. This idea is known as dualness of the optimization downside. For instance, if our authentic goal is to maximise the income of an organization inside the given useful resource constraints, the identical downside may be formulated in a approach to reduce the useful resource constraints whereas aiming to promote a sure variety of merchandise. The unique type of the linear optimization downside that’s offered is known as the primal downside. For each primal downside, there’s a corresponding twin downside. If the primal is a maximization downside, then the twin is a minimization downside, and vice versa. As such, the twin of a twin downside is a primal downside itself. This elementary dualness within the characterization of optimization issues is known as duality.
As said above, the sense of the target features is simply reverse in primal and twin issues. Moreover, the choice variables utilized in primal issues are formulated as constraints in twin issues, and the constraints within the primal downside are formulated as determination variables. This duality has a mess of benefits in fixing linear optimization issues. When a solver solves an optimization downside, each the primal and twin feasibility circumstances must be met. If the primal downside has many variables however fewer constraints, in that case, the twin downside is likely to be simpler to resolve. Moreover, duality offers deeper insights into the construction of the optimization downside.
Let’s assume now we have a primal downside within the following kind:
The place A, b, and c all belong to actual numbers. Say now we have m variety of constraints, and n variety of determination variables. A is the constraint coefficient matrix with the order m*n, x is the choice variable vector with n variables, b is the RHS vector with m parts, and c is the associated fee vector comprising value coefficients of every determination variable.
The corresponding twin downside is given within the kind:
We will see that the transpose of b, which is the useful resource restrict outlined within the primal downside, comes within the goal operate of the twin downside. y is the choice variable within the twin downside and is therefore known as twin variables. Twin variables present the sensitivity of the primal goal operate with respect to each constraint within the optimum level. In financial interpretation, twin values are additionally known as shadow costs or truthful costs.
Steps for conversion of primal downside to twin downside
The steps for changing a primal downside right into a twin downside could be summarized under. That is impressed by this video.
- First, convert the issue to canonical kind. If the issue is maximization, the constraints needs to be within the type of lower than or equal to. And if the issue is minimization, then the constraint needs to be within the type of larger than or equal to
- Change the sense of the target operate. Maximization downside turns into minimization, and vice versa.
- The variety of variables within the primal downside would be the variety of constraints within the twin downside, and vice versa.
- Value constraints within the goal operate within the primal downside might be RHS fixed of the constraints within the twin downside, and vice versa.
- For formulating the constraints within the twin downside, use the transpose of the constrain matrix within the primal downside.
Instance of primal to twin conversion
Primal downside
Assume we wish to maximize the income of a furnishings firm. x and y are the variety of gross sales of chairs and tables at a specific interval, and their unit gross sales worth is 90 and 75, respectively.
Say now we have useful resource constraints when it comes to power, variety of labor and dealing hours. Every chair wants 3 models and every desk wants 2 models of power, and total, they can not eat greater than 66 models of power. Every chair wants 9 models and every desk wants 4 models of manpower and total, it needs to be lower than or equal to 180 models of manpower. Every chair wants 2 models and every desk wants 10 models of working hours and total it needs to be lower than or equal to 200 models of working hours. This downside is written in canonical kind as follows:
maximize z = 90x + 75y
s.t. 3x+2y ≤ 66 (power)
9x+4y ≤ 180 (manpower)
2x+10y ≤ 200 (time)
x, y ≥ 0
(chairs, tables)
Twin downside
Within the above-mentioned downside, I’ve two determination variables, and three constraints within the primal downside. Accordingly, the twin downside can have three variables and two constraints. Let w1, w2 and w3 be the three variables within the twin downside primarily based on every constraint within the primal downside. On this case, w1, w2, and w3 could be thought of because the shadow costs related to power, manpower, and time constraints, respectively. Shadow costs discuss with the quantity by which the answer to the primal goal operate would change on the optimum level, if the primal RHS constraint is modified 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
(power, manpower, time)
Changing the issue to straightforward kind
To transform the primal and twin downside to normal kind means to transform the inequality constraints to equations by including some variables. That is helpful for figuring out the optimality circumstances, which is mentioned additional within the succeeding part.
Within the primal downside, I add slack variables to transform the lower than inequality constraint to an equality constraint as proven under. h1, h2, and h3 are slack variables for power, manpower and time constraints, respectively.
maximize z = 90x+75y
s.t. 3x+2y+h1 = 66 (power)
9x+4y+h2 = 180 (manpower)
2x+10y+h3 = 200 (time)
x, y, h1, h2, h3 ≥ 0
Within the twin downside, I exploit surplus variables to transform larger 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 now we have used equality constraints in the usual kind, the constraints are all the time binding, which means we’re utilizing all of the sources which are obtainable with out leaving any waste. On this situation, within the primal optimum resolution, the values of slack variables change into equal to zero. And within the twin optimum resolution, the values of surplus variables additionally change into equal to zero. If the constraint is non-binding (e.g., it has lower than or equal to constraint), then the worth of those variables might be both larger than or equal to zero within the optimum resolution.
Optimality circumstances for linear issues
For a linear optimization downside, the answer to primal downside and an answer to twin downside are optimum if and provided that the next three circumstances are met. (That is impressed by this video lecture by Gurobi Optimization.)
- Primal feasibility
The answer must be primal possible. This means that the worth of the choice variables within the resolution to the primal downside ought to fulfill all its constraints. In our case, the variety of chairs and tables (x and y) needs to be inside the useful resource constraints for power, manpower, and time, respectively.
3x+2y ≤ 66 (power)
9x+4y ≤ 180 (manpower)
2x+10y ≤ 200 (time)
x, y ≥ 0
b. Twin feasibility
This means that the answer to the twin downside ought to fulfill all of its constraints. In our case, the shadow costs related to power, manpower, and time (w1, w2, and w3) ought to fulfill the value constraints (value 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 circumstances)
Say x* refers back to the determination variables within the optimum primal resolution and h* refers back to the slack variables in the identical primal downside. Say s refers back to the slack variables within the twin downside, and w refers back to the related shadow costs within the twin downside. At optimality, the product of determination variables within the primal downside and the excess variables related to twin downside needs to be zero. That is known as being value environment friendly as a result of this situation ensures that we’re making essentially the most environment friendly use of our sources.
x*s = 0
In our downside, x * s1 = 0 and y * s2 = 0 implies:
x*(3w1+9w2+2w3-90) = 0
y*(2w1+4w2+10w3-75) = 0
Additionally, at optimality, the product of slack variables within the primal downside and the shadow costs within the twin downside needs to be equal to zero. This means that we’re being useful resource environment friendly and leaving no waste of sources.
h*w = 0
h1*w1 = 0; h2*w2 = 0; h3*w3 = 0;
Primary Answer, Duality hole, Robust duality and weak duality
Primary Answer
As per this good definition from HiGHS documentation, if a linear downside is possible and has bounded possible area within the path of optimization, then it has an optimum resolution at a vertex. “At this vertex, the choice variables could be partitioned into as many fundamental variables as there are constraints, and the non-basic variables. Within the given resolution, fundamental variables are those having non-zero values, and non-basic variables are those having zero values. This set of options is known as fundamental resolution, and the partition is known as foundation.
(If a linear downside is solved utilizing simplex algorithm, the set of fundamental and non-basic options can change over time. Throughout iterations, some slack variables will change into non-basic, and different variables will change into fundamental. The simplex strikes from one foundation to a different bettering the target operate, till it reaches the optimum level and can’t enhance the target operate additional.)
Duality hole
The distinction between the optimum primal worth p* and the optimum twin worth d* is known as the duality hole p*–d*. This worth is all the time larger than or equal to zero.
Robust duality
Robust duality holds if the primal goal worth (resolution) and the twin goal worth is similar, implying that the duality hole is zero. Robust duality implies that the issue is “typically” convex and satisfies sure constraint circumstances. The twin downside on this case is a decent approximation of the primal downside.
For instance, if the utmost income in a furnishings manufacturing unit composed of gross sales of chairs and tables is the same as the minimal value of useful resource use, together with power, labour, and hours, this situation is known as sturdy duality.
Weak duality
If the duality hole is bigger than or equal to zero, then the situation is known as weak duality. This means that the twin resolution is lower than or equal to the primal resolution.
In case of weak duality, the twin resolution fairly offers bounds on the primal goal worth. If the primal is a minimization downside, then the twin possible resolution offers the decrease sure on the primal goal worth. And if the primal is a maximization downside, then the twin possible resolution offers the higher sure on the primal goal worth.
Conclusion
That is my first article in In direction of Information Science the place I describe some mathematical optimization ideas with out utilizing any code. On this publish, I clarify with examples the duality ideas in mathematical optimization, together with primal to twin kind conversion, canonical and normal types of the issues, the circumstances for optimality, fundamental resolution, duality hole, sturdy and weak duality. After I began to study these ideas, they have been fairly summary to me. Subsequently, I attempted to study these ideas by myself, in addition to bundle them collectively since all these ideas are interrelated. I hope you discover them helpful. You may discuss with some notebooks of my earlier optimization-related blogs on this GitHub repository. Thanks for studying!
