×

A two-level approach to large mixed-integer programs with application to cogeneration in energy-efficient buildings. (English) Zbl 1353.90093

Summary: We study a two-stage mixed-integer linear program (MILP) with more than 1 million binary variables in the second stage. We develop a two-level approach by constructing a semi-coarse model that coarsens with respect to variables and a coarse model that coarsens with respect to both variables and constraints. We coarsen binary variables by selecting a small number of prespecified on/off profiles. We aggregate constraints by partitioning them into groups and taking convex combination over each group. With an appropriate choice of coarsened profiles, the semi-coarse model is guaranteed to find a feasible solution of the original problem and hence provides an upper bound on the optimal solution. We show that solving a sequence of coarse models converges to the same upper bound with proven finite steps. This is achieved by adding violated constraints to coarse models until all constraints in the semi-coarse model are satisfied. We demonstrate the effectiveness of our approach in cogeneration for buildings. The coarsened models allow us to obtain good approximate solutions at a fraction of the time required by solving the original problem. Extensive numerical experiments show that the two-level approach scales to large problems that are beyond the capacity of state-of-the-art commercial MILP solvers.

MSC:

90C11 Mixed integer programming
90C06 Large-scale problems in mathematical programming
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
90C90 Applications of mathematical programming

Software:

AMPL; EnergyPlus
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alguacil, N., Motto, A.L., Conejo, A.J.: Transmission expansion planning: a mixed-integer LP approach. IEEE Trans. Power Syst. 18(3), 1070-1077 (2003)
[2] Balas, E.: An additive algorithm for solving linear programs with zero-one variables. Oper. Res. 13(4), 517-546 (1965) · Zbl 0194.19903
[3] Bard, J.F.: Short-term scheduling of thermal-electric generators using Lagrangian relaxation. Oper. Res. 36(5), 756-766 (1988) · Zbl 0655.90030
[4] Barnhart, C., Johnson, E.L., Nemhauser, G.L., Savelsbergh, M.W., Vance, P.H.: Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3), 316-329 (1998) · Zbl 0979.90092
[5] Birge, J.R.: Aggregation bounds in stochastic linear programming. Math. Program. 31(1), 25-41 (1985) · Zbl 0562.90066
[6] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, Berlin (2011) · Zbl 1223.90001
[7] Clay, R.L., Grossmann, I.E.: A disaggregation algorithm for the optimization of stochastic planning models. Comput. Chem. Eng. 21(7), 751-774 (1997)
[8] Crawley, D.B., Lawrie, L.K., Winkelmann, F.C., et al.: EnergyPlus: creating a new-generation building energy simulation program. Energy Build. 33(4), 319-331 (2001)
[9] Crawley, D.B., Pedersen, C.O., Lawrie, L.K., Winkelmann, F.C.: EnergyPlus: energy simulation program. ASHRAE J. 42, 49-56 (2000)
[10] Edmunds, T.A., Bard, J.F.: An algorithm for the mixed-integer nonlinear bilevel programming problem. Ann. Oper. Res. 34(1), 149-162 (1992) · Zbl 0751.90054
[11] Elhallaoui, I., Villeneuve, D., Soumis, F., Desaulniers, G.: Dynamic aggregation of set-partitioning constraints in column generation. Oper. Res. 53(4), 632-645 (2005) · Zbl 1165.90604
[12] Energy Information Administration: Average retail price of electricity, monthly. http://www.eia.gov/electricity/data/browser/#/topic/7?agg=0,1&geo=vvvvvvvvvvvvo&endsec=vg&linechart= ELEC.PRICE.IL-ALL.M&columnchart=ELEC.PRICE.US-ALL.M&map=ELEC.PRICE.US-ALL.M&freq=M&start=200101&end=201402&ctype=linechart&ltype=pin&rtype=s&maptype=0&rse=0&pin= (2015)
[13] Falgout, R.D.: An introduction to algebraic multigrid. Comput. Sci. Eng. 8(6), 24-33 (2006)
[14] Fisher, M.L.: The Lagrangian relaxation method for solving integer programming problems. Manag. Sci. 27(1), 1-18 (1981) · Zbl 0466.90054
[15] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming. Cengage Learning, Boston (2012) · Zbl 0701.90062
[16] Gelman, E., Mandel, J.: On multilevel iterative methods for optimization problems. Math. Program. 48(1-3), 1-17 (1990) · Zbl 0738.90059
[17] Geoffrion, A.M.: An improved implicit enumeration approach for integer programming. Oper. Res. 17(3), 437-454 (1969) · Zbl 0174.20801
[18] Geoffrion, A.M.: Lagrangean Relaxation for Integer Programming. Springer, Berlin (1974) · Zbl 0395.90056
[19] Glover, F.: Surrogate constraints. Oper. Res. 16(4), 741-749 (1968) · Zbl 0165.22602
[20] Glover, F.: Heuristics for integer programming using surrogate constraints. Decis. Sci. 8(1), 156-166 (1977)
[21] Gratton, S., Sartenaer, A., Toint, P.L.: Recursive trust-region methods for multiscale nonlinear optimization. SIAM J. Optim. 19(1), 414-444 (2008) · Zbl 1163.90024
[22] Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Stat. Comput. 13(5), 1194-1217 (1992) · Zbl 0760.65063
[23] Hedman, K.W., Ferris, M.C., O’Neill, R.P., Fisher, E.B., Oren, S.S.: Co-optimization of generation unit commitment and transmission switching with N-1 reliability. IEEE Trans. Power Syst. 25(2), 1052-1063 (2010)
[24] Jain, A.K.: Data clustering: 50 years beyond K-means. Pattern Recognit. Lett. 31(8), 651-666 (2010)
[25] Mathews, G.B.: On the partition of numbers. Proc. Lond. Math. Soc. 1(1), 486-490 (1896) · JFM 28.0168.03
[26] Moore, J.T., Bard, J.F.: The mixed integer linear bilevel programming problem. Oper. Res. 38(5), 911-921 (1990) · Zbl 0723.90090
[27] Pinar, A., Meza, J., Donde, V., Lesieutre, B.: Optimization strategies for the vulnerability analysis of the electric power grid. SIAM J. Optim. 20(4), 1786-1810 (2010) · Zbl 1201.90138
[28] Pruitt, K.A., Braun, R.J., Newman, A.M.: Evaluating shortfalls in mixed-integer programming approaches for the optimal design and dispatch of distributed generation systems. Appl. Energy 102, 386-398 (2013)
[29] Pruitt, K.A., Leyffer, S., Newman, A.M., Braun, R.J.: A mixed-integer nonlinear program for the optimal design and dispatch of distributed generation systems. Optim. Eng. 15, 167-197 (2014) · Zbl 1314.90056
[30] Ren, H., Gao, W.: A MILP model for integrated plan and evaluation of distributed energy systems. Appl. Energy 87(3), 1001-1014 (2010)
[31] Rogers, D.F., Plante, R.D., Wong, R.T., Evans, J.R.: Aggregation and disaggregation techniques and methodology in optimization. Oper. Res. 39(4), 553-582 (1991) · Zbl 0729.90738
[32] Scaparra, M.P., Church, R.L.: A bilevel mixed-integer program for critical infrastructure protection planning. Comput. Oper. Res. 35(6), 1905-1923 (2008) · Zbl 1139.90439
[33] Siddiqui, A.S., Marnay, C., Bailey, O., Hamachi LaCommare, K.: Optimal selection of on-site generation with combined heat and power applications. Int. J. Distrib. Energy Res. 1(1), 33-62 (2005)
[34] Stadler, M., Marnay, C., Siddiqui, A., Lai, J., Coffey, B., Aki, H.: Effect of heat and electricity storage and reliability on microgrid viability: A study of commercial buildings in California and New York states. Lawrence Berkeley National Laboratory Technical Report LBNL-1334E (2009) · Zbl 0441.90057
[35] Vicente, L.N., Calamai, P.H.: Bilevel and multilevel programming: a bibliography review. J. Glob. Optim. 5(3), 291-306 (1994) · Zbl 0822.90127
[36] Wen, U.P., Hsu, S.T.: Linear bi-level programming problems—a review. J. Oper. Res. Soc. 42(2), 125-133 (1991) · Zbl 0722.90046
[37] Wen, U.P., Huang, A.D.: A simple tabu search method to solve the mixed-integer linear bilevel programming problem. Eur. J. Oper. Res. 88(3), 563-571 (1996) · Zbl 0908.90194
[38] Wen, U.P., Yang, Y.H.: Algorithms for solving the mixed integer two-level linear programming problem. Comput. Oper. Res. 17(2), 133-142 (1990) · Zbl 0683.90055
[39] Wen, Z., Goldfarb, D.: A line search multigrid method for large-scale nonlinear optimization. SIAM J. Optim. 20(3), 1478-1503 (2009) · Zbl 1203.65095
[40] Zipkin, P.H.: Bounds for row-aggregation in linear programming. Oper. Res. 28(4), 903-916 (1980) · Zbl 0441.90057
[41] Zipkin, P.H.: Bounds on the effect of aggregating variables in linear programs. Oper. Res. 28(2), 403-418 (1980) · Zbl 0426.90056
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.