Mathematical Institute
Search results: 13
Prelims Optimisation is recommended.
In many areas of practical importance linear optimisation problems occur with integrality constraints imposed on some of the variables. In optimal crew scheduling for example, a pilot cannot be fractionally assigned to two different flights at the same time. Likewise, in combinatorial optimisation an element of a given set either belongs to a chosen subset or it does not. Integer programming is the mathematical theory of such problems and of algorithms for their solution. The aim of this course is to provide an introduction to some of the general ideas on which attacks to integer programming problems are based: generating bounds through relaxations by problems that are easier to solve, and branch-and-bound.
Prof. Raphael Hauser
Students will understand some of the theoretical underpinnings that render certain classes of integer programming problems tractable ("easy'' to solve), and they will learn how to solve them algorithmically. Furthermore, they will understand some general mechanisms by which intractable problems can be broken down into tractable subproblems, and how these mechanisms are used to design good heuristics for solving the intractable problems. Understanding these general principles will render the students able to guide the modelling phase of a real-world problem towards a mathematical formulation that has a reasonable chance of being solved in practice.
Course outline. What is integer programming (IP)? Some classical examples.
Further examples, hard and easy problems.
Alternative formulations of IPs, linear programming (LP) and the simplex method.
LP duality, sensitivity analysis.
Optimality conditions for IP, relaxation and duality.
Total unimodularity, network flow problems.
Optimal trees, submodularity, matroids and the greedy algorithm.
Augmenting paths and bipartite matching.
The assignment problem.
Dynamic programming.
Integer knapsack problems.
Branch-and-bound.
More on branch-and-bound.
Lagrangian relaxation and the symmetric travelling salesman problem.
Solving the Lagrangian dual.
Branch-and-cut.
In many areas of practical importance linear optimisation problems occur with integrality constraints imposed on some of the variables. In optimal crew scheduling for example, a pilot cannot be fractionally assigned to two different flights at the same time. Likewise, in combinatorial optimisation an element of a given set either belongs to a chosen subset or it does not. Integer programming is the mathematical theory of such problems and of algorithms for their solution. The aim of this course is to provide an introduction to some of the general ideas on which attacks to integer programming problems are based: generating bounds through relaxations by problems that are easier to solve, and branch-and-bound.
Prof. Raphael Hauser
Students will understand some of the theoretical underpinnings that render certain classes of integer programming problems tractable ("easy'' to solve), and they will learn how to solve them algorithmically. Furthermore, they will understand some general mechanisms by which intractable problems can be broken down into tractable subproblems, and how these mechanisms are used to design good heuristics for solving the intractable problems. Understanding these general principles will render the students able to guide the modelling phase of a real-world problem towards a mathematical formulation that has a reasonable chance of being solved in practice.
- Classical examples of Integer Programming problems (IP): the Assignment Problem, the Knapsack Problem, the Travelling Salesman Problem, the Shortest Path Problem.
- Linear programming (LP) and the simplex method.
- Linear programming duality, sensitivity analysis.
- Total unimodularity and ideal formulations of IPs.
- Submodularity and the Greedy Algorithm. Connections to regularised least squares.
- LP based branch-and-bound for general integer programming problems.
- Delayed column generation and the cutting-stock problem.
- Branch-and-Cut algorithms and the General Assignment Problem.
- Lagrangian relaxation.
- Lagrangian Duality and the Subgradient Algorithm.
In many practical problems that can be approached via linear optimisation problems, some or all of the variables are constrained to take binary or integer values. For example, in optimal crew scheduling a pilot cannot be fractionally assigned to two different flights at the same time. Likewise, in combinatorial optimisation an element of a given set either belongs to a chosen subset or it does not. Integer programming is the mathematical theory of such problems and of algorithms for their solution. The aim of this course is to provide an introduction to some of the general ideas on which attacks to integer programming problems are based: generating bounds through relaxations by problems that are easier to solve, and branch-and-bound.
Prof. Raphael Hauser
Students will understand some of the theoretical underpinnings that render certain classes of integer programming problems tractable ("easy'' to solve), and they will learn how to solve them algorithmically. Furthermore, they will understand some general mechanisms by which intractable problems can be broken down into tractable subproblems, and how these mechanisms are used to design good heuristics for solving the intractable problems. Understanding these general principles will enable the students to guide the modelling phase of a real-world problem towards a mathematical formulation that has a reasonable chance of being solved in practice.
Week 1:
- Classical examples of Integer Programming problems (IP), modelling and basic terminology.
- Linear programming I: the simplex method.
Week 2:
- Linear programming II: Duality Theory.
- Total unimodularity I: Ideal formulations of IPs and totally unimodular matrices.
Week 3:
- Total Unimodularity II: Exact theoretical characterisation, practical sufficient criteria, bipartite matching, the shortest path problem.
- Submodularity I: Submodular functions and submodular optimisation problems.
Week 4:
- Submodularity II: Submodular rank functions, matroids, the greedy algorithm and the maximum weight independent set problem.
- Branch-and-Bound I: LP based branch-and-bound for general integer programming problems.
Week 5:
- Branch-and-bound II: general B&B, pre-processing, warm starting of LPs, dual simplex method.
- Dantzig-Wolfe decomposition, delayed column generation.
Week 6:
- Branch-and-Price, application to the cutting stock problem.
- Preprocessing of LPs and IPs, generating valid cuts, cutting plane algorithm.
Week 7:
- Chvatal cuts, Gomoroy cuts, branch-and-cut algorithm.
- The Generalised Assignment Problem.
Week 8:
- Lagrangian relaxation and Lagrangian duality.
- The subgradient algorithm.
In many practical problems that can be approached via linear optimisation problems, some or all of the variables are constrained to take binary or integer values. For example, in optimal crew scheduling a pilot cannot be fractionally assigned to two different flights at the same time. Likewise, in combinatorial optimisation an element of a given set either belongs to a chosen subset or it does not. Integer programming is the mathematical theory of such problems and of algorithms for their solution. The aim of this course is to provide an introduction to some of the general ideas on which attacks to integer programming problems are based: generating bounds through relaxations by problems that are easier to solve, and branch-and-bound.
Prof. Raphael Hauser
Students will understand some of the theoretical underpinnings that render certain classes of integer programming problems tractable ("easy'' to solve), and they will learn how to solve them algorithmically. Furthermore, they will understand some general mechanisms by which intractable problems can be broken down into tractable subproblems, and how these mechanisms are used to design good heuristics for solving the intractable problems. Understanding these general principles will enable the students to guide the modelling phase of a real-world problem towards a mathematical formulation that has a reasonable chance of being solved in practice.
Week 1:
- Classical examples of Integer Programming problems (IP), modelling and basic terminology.
- Linear programming I: the simplex method.
Week 2:
- Linear programming II: Duality Theory.
- Total unimodularity I: Ideal formulations of IPs and totally unimodular matrices.
Week 3:
- Total Unimodularity II: Exact theoretical characterisation, practical sufficient criteria, bipartite matching, the shortest path problem.
- Submodularity I: Submodular functions and submodular optimisation problems.
Week 4:
- Submodularity II: Submodular rank functions, matroids, the greedy algorithm and the maximum weight independent set problem.
- Branch-and-Bound I: LP based branch-and-bound for general integer programming problems.
Week 5:
- Branch-and-bound II: general B&B, pre-processing, warm starting of LPs, dual simplex method.
- Dantzig-Wolfe decomposition, delayed column generation.
Week 6:
- Branch-and-Price, application to the cutting stock problem.
- Preprocessing of LPs and IPs, generating valid cuts, cutting plane algorithm.
Week 7:
- Chvatal cuts, Gomoroy cuts, branch-and-cut algorithm.
- The Generalised Assignment Problem.
Week 8:
- Lagrangian relaxation and Lagrangian duality.
- The subgradient algorithm.
- Lecturer: Raphael Hauser
Classical examples of Integer Programming problems (IP), modelling and basic terminology.
Linear programming I: the simplex method.
Week 2:
Linear programming II: Duality Theory.
Total unimodularity I: Ideal formulations of IPs and totally unimodular matrices.
Week 3:
Total Unimodularity II: Exact theoretical characterisation, practical sufficient criteria, bipartite matching, the shortest path problem.
Submodularity I: Submodular functions and submodular optimisation problems.
Week 4:
Submodularity II: Submodular rank functions, matroids, the greedy algorithm and the maximum weight independent set problem.
Branch-and-Bound I: LP based branch-and-bound for general integer programming problems.
Week 5:
Branch-and-bound II: general B&B, pre-processing, warm starting of LPs, dual simplex method.
Dantzig-Wolfe decomposition, delayed column generation.
Week 6:
Branch-and-Price, application to the cutting stock problem.
Preprocessing of LPs and IPs, generating valid cuts, cutting plane algorithm.
Week 7:
Chvatal cuts, Gomoroy cuts, branch-and-cut algorithm.
The Generalised Assignment Problem.
Week 8:
Lagrangian relaxation and Lagrangian duality.
The subgradient algorithm.
- Lecturer: Raphael Hauser
Classical examples of Integer Programming problems (IP), modelling and basic terminology.
Linear programming I: the simplex method.
Week 2:
Linear programming II: Duality Theory.
Total unimodularity I: Ideal formulations of IPs and totally unimodular matrices.
Week 3:
Total Unimodularity II: Exact theoretical characterisation, practical sufficient criteria, bipartite matching, the shortest path problem.
Submodularity I: Submodular functions and submodular optimisation problems.
Week 4:
Submodularity II: Submodular rank functions, matroids, the greedy algorithm and the maximum weight independent set problem.
Branch-and-Bound I: LP based branch-and-bound for general integer programming problems.
Week 5:
Branch-and-bound II: general B&B, pre-processing, warm starting of LPs, dual simplex method.
Dantzig-Wolfe decomposition, delayed column generation.
Week 6:
Branch-and-Price, application to the cutting stock problem.
Preprocessing of LPs and IPs, generating valid cuts, cutting plane algorithm.
Week 7:
Chvatal cuts, Gomoroy cuts, branch-and-cut algorithm.
The Generalised Assignment Problem.
Week 8:
Lagrangian relaxation and Lagrangian duality.
The subgradient algorithm.
- Lecturer: Raphael Hauser
Classical examples of Integer Programming problems (IP), modelling and basic terminology.
Linear programming I: the simplex method.
Week 2:
Linear programming II: Duality Theory.
Total unimodularity I: Ideal formulations of IPs and totally unimodular matrices.
Week 3:
Total Unimodularity II: Exact theoretical characterisation, practical sufficient criteria, bipartite matching, the shortest path problem.
Submodularity I: Submodular functions and submodular optimisation problems.
Week 4:
Submodularity II: Submodular rank functions, matroids, the greedy algorithm and the maximum weight independent set problem.
Branch-and-Bound I: LP based branch-and-bound for general integer programming problems.
Week 5:
Branch-and-bound II: general B&B, pre-processing, warm starting of LPs, dual simplex method.
Dantzig-Wolfe decomposition, delayed column generation.
Week 6:
Branch-and-Price, application to the cutting stock problem.
Preprocessing of LPs and IPs, generating valid cuts, cutting plane algorithm.
Week 7:
Chvatal cuts, Gomoroy cuts, branch-and-cut algorithm.
The Generalised Assignment Problem.
Week 8:
Lagrangian relaxation and Lagrangian duality.
The subgradient algorithm.