×

A decomposition method for large scale MILPs, with performance guarantees and a power system application. (English) Zbl 1335.93018

Summary: Lagrangian duality in mixed integer optimization is a useful framework for problem decomposition and for producing tight lower bounds to the optimal objective. However, in contrast to the convex case, it is generally unable to produce optimal solutions directly. In fact, solutions recovered from the dual may not only be suboptimal, but even infeasible. In this paper we concentrate on large scale mixed-integer programs with a specific structure that appears in a variety of application domains such as power systems and supply chain management. We propose a solution method for these structures, in which the primal problem is modified in a certain way, guaranteeing that the solutions produced by the corresponding dual are feasible for the original unmodified primal problem. The modification is simple to implement and the method is amenable to distributed computation. We also demonstrate that the quality of the solutions recovered using our procedure improves as the problem size increases, making it particularly useful for large scale problem instances for which commercial solvers are inadequate. We illustrate the efficacy of our method with extensive experimentations on a problem stemming from power systems.

MSC:

93A15 Large-scale systems
90C11 Mixed integer programming
90C46 Optimality conditions and duality in mathematical programming
93C95 Application models in control theory

Software:

CPLEX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anstreicher, K. M.; Wolsey, L. A., Two “well-known” properties of subgradient optimization, Mathematical Programming, 120, 1, 213-220 (2009) · Zbl 1180.90179
[2] Aubin, J. P.; Ekeland, I., Estimates of the duality gap in nonconvex optimization, Mathematics of Operations Research, 1, 3, 225-245 (1976) · Zbl 0366.90102
[3] Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.; Vance, P. H., Branch-and-price: Column generation for solving huge integer programs, Operations Research, 46, 3, 316-329 (1998) · Zbl 0979.90092
[4] Baumann, P.; Trautmann, N., Portfolio-optimization models for small investors, Mathematical Methods of Operations Research, 77, 3, 345-356 (2013) · Zbl 1271.91094
[6] Bertsekas, D. P., Constrained optimization and lagrange multiplier methods (1996), Athena Scientific · Zbl 0866.90059
[7] Bertsekas, D. P., Nonlinear programming (1999), Athena Scientific · Zbl 0935.90037
[8] Bertsekas, D. P., Dynamic programming & optimal control, vol. I (2005), Athena Scientific · Zbl 1125.90056
[9] Bertsekas, D. P., Convex optimization theory (2009), Athena Scientific · Zbl 1242.90001
[10] Bertsekas, D. P.; Lauer, G.; Sandell, N.; Posbergh, T., Optimal short-term scheduling of large-scale power systems, IEEE Transactions on Automatic Control, 28, 1, 1-11 (1983) · Zbl 0522.90054
[11] Birge, J. R.; Dempstert, M.a. H., Stochastic programming approaches to stochastic scheduling, Journal of Global Optimization, 9, 3-4, 417-451 (1996) · Zbl 0870.90067
[12] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge University Press · Zbl 1058.90049
[13] Callaway, D.; Hiskens, I., Achieving controllability of electric loads, Proceedings of the IEEE, 99, 1, 184-199 (2011)
[14] Caroe, C. C.; Schultz, R., Dual decomposition in stochastic integer programming, Operations Research Letters, 24, 1, 37-45 (1999) · Zbl 1063.90037
[15] Dawande, M.; Gavirneni, S.; Tayur, S., Effective heuristics for multiproduct partial shipment models, Operations Research, 54, 2, 337-352 (2006) · Zbl 1167.90686
[16] Desrosiers, J.; Lübbecke, M. E., A primer in column generation (2005), Springer · Zbl 1246.90093
[19] Geoffrion, A. M., (Lagrangean relaxation for integer programming. Lagrangean relaxation for integer programming, Mathematical programming studies, vol. 2 (1974), Springer Berlin: Springer Berlin Heidelberg) · Zbl 0395.90056
[20] Greenberg, H. J., The use of the optimal partition in a linear programming solution for postoptimal analysis, Operations Research Letters, 15, 179-185 (1994) · Zbl 0814.90077
[21] Held, M.; Karp, R. M., The Traveling-Salesman problem and minimum spanning trees, Operations Research, 18, 6, 1138-1162 (1970) · Zbl 0226.90047
[24] Lemarechal, C., Lagrangian relaxation, (Juenger, M.; Naddef, D., Computational combinatorial optimization, vol. 2241 (2001), Springer: Springer Berlin Heidelberg, Berlin, Heidelberg), 112-156 · Zbl 1052.90065
[25] Lopes, J.; Soares, F.; Almeida, P., Integration of electric vehicles in the electric power system, Proceedings of the IEEE, 99, 1, 168-183 (2011)
[26] Ma, Z.; Callaway, D.; Hiskens, I., Decentralized charging control for large populations of plug-in electric vehicles, (2010 49th IEEE conference on decision and control (CDC) (2010), IEEE), 206-212
[27] Mangasarian, O., Uniqueness of solution in linear programming, Linear Algebra and its Applications, 25, 151-162 (1979) · Zbl 0399.90053
[28] Nedic, A.; Ozdaglar, A., Approximate primal solutions and rate analysis for dual subgradient methods, SIAM Journal on Optimization, 19, 4, 1757-1780 (2009) · Zbl 1191.90037
[29] Redondo, N.; Conejo, A., Short-term hydro-thermal coordination by lagrangian relaxation: solution of the dual problem, IEEE Transactions on Power Systems, 14, 1, 89-95 (1999)
[30] Riezenman, M., The search for better batteries, IEEE Spectrum, 32, 5 (1995)
[31] Rockafellar, R. T., (Convex analysis. Convex analysis, Princeton landmarks in mathematics (1997), Princeton University Press: Princeton University Press Princeton, NJ), Reprint of the 1970 original, Princeton paperbacks
[32] Ruszczyński, A. P., Nonlinear optimization, vol. 13 (2006), Princeton University Press
[33] Shor, N.; Kiwiel, K.; Ruszczynski, A., Minimization methods for non-differentiable functions, vol. 121 (1985), Springer Verlag
[34] Sioshansi, R., Modeling the impacts of electricity tariffs on plug-in hybrid electric vehicle charging, costs, and emissions, Operations Research, 60, 3, 506-516 (2012) · Zbl 1251.90410
[35] Vanderbeck, F., Implementing mixed integer column generation, (Column generation (2005), Springer), 331-358 · Zbl 1246.90108
[38] Wilbaut, C.; Hanafi, S.; Salhi, S., A survey of effective heuristics and their application to a variety of knapsack problems, IMA Journal of Management Mathematics, 19, 3, 227-244 (2008) · Zbl 1163.90721
[39] Yamin, H., Review on methods of generation scheduling in electric power systems, Electric Power Systems Research, 69, 227-248 (2004)
[40] Yu, W.; Lui, R., Dual methods for nonconvex spectrum optimization of multicarrier systems, IEEE Transactions on Communications, 54, 7, 1310-1322 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.