1 of 34

TNK104 Applied Optimization

Introduction

Lecture 1

based on the slides provided by Nikolaos Pappas

Tatiana Polishchuk,

Associate Professor,

Linköping University, KTS

https://www.itn.liu.se/~tatpo46/

2 of 34

The course aims at providing you with insights into applying optimization to real-world problems

2

Aim

problem analysis
development of mathematical models
design and implementation of algorithms
computational experiments and results analysis

You are expected to gain

knowledge in integer programming, combinatorial optimization, and optimization in graphs
insight into classical optimization problems in transportation and communications and problem complexity
knowledge in solving large-scale problems by integer programming, heuristics, and relaxation and bounding techniques
skills in developing and implementing optimization models and algorithms

3 of 34

2024 Course Evaluation

Only 6 out of 14 answered

Overall course evaluation was quite good

The link to the full evaluation document

3

4 of 34

Course Information

4

Organization

Lectures: The theoretical foundation. Self-studies time is significant!
Computer programming assignments: Practical skills in implementing optimization algorithms

Course staff

Examiner and lecturer: Tatiana Polishchuk
Lab sessions and take-home assignments: Anastasia Lemetti

Please see the course information document for more details

5 of 34

Course Information (cont’d)

5

Prerequisites

Basic knowledge in graph optimization problems and linear and integer linear programming
Basics of data structure and algorithms
Knowledge in computer programming

6 of 34

Course Information (cont’d)

6

Material

Lecture slides and instructions for the assignments: course webpage
3 main information sources for Self Studies:

MIT open courseware lectures, textbook, + good YT videos

It is strongly recommended that you study and prepare for the lab assignments before the scheduled sessions

Reference literature

Textbook: I ntroduction to Algorithms, Third Edition, by Cormen, Leiserson, Rivest, and Stein.
J. Lundgren, M. Rönnqvist, P. Värbrand (2010), Optimization, Studentlitteratur.
R. L. Rardin (1998), Optimization in Operations Research, Prentice Hall.
C. R. Reeves (ed.) (1993), Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford.

7 of 34

Course Information (cont’d)

7

Examination and grading

Computer programming assignments (labs) (3 hp)

Five lab assignments
For each assignment, it is required to show the program code, the parameter specification, and an example output result from the program code
The overall grade of the assignments is pass/fail

Individual final take-home assignments (3hp): solve 5 out of 6 suggested optimization problems

alternatively: individual research projects on real research topics in optimization (go deeper into one topic, write a survey, understand example problem or implement a new algorithm) (3hp)

8 of 34

Course Content

8

Graph algorithms (repetition)
Linear programming (repetition)
Integer linear programming
Construction (greedy) heuristics
Metaheuristics
Problem complexity
Bounding and relaxation techniques
Mathematical modeling

9 of 34

Problem Solving by Applied Optimization: A Framework

Applied Optimization

This course

Real-world Optimization Problem

System Modeling

Modeling

(Simple) Heuristics

Implementation

Solution-tool

Software with GUI

Numerical Solution

Simulation

Optimization

Mathematical Modeling

Modeling

Practitioner

Pure Mathematics

Computer Science

Optimization Theory

Acknowledgment: The figure by Nikolaos Pappas, is inspired by a presentation of Prof. Arie Koster, University of Aarchen, Germany

Mathematical Theory

Solver-based Methods Problem-specific Methods Advanced Heuristics

9

10 of 34

Applied Mathematical Optimization: Key Components

System Modeling
Assumptions
Decision variables
Objectives
Requirements/constraints

Mathematical Modeling

Method Development
Pre-processing
General solver
Problem-specific methods
Parameter tuning

Evaluation
Implementation
Experiments
Result analysis
Performance assessment

The World is complex

→ No unique definition of “the problem”

→ Breakdown of planning tasks in system modeling

f(x)

10

max min

s. t.

x ∈ X

11 of 34

Model Classification

11

The objective and constraint functions are linear → linear models

Continuous variables: Linear programming (LP)
Discrete (integer) variables: Integer linear programming (ILP) or Mixed integer linear programming (MIP)

Non-linear objective function or constraints → Non-linear models (NLP)

Continuous NLP or discrete NLP

A problem is convex if

Convex (concave) objective function for minimization (maximization), and
X is a convex set

otherwise it is non-convex

Convex ~ easy; non-convex ~ hard to solve

LP is convex
ILP and MIP are non-convex in general
Continuous NLP can be convex or non-convex, depending on structure
Discrete NLP is non-convex in general

12 of 34

Combinatorial Optimization

12

In combinatorial optimization, the solution space is a discrete set
A topic in the intersection of applied mathematics and computer science

A combinatorial optimization problem typically has an underlying structure (e.g., a graph)
Many applications in communication and transport systems

13 of 34

Examples of Combinatorial Optimization Problems

13

t

The Shortest Path problem

A graph where each link has a length/cost
Find a path of minimum length/cost from s to t
All possible paths from s to t form a discrete set

s

i

j

^ci j

14 of 34

Examples of Combinatorial Optimization Problems (cont’d)

14

Minimum spanning tree (MST)

Select edges to connect the nodes of a graph with minimum total cost

→ Optimum is a spanning tree

The set of possible spanning trees is discrete

3

5

1

4

9

7

6

4

8

2

5

3

6

7

15 of 34

Examples of Combinatorial Optimization Problems (cont’d)

15

Traveling salesman problem (TSP)

Given a graph, find a tour visiting each node exactly once, such that the total length/cost is minimized
The set of feasible tours is discrete

16 of 34

Examples of Combinatorial Optimization Problems (cont’d)

16

Vehicle Routing Problem (VRP)

A graph having one depot node
Customers/nodes, each having a demand to be delivered
A fleet of vehicles, each having a capacity limit, supplies the customers
Every vehicle starts at the depot
Construct the routes, minimizing the total cost (e.g., distance)
The set of possible routes is discrete

Depot

What’s does VRP relate to TSP?

17 of 34

Minimum Cost Set Covering

Examples of Combinatorial Optimization Problems (cont’d)

17

A set of customers/demand points
A set of candidate service centers
Each service center has an installation cost, and can serve a subset of the demand points (has a capacity)
Find (and install) a subset of service centers at minimum total cost, so that all demand points are covered
The set of all feasible installation patterns is discrete

18 of 34

Examples of Combinatorial Optimization Problems (cont’d)

Vertex coloring

Assign a color to each vertex (node); two adjacent vertices must use different colors
Minimize the total number of colors
The set of feasible coloring solutions is discrete

18

19 of 34

Examples of Combinatorial Optimization Problems (cont’d)

19

Knapsack problem

A set of item types, each with a value and weight
A knapsack with a capacity limit on the total weight
Select item types and numbers such that

The total value is maximized
The total weight does not exceed the limit

A special case is the binary knapsack problem (0/1 choice)
The set of possible selections is a discrete

$25 5 kg

$24 3 kg

$10 1 kg

$12 2 kg

$11

2.5 kg

$30 4 kg

20 of 34

How to approach the problem?

20

Size

10

15

20

25

. . .

100

MST

0.01 second

2.25 days 831 years

450 trillion years

. . .

TSP

0.36 millisecond

2.17 minutes

7.7 years 49 million years

. . .

Knapsack

0.1 microsecond

3.27 microsecond

0.1 millisecond

3.35 millisecond

. . .

4 million years

Brute force works fine for small instances
For large cases, we need something better (faster CPU can hardly help)

What about the Brute Force?

A finite number of possible solutions

→ Exhaustive search gives the optimum

Assume that we can test a solution in 10^-10second (one CPU cycle at 10 GHz)

MST: nⁿ^—²possible trees for a complete graph of n nodes
TSP: n! possible tours for a complete graph of n nodes
Binary knapsack: 2ⁿpotential solutions (some infeasible) for n items

21 of 34

Mathematical Modeling

Representation of decision-making problems by optimization models
Identification and definition of

Decision variables
Objective function
Constraints

21

Shortest Path
Variables: Link selection
Objective: Total length
Constraint: The links selected must form a path

Graph coloring
Variables: Color assignment
Objective: Total number of colors
Constraint: Two adjacent nodes are assigned different colors

Combinatorial optimization problems: Typically ILP/MIP
There are often several valid ILPs/MIPs for a comb. opt. problem

22 of 34

Optimization and Mathematical Programming

22

23 of 34

23

Example: Modeling Shortest Path with the Flow

24 of 34

Example: Modeling Shortest Path (cont’d)

24

25 of 34

25

Example: Modeling Graph Coloring

26 of 34

24

Example: Modeling Graph Coloring (cont’d)

27 of 34

a set of rules to be followed in calculations or other problem-solving operations

or simply:

a sequence of steps needed to solve a problem

What is algorithm? (watch video 5 min)

27

Implementation: What is an Algorithm?

Last time we spoke about scripts, and you tried to write your own first programs at labs. But before writing any program, it is useful to think about the steps that will be necessary to perform.

You’ve learned that you program will have at least an input and an output. What else should be planned there inbetween?

Pseudocode is a programming tool that helps programmer design the problem before writing the program in a programming language. It is a detailed and easily understandable description of steps of algorithms or a program, which does not use any programming concepts, rather uses natural language. Program designer uses pseudocode as a programming tool to express and explain the design in depth which helps programmers understand the needs and converts that design into an actual program by writing codes in some programming language. Since it’s not a programming language; it cannot be compiled or executed. Unlike programming languages, there is no specific statements and syntax for writing Pseudo code.

�

28 of 34

28

Input

Output

Calculations

Algorithm

29 of 34

Sequential:

Input radius r
Calculate the area A
Display the output

29

Algorithm: Example v.0

30 of 34

30

Algorithm: Structure

31 of 34

Conditional:

Input radius r

if (r >=0)

calculate A

output A

else

output Error

31

ATTN:

r>=0!

Algorithm: Example v.1

32 of 34

Is our algorithm efficient?

Measured using runtime = time to get the solution

Depends on the input size

Linear time (polynomial, P problems) algorithms are efficient

Several other complexity classes = not polynomially solvable

NP problems: check the correctness of the given solution in polynomial time

Solving problem in general is harder than checking the correctness (P vs. NP)

NP-complete problems: the hardest among NP problems, no efficient solutions

NP-hard problems: are not possible to solve in polynomial time (running time depends non-linearly from the input size, e.g. can grow exponentially)

32

Algorithm: Complexity

33 of 34

Time complexity:

The running times of operations on the data structure should be as small as possible

Space complexity:

The data structure should use as little memory as possible

Correctness:

The algorithm should correctly implement its model and output correct results

What does it mean that “the algorithm does work?”

33

Algorithm: characteristics

34 of 34

Solving Comb. Opt. Problems: What Options Do We Have?

34

Problem complexity: Easy and difficult problems
Easy problems: Optimum by fast/efficient algorithms
Difficult problems

Integer programming methods

Modeling
Linear programming relaxation/bounding
Improvement of the LP (cutting plane)
Branch and bound, branch and cut, branch and price
Other relaxation and decomposition methods

Approximation algorithms with performance guarantee (if applicable)
Heuristic algorithms