Decision Support Methods

Code:

CC3003

Acronym:

CC3003

Level:

300

Keywords
Classification	Keyword
OFICIAL	Computer Science

Instance: 2018/2019 - 2S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~apt/aulas/MAD/1819
Responsible unit:	Department of Computer Science
Course/CS Responsible:	Bachelor in Computer Science

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	0	Official Study Plan	3	-	6	56	162
L:CC	64	Plano de estudos a partir de 2014	3	-	6	56	162
L:F	1	Official Study Plan	2	-	6	56	162
			3
L:G	0	study plan from 2017/18	3	-	6	56	162
L:M	2	Official Study Plan	2	-	6	56	162
			3
L:Q	0	study plan from 2016/17	3	-	6	56	162
MI:ERS	6	Plano Oficial desde ano letivo 2014	2	-	6	56	162
			3

Teaching language

Suitable for English-speaking students

Objectives

Students should:
- get familiar with techniques of operations research and constraint programming and their application to modeling and solving deterministic and stochastic decision and optimization problems.
- develop skills for understanding computational complexity of concrete problems, and choosing algorithms, programming languages and libraries/APIs for solving them.

Learning outcomes and competences

Master the main techniques in optimization.

Working method

Presencial

Program

Formulation of formal models for decision problems.
Linear Programming: the Simplex method; transportation and assignment problems. Network problems: shortest and longest paths, spanning trees, max flow, project management (Critical Path Method).
Introduction to Integer Programming and Combinatorial Optimization.
Methods and techniques for reducing the search space: dynamic programming, constraint propagation, local consistency enforcement, branch-and-bound, cutting planes, symmetry breaking, model reformulation, approximation algorithms (greedy strategies) and local search.
Constraint Programming languages and systems.
Introduction Markov Chains and queueing theory.

Mandatory literature

Hillier Frederick S.; Introduction to operations research. ISBN: 0-07-246121-7 (F. Hillier, G. Lieberman. Introduction to Operations Research. McGraw-Hill)

Complementary Bibliography

Winston Wayne L.; Operations research. ISBN: 9780534423629 (Operations research : applications and algorithms / Wayne L. Winston ; with cases by Jeffrey B. Goldberg)
Cormen Thomas H. 070; Introduction to algorithms. ISBN: 978-0-262-03293-3 (Introduction to algorithms / Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Stein)
Rossi Francesca 1962- 340; Handbook of constraint programming. ISBN: 0-444-52726-5 (Handbook of constraint programming / edited by Francesca Rossi, Peter van Beek, Toby Walsh))

Comments from the literature

For software:

GLPK documentation (http://www.gnu.org/software/glpk/glpk.html)
AMPL documentation (http://www.ampl.com)
SCIP documentation (http://scip.zib.de)
Constraint programming, Bockmayr and Hooker (http://web.tepper.cmu.edu/jnh/cp-hb.pdf)
GECODE http://www.gecode.org/
ECLIPSE http://www.eclipseclp.org/

- Some chapters from
A. P. Tomás. Métodos de Apoio à Decisão. DCC-FCUP, 2003 (in Portuguese)

Teaching methods and learning activities

Lectures: presentation of the program topics and discussion of examples.

Labs: problem solving and case studies with experimental evaluation. Development of a practical project (team work).

Assignments: practical project; oral and written presentation.
 

Software

GLPK, AMPL, SCIP, GECODE, ECLIPSE (clp)

keywords

Physical sciences > Mathematics > Computational mathematics
Physical sciences > Computer science > Programming
Physical sciences > Mathematics > Applied mathematics > Operations research

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	75,00
Trabalho laboratorial	25,00
Total:	100,00

Amount of time allocated to each course unit

designation	Time (hours)
Estudo autónomo
Frequência das aulas
Trabalho laboratorial
Total:	0,00

Eligibility for exams

Required:
* Not to exceed the absence limit (25% of total number of estimated lab classes)

 

Calculation formula of final grade

Written examination (75%). One Lab Assignment (25%) - team project (TP).
A minimum grade of 8 at 20 is required in the final exam (tests).

If it fits in the academic calendar for 2018/2019, there will be two optional tests during the semester (TE1, TE2).  To attend TE2, it is required a minimum grade of 8.0/20.0 in TE1.  The second test covers all topics.  A minimum grade of 8.0/20.0 is required also.

The final grade is given by

    max(0.4*TE1+0.6*TE2, TE2, FinalExam)*.75 + 0.25* TP

Students do not need to take the final exam if max(0.4*TE1+0.6*TE2, TE2)*0.75 + TP*0.25 >= 9.5.

Internship work/project

There will be a practical project to be developed by a team.

Special assessment (TE, DA, ...)

The same evaluation criteria for all students.

 

Classification improvement