### Linear & Integer Linear Programming (2017)

Welcome to Linear & Integer Linear Programming

Description: The course will consist of two parts. Part 1 will address linear programming (LP) (also called linear optimization) which is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (mathematical optimization). Whereas linear programming is solvable in polynomial time the exponential Simplex algorithm is the most widely used algorithm for solving LP problems. This part will illustrate how several problems may be formulated and solved using LP.

The second part considers integer programming problems being optimization problems, where some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. In contrast to (ordinary) linear programming, which is solvable in polynomial time, ILP is NP-hard.  However, there are several problems which may be naturally formulated as ILP, e.g. task-graph scheduling, travelling sales-person problem, worst-case execution time analysis of code. This part will provide heuristics for how to solve ILP efficiently for several practical instances.

Prerequisites: Understanding of basic complexity theory, manipulation of matrices and basic linear algebra.

Learning objectives: To be able to formulate and solve optimization problems using LP and ILP

Organizer and lecturers: Krishna-Murthy Subramani, email: sub@cs.aau.dk

ECTS: 2

Time: May 8th, 9th, 11th, 15th, 17th and 19th. Each time from 10:00-12:00 in the room 0.2.90

Place: AAU, Selma Lagerlöfsvej 300

Zip code: 9220

City: Aalborg

Number of seats: 20