Computational Problem Solving (2235.YR.015726.1)

General information

Type:	OBL	Curs:	1	Period:	S semester
ECTS Credits:	6 ECTS

Teaching Staff:

To follow the course students should have successfully completed previous courses dedicated to laying the foundations of algorithmic thinking and computer programming, including "Computing Foundations", "Programming with Data" and "Data Structures and Algorithm Design" (formerly known as Advanced Algorithms).

The course will assume student to be familiar with basic Python programming routines, including loops, conditionals and functions, as well as more advanced topics and object-oriented programming Students should also be comfortable in debugging their code and writing code that's properly structured and understandable.

To achieve the objectives, this course will be based on lectures, class discussions and practice. Lectures and in-class exercises will represent 50% of the workload. The assignments and the preparation for the mid-term and final exams will represent the other 50% of the workload.

This course aims to develop a comprehensive understanding of optimization and modeling approaches to effectively tackle complex economic, social and environmental challenges. By integrating optimization methods and simulations, the course bridges the gap between theory and practice, empowering students with computational problem-solving skills. In the context of business administration and artificial intelligence, these techniques are highly relevant and applicable across various domains, including operations management, finance, marketing, and strategic planning. Students will be well-equipped to analyze data, optimize processes, and devise innovative solutions, which are essential competencies in the evolving landscape of business and technology.

The course will focus on two main areas: optimization methods and simulations.

Optimization methods play a crucial role in enhancing decision-making processes and maximizing outcomes. By exploring various techniques such as hill-climbing search, simulated annealing, and tabu search. The hill-climbing search involves iteratively improving a solution by making small changes, while simulated annealing mimics the process of annealing to find global optima. Tabu search utilizes a memory mechanism to avoid revisiting previously explored solutions. Combined together, these methods will equip students with tools to identify the most optimal solution, leading to increased efficiency, cost savings, and competitive advantage.

The second part of the course will delve into simulations, starting with Monte Carlo simulations that utilize random sampling to estimate outcomes. We will then introduce evolutionary algorithms that involve iterative selection, recombination, and mutation to find optimal solutions. Finally, we describe ant algorithms, a kind of algorithm that is inspired by the behaviour of ants and their pheromone trails to solve complex problems.

The course will end by explaining the basis of agent-based simulations, which will allow students to explore emergent properties and simulate the behaviour of individual agents within a system, providing insights into the dynamics of emergent social, environmental and economic phenomena.

From State Space Search to optimization
- Hill-climbing search
- Simulated annealing
- Tabu search

Simulations
- Montecarlo simulations
- Evolutionary algorithms
- Ant algorithms
- Agent based simulations

1. Optimization methods

1.1. Hill-climbing search A hill-climbing algorithm is an Artificial Intelligence (AI) algorithm that increases in value continuously until it achieves a peak solution. This algorithm is used to optimize mathematical problems and in other real-life applications like marketing and job scheduling

1.2. Simulated annealing Simulated annealing is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem

1.3. Tabu search The tabu search is an optimization technique that uses a guided local search procedure that avoids local optima and rejects moves to points already visited in the search space by means of the so-called tabu list.

2. Simulations

2.1. Montecarlo simulations Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle.

2.2. Evolutionary algorithms An evolutionary algorithm is an algorithm that uses mechanisms inspired by nature and solves problems through processes that emulate the behaviors of living organisms.

2.3. Ant colony optimization the ant colony optimization algorithms are probabilistic techniques for solving computational problems which can be reduced to finding good paths through graphs.

2.4. Agent-based simulations Agent-based models are computer simulations used to study the interactions between people, things, places, and time. They are stochastic models built from the bottom up meaning individual agents (often people in epidemiology) are assigned certain attributes.

Lecture/Discussion. During theoretical lessons, we will introduce the basic concepts for each topic. These sessions will be devoted to the presentation and discussion of frameworks, concepts, and theories.

Practice. In Practice sessions, students will work with different practical exercises. In-class exercises will help to interiorize and reflect the concepts and discussed in theory class. Exercises can be on paper or with Python.

ASSESSMENT BREAKDOWN

Stefan Edelkamp and Stefan Schrödl, Heuristic Search: Theory and Applications, Elsevier, ISBN: 978-0-12-372512-7, 2012.
Uri Wilensky, William Rand. An Introduction to Agent-Based Modeling: Modeling Natural, Social, and Engineered Complex Systems with NetLogo, The MIT Press, 2015.