Academic Year 2013/2014
- Docente: Silvano Martello
- Credits: 8
- SSD: MAT/09
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
- Corso: Second cycle degree programme (LM) in Computer Engineering (cod. 0937)
Learning outcomes
Mathematical models, linear programming, simplex algorithm,
duality. Integer linear programming, cutting planes,
branch-and-bound. Complexity. Dynamic programming. Discrete
simulation.
Course contents
Prerequisites:
It is required that the student understands written English in
order to follow the course slides.
Contents:
1. The scientific method: systems, models, methodologies
2. Mathematical Programming
2.1 Optimization problems
2.2 Convex sets and functions
2.3 Convex programming
3. Linear programming
3.1 General, canonical and standard forms
3.2 Bases e basic solutions
3.3 Convex polytopes
4. Simplex algorithm
4.1 Moving among basic solutions
4.2 Tableau and pivoting
4.3 Optimality criterion
4.4 Simplex algorithm
4.5 Two-phase method
4.6 Geometrical aspects
5. Duality
5.1 Dual of a linear programming problem
5.2 Duality properties
5.3 Farkas' lemma
5.4 Complementary slackness
5.5 Dual simplex algorithm
5.6 Primal-dual algorithm
6. Integer linear programming
6.1 Unimodularity
6.2 Cutting-plane algorithms and Gomory cuts
6.3 Branch-and-bound algorithm
6.4 Exploration strategies
6.5 0-1 knapsack problem
6.6 Branch-and-cut algorithms
7. Complexity theory
7.1 Recognition version
7.2 P and NP classes
7.3 NP-complete problems
7.4 Dynamic programming
7.5 Strong NP-completeness
8 Discrete Simulation
8.1 Generation of pseudo-random numbers
8.2 Main components of a simulation model
8.3 Simulation languages
8.4 Temporary and permanent entities
8.5 Events and event notices
8.6 Experiments
Readings/Bibliography
Textbook: S. Martello, Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2014.
The textbook contains a number of exercise solutions. For additional ones:
S. Martello, D. Vigo, Esercizi di Ricerca Operativa, Esculapio (progetto Leonardo), Bologna, 2003.
S. Martello, D. Vigo, Esercizi di Simulazione Numerica, Esculapio (progetto Leonardo), Bologna, 2001.Further readings:
C.H. Papadimitriou, K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations, Wiley, 1990 (free download)
R. Burkard, M. Dell'Amico, S. Martello, Assignment Problems - Revised reprint, SIAM, Philadelphia, 2012.Teaching methods
The course consists of lectures and class exercises.
The lectures discuss the theoretical and algorithmic aspects of the
various arguments.
In class exercises, industrial cases are introduced, and the
corresponding mathematical or simulation models are developed. The
mathematical models are solved through the algorithms developed in
the lectures.
In the laboratory the students can use commercial software for
linear programming and integer linear programming, and the
simulation language SIMSCRIPT II.5 .
Assessment methods
Written test, followed, in case of positive outcome, from an oral
test.
The written test consists in writing the simulation model of a
system and in solving, through the appropriate algorithms, simple
optimization problems. The duration of the written test is
approximately two hours.
The candidates who obtain a positive mark in the written test must
have an oral test on the theoretical contents of the course. Let k
be the examination session in which a positive mark in the written
test has been obtained: the oral test must be taken within
examination session k+2.
The overall mark is given by:
2/3 (written mark) + 1/3 (oral mark),
rounded up.
For the students who fail the oral test, the mark obtained in the
written test is preserved (within its validity window) .
Teaching tools
CRT projector
Blackboard
Applets and freewareLinks to further information
http://www.or.deis.unibo.it/staff_pages/martello/cvitae.html
Office hours
See the website of Silvano Martello