This subject is taught during the second semester of the second academic year of the degree. When the student arrives, she/he will have already acquired the basic mathematical knowledge necessary to work on mathematical formalization and problem solving. The knowledge about solving systems of linear equations, graph theory and combinatorics studied in the subjects of "Discrete Mathematics" and "Algebra" in the first academic year is fundamental.



Based on this basic mathematical knowledge, the subject is an introduction to the resolution of optimization problems. At the content level two major parts are distinguished: linear programming and heuristic optimization.



In the first part, the classic techniques of solving linear optimization problems are analyzed. To begin with, the mathematical formalization of the problem is studied, and linear models that represent them are constructed. Next, some of the linear programming techniques available for resolution are studied: the Simplex algorithm, the dual Simplex algorithm, the algorithms for the transportation problem and the assignment problem, and the branch and bound algorithms for integer linear problems.



In the second part, heuristic methods that are currently having great success and are one of the most promising lines to follow in optimization are presented. Students are asked to work on the formalization of problems and some well known algorithms are analyzed for their resolution: the constructive algorithms, the local search algorithms and the genetic algorithms.



Starting at the mathematical formalization, this subject provides the theoretical and practical knowledge necessary to deal with the resolution of real problems. In the professional practice of Computer Science and Artificial Intelligence, it is necessary to have the ability to find a computer solution to optimization problems that very frequently arise in different areas of application. Student who wish to follow with problem solving related subjects are encouraged to go on with the specialty of Computation or the subject of "Heuristic Search" nowadays offered in Basque as "Bilaketa Heuristikoak", among others.

* To be able to identify the kinds of problems addressed with linear programming and heuristic optimization.



* To show the ability to represent such problems constructing linear models or using the appropriate formalization.



* To understanding the underlying theory of the algorithms and methods used to solve the problems and to develop the ability to use them using specific software.



* To interpret the solution obtained and to be able to make the correct decisions for real problems

1. Linear algebra. Linear models

1.1 Systems of linear equations

1.2 Vector spaces. Basic solutions

1.3 Convex sets

1.4 Linear models

1.5 Graphical solution



2. Linear programming

2.1 The simplex method

2.2 The Big-M method. The two-phase method

2.3 Sensitivity analysis



3. Duality

3.1 The dual simplex method

3.2 The artificial constraint technique

3.3 Economic interpretation of duality



4. Integer programming

4.1 The branch and bound algorithm

4.2 The 0-1 branch and bound algorithm



5. The transportation problem. The assignment problem

5.1 The transportation algorithm

5.2 The Hungarian algorithm



6. Heuristic optimization

6.1 Combinatorial optimization problems

6.2 Constructive (Greedy) algorithms

6.3 Local Search

6.4 Genetic algorithms

The learning methodology used in the classroom gives students a prominent role. A methodology that aggregates two working styles is followed in this subject:



* In the classes, the theory is discussed constructively and students are invited to take part in the discussion, so that they can raise and resolve doubts, train their oral communication skills and work actively as a team. Problems are solved on the blackboard.



* In the laboratory sessions, using specific computer software and bibliographic resources, students will be encouraged to work autonomously in the resolution of problems, with the close help of the lecturer.

• Continuous Assessment System
• Final Assessment System
• Tools and qualification percentages:
  • The percentages and types of assessment are detailed in the following sections (%): 100

The student can be evaluated under two types of assessments: continuous or final. The continuous assessment system is prioritized, as indicated in the regulation of the UPV/EHU.



If a student who meets the requirements of continuous assessment wishes to opt for the final assessment, he or she must inform the lecturers responsible for the subject in the following manner and within the following deadlines: via eGela once the written test has been graded.



CONTINUOUS ASSESSMENT:

- Written test (60%)

- Practical computer test (20%)

- Team-works (20%)



In order to pass the subject in continuous assessment, it is necessary to pass the written test, to pass the practical computer test, to deliver the team-works and to get a minimum of 50/100 points in total.



FINAL ASSESSMENT:

- Written test (80%)

- Practical computer test (20%)



In order to pass the subject in final assessment, it is necessary to pass the written test and the practical computer test. If both the written test and the practical computer test are not carried out, it is assumed that the student gives up to the assessment.

It is the same as the final assessment of the ordinary call.



- Written test (80%)

- Practical computer test (20%)



In order to pass the subject, it is necessary to pass the written test and the practical computer test. If both the written test and the practical computer test are not carried out, it is assumed that the student gives up to the assessment.

The essential material will be published in the course moodle platform (eGela).
https://egela.ehu.eus/

Moreover, for the linear programming part the following material will be used:

Operations Research. Linear Programming
Zelaia Jauregi, Ana
OpenCourseWare, eCampus, UPV/EHU (2013)
https://ocw.ehu.eus/course/view.php?id=170

In the laboratory sessions the R programming language will be used.

Basic bibliography

Operations research : applications and algorithms

Winston, Wayne L

Belmont, California: Duxbury Press, (1994)

Boston, Massachusetts: PWS Kent, (1991)



Introduction to operations research

Hillier, Frederick S and Lieberman, Gerald J

Oakland, California: Holden Day, (1986)



Operations research: an introduction

Taha, Hamdy A

Prentice-Hall. (1995), (2011)

In-depth bibliography

Linear programming and network flow
Bazaraa, Mokhtar S., Sherali, Hanif D, coautor., Jarvis, John J, coautor
John Wiley & Sons. (1990)

Linear programming
Calvert, James and Voxman, William, coautor
Harcourt Brace Jovanovich. (1989)

Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison
Christian Blum, Andrea Roli
ACM Computing Surveys, 35(3), pp. 268-308, 2003.

Journals

European Journal of Operational Research
Computers and Operations Research
Combinatorial Optimization and Applications
IEEE Transactions on Evolutionary Computation
Optimization Letters

Web addresses

http://www.r-project.org/ (R, Official website)
http://www.rstudio.com/ (RStudio, Official website)
http://lpsolve.sourceforge.net/5.5/index.htm (lpSolveAPI)
https://github.com/b0rxa/metaheuR (metaheuR)
http://www.sc.ehu.es/ccwikera/index.html (software for linear programming)
http://www.lindo.com (software for linear programming)
https://winqsb.uptodown.com/windows (software for linear programming)