Integer programming ( efterår 2007 - 10 ECTS )
Rammer for udbud
-
Uddannelsessprog:
(se under Undervisnings- og arbejdsform)
-
Niveau:
Advanced course.
-
Semester/kvarter:
1st and 2nd quarter (Autumn 2007).
-
Timer per uge:
-
Deltagerbegrænsning:
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
7952
Formål
Integer programming is one of the major branches of Operations Research and optimization. Especially combinatorial optimization problems can be formulated as integer programming problems. Combinatorial optimization is concerned with resolving decision problems that are characterized by a finite solution space, in particular optimization problems where the objective is to find an optimal subset, an optimal partitioning of a ground set, an optimal sequence or an optimal assignment. The range of applications of such types of problems is immense, and integer programming techniques are successfully applied in many fields of economics, management, industry and engineering. This course aims at providing fundamental theoretical knowledge and important solution techniques in general integer programming.
Indhold
Modelling with binary variables; examples of integer programming problems and applications; basics of complexity theory; recapitulation of some results from convex analysis; theory of valid inequalities: Gomory-Chvátal inequalities, disjunctive constraints, superadditive valid inequalities, mixed-integer rounding, lift-and-project, valid inequalities for the knapsack polytope, lifting of valid inequalities, lifting of cover inequalities, valid inequalities for the node packing polytope, flow cover inequalities; duality and relaxation: superadditive duality, Lagrangean relaxation and duality; general algorithms: preprocessing and probing, branch-and-bound algorithms, branch-and-cut algorithms; decomposition methods: column generation and branch-and-price; Benders' decomposition, cross decomposition.
Læringsmål
At the end of this course, the students should be able to (a) model decision problems as integer programming problems in a way suitable for the chosen solution method; (b) apply standard integer programming methods and techniques; (c) overcome limitations of mixed-integer programming solvers by adding user-supplied functionalities that exploit specific problem structures and additional techniques; (d) build the insight about the underlying theory that is required for further deeper studies and investigations in that important field of Operations Research.
Faglige forudsætninger
Mathematical Programming.
Underviser
Andreas Klose.
Undervisnings- og arbejdsform
2 x 2 hours of lecture per week. English.
Litteratur
Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization, Wiley.
Litteratur
Nemhauser GL, Wolsey LA (1988) Integer and Combinatorial Optimization,
Wiley.
Eksamensterminer
Examination: 2nd quarter. Re-examination: Contact the teacher.
Udbyder
Department of Mathematical Sciences.
Tilmelding til undervisning
1-15 May 2007 at the Information Office, Department of Mathematical Sciences.
Bedømmelse
A number of exercises have to be solved during the course. The course will be evaluated using the Danish 7-scale with an external examiner.
