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 l****ecturers: **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

**Deadline: **24. April 2017

**Important information concerning PhD courses**** **We have over some time experienced problems with no-show for both project and general courses. It has now reached a point where we are forced to take action. Therefore, the Doctoral School has decided to introduce a no-show fee of DKK 5,000 for each course where the student does not show up. Cancellations are accepted no later than 2 weeks before start of the course. Registered illness is of course an acceptable reason for not showing up on those days. Furthermore, all courses open for registration approximately three months before start. This can hopefully also provide new students a chance to register for courses during the year. We look forward to your registrations.

- Teacher: Jiri Srba