Abstract
In this paper, we consider a dynamic Lagrangian dual optimization procedure for solving mixed-integer 0–1 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balas E, Ceria S, Cornuéjols G (1993) A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math Program 58(3):295–324
Balas E, Ceria S, Cornuéjols G (1996) Mixed integer 0–1 programming by lift-and-project in a branch-and-bound framework. Manag Sci 42(9):1229–1246
Barahona F, Anbil R (2000) The volume algorithm: Producing primal solutions with a subgradient method. Math Program 87:385–399
Camerini PM, Fratta L, Maffioli F (1975) On improving relaxation methods by modified gradient techniques. Math Program Stud 3:26–34
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–237
Fisher M (1981) The Lagrangian relaxation method for solving integer programming problems. Manag Sci 27(1):1–18
Guignard M (1998) Efficient cuts in Lagrangean ‘relax-and-cut’ schemes. Eur J Oper Res 105(1):216–223
Held M, Wolfe P, Crowder H (1974) Validation of subgradient optimization. Math Program 6:62–88
Kiwiel KC (1990) Proximity control in bundle methods for convex nondifferentiable minimization. Math Program 46(1–3):105–122
Larsson T, Patriksson M, Strömberg A-B (1999) Ergodic, primal convergence in dual subgradient schemes for convex programming. Math Program 86:283–312
Lim C, Sherali HD (2006a) Convergence and computational analyses for some variable target value and subgradient deflection methods. Comput Optim Appl, 34(3):409–428
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–53
Lovász L, Schrijver A (1991) Cones of matrices and set-functions and 0–1 optimization. SIAM J Optim 1:166–190
Lucena A (1992) Steiner problem in graphs: Lagrangian relaxation and cutting planes. COALA Bull, 21:2–8
Lucena A (2005) Non-delayed relax-and-cut algorithms. Ann Oper Res 140:375–410
Nemhauser GL, Wolsey LA (1999) Integer and combinatorial optimization, 2nd edn. Wiley, New York
Nesterov Y (2005) Smooth minimization of non-smooth functions. Math Program 103:127–152
Polyak BT (1967) A general method of solving extremum problems. Sov Math Dokl 8:593–597
Polyak BT (1969) Minimization of unsmooth functionals. USSR Comput Math Math Phys 9:14–29
Shapiro JF (1979) A survey of Lagrangean techniques for discrete optimization. Ann Discrete Math 5:113–138
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–430
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–106
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–113
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–462
Sherali HD, Lim C (2007) Enhancing Lagrangian dual optimization for linear programs by obviating nondifferentiability. INFORMS J Comput 19(1):3–13
Sherali HD, Tuncbilek CH (1995) A reformulation-convexification approach for solving nonconvex quadratic programming problems. J Glob Optim 7:1–31
Sherali HD, Tuncbilek CH (1997) New Reformulation-Linearization/Convexification relaxations for univariate and multivariate polynomial programming problems. Oper Res Lett 21(1):1–10
Sherali HD, Ulular O (1989) A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems. Appl Math Optim 20:193–221
Sherali HD, Choi G, Tuncbilek CH (2000a) A variable target value method for nondifferentiable optimization. Oper Res Lett 26(1):1–8
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–267
Shor NZ (1985) Minimization methods for nondifferentiable functions. Springer, Berlin
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sherali, H.D., Smith, J.C. Dynamic Lagrangian dual and reduced RLT constructs for solving 0–1 mixed-integer programs. TOP 20, 173–189 (2012). https://doi.org/10.1007/s11750-011-0199-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-011-0199-3
Keywords
- Mixed-integer programming
- Dynamic Lagrangian dual
- Delayed relax-and-cut approach
- Reformulation-Linearization Technique (RLT)
- Valid inequalities