Title  A TwoLevel Approach to Large MixedInteger Programs with Application to CoGeneration in EnergyEfficient Buildings 
Publication Type  Journal Article 
Year of Publication  2015 
Authors  Lin, F, Leyffer, S, Munson, T 
Journal  Computational Optimization and Applications 
Pagination  146 
Date Published  04/2016 
Other Numbers  ANL/MCSP53320415 
Abstract  We study a twostage mixedinteger linear program (MILP) with more than 1 million binary variables in the second stage. We develop a twolevel approach by constructing a semicoarse model (coarsened with respect to variables) and a coarse model (coarsened with respect to both variables and constraints). We coarsen binary variables by selecting a small number of prespecified daily on/off profiles. We aggregate constraints by partitioning them into groups and summing 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 semicoarse 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 twolevel approach scales to large problems that are beyond the capacity of stateoftheart commercial MILP solvers.

URL  http://link.springer.com/article/10.1007%2Fs1058901698420 
PDF  http://www.mcs.anl.gov/papers/P53320415.pdf 