Algorithms for highly symmetric linear and integer programs

Bödi, Richard; Herr, Katrin; Joswig, Michael

doi:10.21256/zhaw-1736

Please use this identifier to cite or link to this item: https://doi.org/10.21256/zhaw-1736

Publication type:	Article in scientific journal
Type of review:	Peer review (publication)
Title:	Algorithms for highly symmetric linear and integer programs
Authors:	Bödi, Richard Herr, Katrin Joswig, Michael
DOI:	10.21256/zhaw-1736 10.1007/s10107-011-0487-6
Published in:	Mathematical Programming
Volume(Issue):	137
Issue:	1-2
Page(s):	65
Pages to:	90
Issue Date:	Feb-2013
Publisher / Ed. Institution:	Springer
Publisher / Ed. Institution:	Berlin
ISSN:	0025-5610
Language:	English
Subjects:	Linear programming; Symmetry; Integer programming; Permutation group
Subject (DDC):	510: Mathematics
Abstract:	This paper deals with exploiting symmetry for solving linear and integer programming problems. Basic properties of linear representations of finite groups can be used to reduce symmetric linear programming to solving linear programs of lower dimension. Combining this approach with knowledge of the geometry of feasible integer solutions yields an algorithm for solving highly symmetric integer linear programs which only takes time which is linear in the number of constraints and quadratic in the dimension.
Further description:	Erworben im Rahmen der Schweizer Nationallizenzen (http://www.nationallizenzen.ch)
URI:	https://digitalcollection.zhaw.ch/handle/11475/3232
Fulltext version:	Published version
License (according to publishing contract):	Licence according to publishing contract
Departement:	School of Engineering
Organisational Unit:	Institute of Data Analysis and Process Design (IDP)
Appears in collections:	Publikationen School of Engineering

Files in This Item:

File	Description	Size	Format
2013_Bödi_Algorithms for highly_Math Program.pdf		326.38 kB	Adobe PDF	View/Open

Show full item record

Bödi, R., Herr, K., & Joswig, M. (2013). Algorithms for highly symmetric linear and integer programs. Mathematical Programming, 137(1-2), 65–90. https://doi.org/10.21256/zhaw-1736

Bödi, R., Herr, K. and Joswig, M. (2013) ‘Algorithms for highly symmetric linear and integer programs’, Mathematical Programming, 137(1-2), pp. 65–90. Available at: https://doi.org/10.21256/zhaw-1736.

R. Bödi, K. Herr, and M. Joswig, “Algorithms for highly symmetric linear and integer programs,” Mathematical Programming, vol. 137, no. 1-2, pp. 65–90, Feb. 2013, doi: 10.21256/zhaw-1736.

BÖDI, Richard, Katrin HERR und Michael JOSWIG, 2013. Algorithms for highly symmetric linear and integer programs. Mathematical Programming. Februar 2013. Bd. 137, Nr. 1-2, S. 65–90. DOI 10.21256/zhaw-1736

Bödi, Richard, Katrin Herr, and Michael Joswig. 2013. “Algorithms for Highly Symmetric Linear and Integer Programs.” Mathematical Programming 137 (1-2): 65–90. https://doi.org/10.21256/zhaw-1736.

Bödi, Richard, et al. “Algorithms for Highly Symmetric Linear and Integer Programs.” Mathematical Programming, vol. 137, no. 1-2, Feb. 2013, pp. 65–90, https://doi.org/10.21256/zhaw-1736.