I do not want to dig deep into theory of duality regarding the mixed integer programs, because I know they are far from being convex.
but, I did try to formulate dual of a very simple knapsack problem of low dimension, (MILP)
which in the dual problem, I only needed one dual variable due to the single constraint of the primal ( that be the capacity limit ) .
The dual was formulated without any notion or regard to the binary nature of primal variables.
solving the dual ( an LP), I did exactly get zero duality gap,
but the thing is the dual variable value, which should be seen as the Lagrange multiplier(lambda) of the primal constraint , does not behave like that.
by that I mean, when I increase the capacity by the lambda, the objective function does not increase accordingly.
is there an explanation behind that?
I hope I did make myself clear, sorry if I couldn't put it very technical.
Dear Nicolas,
Thanks a lot for your insightful respond.
about your inquiry, I must add that I did not define the dual variable as a binary variable.
( I am using cvx add-on of MATLAB)
Hence, as I mentioned above, the dual problem is LP.
I actually did try to define the dual variable, as a binary, but it resulted in an infeasible problem.
Let me add the toy problem here: first Primal, then Dual ,
---------------------------P ( P* = 10.5 , X* = 0 1 0 1 0 )
w = [ 5 ,3,4,2,8 ] ; %weights
v = [ 1 ,7,3,3.5,5 ] ; %values
cap =6 ; %capacity
[m ,n]= size(w) ;
cvx_begin
binary variable x(n)
maximize ( sum ( x.*v' ) )
subject to
sum ( x.*w') = v(i)
end
y >= 0
cvx_end
Thanks again Nicolas,
I will reflect more on points you just made.
I highly appreciate your time and attention to my question.
For a MILP the dual of the LP relaxation is a weak dual (i.e. the objective of feasible points of the dual provides a bound for the primal problem, and thus so does the optimal objective value of the dual). There does not hold strong duality (the optimal values are equal) - in general there is a positive duality gap.
But if a MIP possesses the integrality property (all vertices of the constraint polyhedron are integer vectors) there is no duality gap, since a vertex solution of the primal LP solves the MILP). There is a sufficient condition: unimodularity of the matrix.
This is not the case for your problem, so in your case the zero duality gap is 'by accident'.
By adding all lifted cover inequalities to a knapsack problem one gets facets of the convex hull of the feasible integer points. The dual to the LP with the convex hull as con straint set of course would guarantee a zero duality gap.
Best regards
Ralf Gollmer
Thanks Dr. Gollmer for your precise and technical guidance. I had to search a bit about some concept you mentioned here. Thus, I learned a lot more.
Thanks again.
Researchers have developed strong duals for MILP, but they are rather complicated (e.g., there is a strong dual based on subadditive functions).
There are also some papers on computing "approximate" dual prices for MILPs. See, e.g.,
Wolsey, L. A. (1981). Integer programming duality: Price functions and sensitivity analysis. Mathematical Programming, 20(1), 173-195.
Williams, A. C. (1989). Marginal values in mixed integer linear programming. Mathematical Programming, 44(1-3), 67-75.
Williams, H. P. (1996). Duality in mathematics and linear and integer programming. Journal of Optimization Theory and Applications, 90(2), 257-278.
Drexl, A., & Jörnsten, K. (2007). Reflections about pseudo-dual prices in combinatorial auctions. Journal of the Operational Research Society, 58(12), 1652-1659.
Thank you very much, Dr. Letchford. I am sure aforementioned papers would be of great use to me. Specially in order to get a sense of marginal values or Lagrange multipliers of a constraint with Binary variable. I do need it.
I unfortunately am not familiar with the papers referenced by Dr. Letchford. But, if you are interested in dual values just to identify constraints in your MILP that prevent the objective from improving, I've had some success with the following approach. First you solve your MILP of interest to get the optimal objective value. Then you constraint the objective function to be slightly better than this optimal value. Clearly that MILP is infeasible. Then you compute a minimal set of infeasible constraints for this infeasible MILP (in CPLEX, the conflict refiner feature will do this for you). The constraints in this minimal set are ones that are preventing the current objective from improving, because removal of any one makes this infeasible MILP feasible, i.e. it allows the optimal objective of your original MILP to improve.
So if you are interested in some notion of duality on a MILP to help with post-optimality analysis, this approach may give you enough information to be useful. But if you are looking for some true dual values to use, this doesn't really help (although perhaps you could do some additional computations on the minimal set of infeasible constraints to get more info).
Check the book: Optimization over Integers, by Bertsimas and Weismantel. The chapter 4 of this book contains different ways to convert an integer linear programming (ILP) into linear programming (LP). Thus, the dual of this LP is what you looking for.
- Badges
- Science topic
- Similar topics
- Engineering
- Modeling