Dynamic Lagrangian dual and reduced RLT constructs for solving 0- mixed-integer programs
详细信息 查看全文
- 作者：Hanif D. Sherali (1)
J. Cole Smith (2) - 关键词：Mixed ; integer programming ; Dynamic Lagrangian dual ; Delayed relax ; and ; cut approach ; Reformulation ; Linearization Technique (RLT) ; Valid inequalities ; 90C11 ; 90-8 ; 90C57
- 刊名：TOP
- 出版年：2012
- 出版时间：April 2012
- 年：2012
- 卷：20
- 期：1
- 页码：173-189
- 全文大小：576KB
- 参考文献：1. Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0- programs. Math Program 58(3):295-24 CrossRef
2. Balas E, Ceria S, Cornuéjols G (1996) Mixed integer 0- programming by lift-and-project in a branch-and-bound framework. Manag Sci 42(9):1229-246 CrossRef
3. Barahona F, Anbil R (2000) The volume algorithm: Producing primal solutions with a subgradient method. Math Program 87:385-99 CrossRef
4. Camerini PM, Fratta L, Maffioli F (1975) On improving relaxation methods by modified gradient techniques. Math Program Stud 3:26-4 CrossRef
5. Escudero LF, Guignard M, Malik K (1994) A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships. Ann Oper Res 50:219-37 CrossRef
6. Fisher M (1981) The Lagrangian relaxation method for solving integer programming problems. Manag Sci 27(1):1-8 CrossRef
7. Guignard M (1998) Efficient cuts in Lagrangean ‘relax-and-cut-schemes. Eur J Oper Res 105(1):216-23 CrossRef
8. Held M, Wolfe P, Crowder H (1974) Validation of subgradient optimization. Math Program 6:62-8 CrossRef
9. Kiwiel KC (1990) Proximity control in bundle methods for convex nondifferentiable minimization. Math Program 46(1-):105-22 CrossRef
10. Larsson T, Patriksson M, Str?mberg A-B (1999) Ergodic, primal convergence in dual subgradient schemes for convex programming. Math Program 86:283-12 CrossRef
11. Lim C, Sherali HD (2006a) Convergence and computational analyses for some variable target value and subgradient deflection methods. Comput Optim Appl, 34(3):409-28 CrossRef
12. Lim C, Sherali HD (2006b) A trust region target value method for optimizing nondifferentiable Lagrangian duals of linear programs. Math Methods Oper Res, 64(1):33-3 CrossRef
13. Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0- optimization. SIAM J Optim 1:166-90 CrossRef
14. Lucena A (1992) Steiner problem in graphs: Lagrangian relaxation and cutting planes. COALA Bull, 21:2-
15. Lucena A (2005) Non-delayed relax-and-cut algorithms. Ann Oper Res 140:375-10 CrossRef
16. Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization, 2nd edn. Wiley, New York
17. Nesterov Y (2005) Smooth minimization of non-smooth functions. Math Program 103:127-52 CrossRef
18. Polyak BT (1967) A general method of solving extremum problems. Sov Math Dokl 8:593-97
19. Polyak BT (1969) Minimization of unsmooth functionals. USSR Comput Math Math Phys 9:14-9 CrossRef
20. Shapiro JF (1979) A survey of Lagrangean techniques for discrete optimization. Ann Discrete Math 5:113-38 CrossRef
21. Sherali HD, Adams WP (1990) A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J Discrete Math 3(3):411-30 CrossRef
22. Sherali HD, Adams WP (1994) A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems. Discrete Appl Math 52(1):83-06 CrossRef
23. Sherali HD, Choi G (1996) Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs. Oper Res Lett 19(3):105-13 CrossRef
24. Sherali HD, Lim C (2004) On embedding the Volume Algorithm in a variable target value method for solving Lagrangian relaxations of linear programs. Oper Res Lett 32(5):455-62 CrossRef
25. Sherali HD, Lim C (2007) Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability. INFORMS J Comput 19(1):3-3 CrossRef
26. Sherali HD, Tuncbilek CH (1995) A reformulation-convexification approach for solving nonconvex quadratic programming problems. J Glob Optim 7:1-1 CrossRef
27. Sherali HD, Tuncbilek CH (1997) New Reformulation-Linearization/Convexification relaxations for univariate and multivariate polynomial programming problems. Oper Res Lett 21(1):1-0 CrossRef
28. Sherali HD, Ulular O (1989) A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems. Appl Math Optim 20:193-21 CrossRef
29. Sherali HD, Choi G, Tuncbilek CH (2000a) A variable target value method for nondifferentiable optimization. Oper Res Lett 26(1):1- CrossRef
30. Sherali HD, Smith JC, Adams WP (2000b) Reduced first-level representations via the reformulation-linearization technique: Results, counter-examples, and computations. Discrete Appl Math 101(1):247-67 CrossRef
31. Shor NZ (1985) Minimization methods for nondifferentiable functions. Springer, Berlin CrossRef - 作者单位：Hanif D. Sherali (1)
J. Cole Smith (2)
1. Grado Department of Industrial and Systems Engineering (0118), Virginia Polytechnic Institute and State University, Blacksburg, VA, 24061, USA
2. Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL, 32611, USA - ISSN：1863-8279
文摘
In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0- linear programming problems. Similarly to delayed relax-and-cut approaches, the procedure dynamically appends valid inequalities to the linear programming relaxation as induced by the Reformulation-Linearization Technique (RLT). A Lagrangian dual algorithm that is augmented with a primal solution recovery scheme is applied implicitly to a full or partial first-level RLT relaxation, where RLT constraints that are currently being violated by the primal estimate are dynamically generated within the Lagrangian dual problem, thus controlling the size of the dual space while effectively capturing the strength of the RLT-enhanced relaxation. We present a preliminary computational study to demonstrate the efficacy of this approach.