Generating Multiple Solutions for Mixed Integer Programming Problems Export

@incollection{citeulike:6083901, abstract = {As mixed integer programming (MIP) problems become easier to solve in pratice, they are used in a growing number of applications where producing a unique optimal solution is often not enough to answer the underlying business problem. Examples include problems where some optimization criteria or some constraints are difficult to model, or where multiple solutions are wanted for quick solution repair in case of data changes. In this paper, we address the problem of effectively generating multiple solutions for the same model, concentrating on optimal and near-optimal solutions. We first define the problem formally, study its complexity, and present three different algorithms to solve it. The main algorithm we introduce, the one-tree algorithm, is a modification of the standard branch-and-bound algorithm. Our second algorithm is based on MIP heuristics. The third algorithm generalizes a previous approach that generates solutions sequentially. We then show with extensive computational experiments that the one-tree algorithm significantly outperforms previously known algorithms in terms of the speed to generate multiple solutions, while providing an acceptable level of diversity in the solutions produced.}, author = {Danna, Emilie and Fenelon, Mary and Gu, Zonghao and Wunderling, Roland}, citeulike-article-id = {6083901}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-72792-7_22}, citeulike-linkout-1 = {http://www.springerlink.com/content/k7qtm5uh2x024j37}, doi = {10.1007/978-3-540-72792-7_22}, journal = {Integer Programming and Combinatorial Optimization}, keywords = {assignments, diversity, integer, linear, nmr, programming}, pages = {280--294}, posted-at = {2009-11-08 10:43:29}, priority = {2}, title = {Generating Multiple Solutions for Mixed Integer Programming Problems}, url = {http://dx.doi.org/10.1007/978-3-540-72792-7_22}, year = {2007} }

TY - CHAP ID - citeulike:6083901 L3 - citeulike-article-id:6083901 N2 - As mixed integer programming (MIP) problems become easier to solve in pratice, they are used in a growing number of applications where producing a unique optimal solution is often not enough to answer the underlying business problem. Examples include problems where some optimization criteria or some constraints are difficult to model, or where multiple solutions are wanted for quick solution repair in case of data changes. In this paper, we address the problem of effectively generating multiple solutions for the same model, concentrating on optimal and near-optimal solutions. We first define the problem formally, study its complexity, and present three different algorithms to solve it. The main algorithm we introduce, the one-tree algorithm, is a modification of the standard branch-and-bound algorithm. Our second algorithm is based on MIP heuristics. The third algorithm generalizes a previous approach that generates solutions sequentially. We then show with extensive computational experiments that the one-tree algorithm significantly outperforms previously known algorithms in terms of the speed to generate multiple solutions, while providing an acceptable level of diversity in the solutions produced. JF - Integer Programming and Combinatorial Optimization EP - 294 TI - Generating Multiple Solutions for Mixed Integer Programming Problems SP - 280 KW - assignments KW - diversity KW - integer KW - linear KW - nmr KW - programming AU - Danna, Emilie AU - Fenelon, Mary AU - Gu, Zonghao AU - Wunderling, Roland PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-72792-7_22 ER -