Login | Register

Symmetry in combinatorial optimization


Symmetry in combinatorial optimization

Loeschner, Kristina (2002) Symmetry in combinatorial optimization. Masters thesis, Concordia University.

[thumbnail of MQ72888.pdf]
Text (application/pdf)


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)
Authors:Loeschner, Kristina
Pagination:viii, 53 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:M.Sc.
Thesis Supervisor(s):Lam, Clement
Identification Number:QA 402.5 L64 2002
ID Code:1753
Deposited By: Concordia University Library
Deposited On:27 Aug 2009 17:22
Last Modified:13 Jul 2020 19:50
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top