Hello,
I would like to know that how I can obtain the dual value of a constraint when a meta-heuristic algorithm (such as PSO) is used, instead of a mathematical OR software (like GAMS), as the optimization tool.
Regards,
Morteza
http://mortezash.blogfa.com/
The quick answer is that there typically are NO Lagrange multipliers corresponding to a primal optimal solution - especially for problems where meta-heuristics typically are used. Indeed there normally is an optimum to a Lagrangian dual reformulation, but the optimal dual solution normally cannot be "translated" into a primal optimal solution, because of the non-convexity of the primal problem (that is, the optimal values of the primal and the dual problems are NOT equal). I have a paper together with a colleague on some of this theory - see the link
http://dx.doi.org/10.1287/opre.1060.0292
Dear Michael,
Assume that the primal optimization problem is a convex LP problem. Is it possible to calculate the dual variables (i.e., Lagrangian multipliers) using PSO without manually transforming the primal problem to the dual problem?
I hope my question is clear enough.
Regards,
Morteza
Dear Erling,
Actually, to handle some constraints I need to know the dual values of some constraints and due to its complexity, a meta-heuristic algorithm is inevitably needed.
In this line, I would like to know your idea.
Are you looking at a linear program or something else? This is a bit confusing, as you seem to talk about complicated constraints; in linear optimization there are no complicated constraints - they are all linear! :-) Hence a meta-heuristic has no place in the field.
Dear Michael,
The problem is actually a large-scale MILP and I want to solve it using Benders Decomposition. With this aim, the dual values must be calculated by the optimization algorithm and in this case, PSO is my OR tool.
I think there is no need to calculate dual value of a constraint while using metaheuristics.
Dear Mahamad,
That’s not the way I see it.
It depends on the form of your problem. To solve some optimization problems, you need to know the dual values of constraints and thus, the method of obtaining the dual variables will be inevitably required, regardless of your OR tools (meta-heuristic or mathematical-based algorithms).
In Benders decomposition you solve an LP problem every time you fix the binary/integer variables, and from that optimal solution it is easy - even automatic - to provide the LP dual solution (hence the Lagrange multipliers for the LP sub-problem). The master problem which is constructed through the generation of a so-called "cut" can be solved exactly, or more practically for you, perhaps - only approximately, in order to receive a new suggestion on an integer solution.
Hello,
Conceptually, the dual value (i.e., the marginal value or shadow price) of a constraint is the sensitivity of the objective function to the constant value (RHS) of that constraint. In other words, the dual value can be obtained as:
Dual value = Delta_obj / Delta_RHSconstant
Regards,
Dehbashian
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs