Loeschner, Kristina (2002) Symmetry in combinatorial optimization. Masters thesis, Concordia University.
Integer optimization is in the class of NP-hard problems, and it is very time and memory intensive to find optimal solutions. In this thesis an algorithm will be developed to improve the efficiency in solving a linear integer program if there are symmetries in the problem, that is, variables can be permuted without changing the integer program. Using the group of symmetries, the size of the feasible set can be restricted. For the smaller optimization problem, common solution methods will be able to find the optimal solutions faster than for the original problem. The set of all optimal solutions can be generated from the determined ones by applying the symmetry group.
|Divisions:||Concordia University > Faculty of Arts and Science > Mathematics and Statistics|
|Item Type:||Thesis (Masters)|
|Pagination:||viii, 53 leaves : ill. ; 29 cm.|
|Degree Name:||Theses (M.Sc.)|
|Program:||Mathematics and Statistics|
|Thesis Supervisor(s):||Lam, Clement|
|Deposited By:||Concordia University Libraries|
|Deposited On:||27 Aug 2009 17:22|
|Last Modified:||08 Dec 2010 15:22|
Repository Staff Only: item control page