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
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