| Center |
| Faculty of Mathematics |
| Departament |
| Statistics and Operational Research |
| Lecturers in charge |
| Sin datos cargados |
| Met. Docent |
| Met. Avaluació |
| - - |
| Bibliografia |
| 1.- Garfinkel, R. and Nemhauser, G. : Integer Programming. Wiley Interscience 1972. 2.- Nemhauser, G. and Wolsey, L. : Integer and Combinatorial Optimization. Wiley 1988. 3.- Papadimitriou, C. and Steiglitz, K. : Combinatorial Optimization : Algorithms and Complexity. Prentice Hall 1982. 4.- Schrage, L. : Linear, Integer and Quadratic Programming with LINDO. Scientific Press 1986. 5.- Williams, H. : Model Solving in Mathematical Programming. Wiley 1993. 6.- Wolsey, L. : Integer programming. Wiley Interscience 1998. 7.- Cunningham, K. and Schrage, L. : Manual del Lingo. LINDO Systems Inc. 1990. 8.- Williams, H. : Model Building in Mathematical Programming. Wiley 1990. |
| Continguts |
| Objectives Present the basic content of ILP (Integral Lineal Programming), theory and algorithms, focusing on practical applications. In this way the student should be able to formulate and resolve problems, using the computer and commercial ILP packs, but at the same time gain good understanding of the theoretical bases on which the resolution algorithms are based. Theory Program TOPIC 1: The problem of Integral Lineal Programming (ILP). Need for restrictions of integrity. Modelling. Examples. TOPIC 2: Structural problems and related models : (i) Problem of the Rucksack, Assignation Generalised, Covering, Packing and Patitioning; (ii) Problem of Localisation of the Travelling Salesman. TOPIC 3: Reinforcing a formulation : adjusting the boundaries, addition of the logical inequalities, variables fixed to a value, elimination of redundant restrictions. TOPIC 4: "Branch and Bound" Methods. Rules of branching and bounds. Problems in variables 0-1. Mixed Problems. TOPIC 5: Lagrangian Relaxation. Application to the Problem of Generalised Assignment. TOPIC 6: Methods of Cutting Plans. GomoryĆs cuts for integral pure and mixed problems. Valid Disequalities. TOPIC 7: Heuristic Algorithms. Practical Program 1.- Introduction to modelling language LINGO. Model Formulation and solving. 2.- Problem formulation and solving in ILP. 3.- Introduction to TRAVEL (heuristic algorithms and exacts for the Travelling Salesman problem). |