Computers Architecture, Systems, and Networks Optimization (CANO)



Course Description

The course is a comprehensive introduction to the theory and algorithms of integer optimization. It is organized in four parts: mathematical programming, heuristic algorithms, network flows, and computers architecture, systems, and networks problems.


Goals

The goals of the course are the following:

  • To present students with a knowledge of the state-of-the art in the theory and practice of computers architecture, systems, and networks applied integer optimization,
  • To provide students with a rigorous analysis of heuristic algorithms,
  • To help each student develop his or her own intuition about ILP modeling and algorithm development and analysis.


    • Topics

    1. Mathematical Programming:

    This introductive part presents the mathematical programming basics and discusses how to formulate integer optimization problems, the duality of integer optimization and how to solve the resulting relaxations both practically and theoretically.
    Contents:
  • Linear Programming (LP) basics.
  • Integer programming (ILP).
  • Network flow models.
  • Non-linear programming.
  • Modeling and solving software: OPL/CPLEX (Lab sessions).

    2. Network flows:

    Network flow problems form a subclass of linear programming problems with applications to transportation, logistics, manufacturing, computer science, project management, finance as well as a number of other domains. This part surveys some of the applications of network flows and focus on key special cases of network flow problems.
    Contents:
  • Introduction to Graph Theory.
  • General Network Flows problems.
  • Network Flows problems in computers architecture and networks.

    3. Heuristics methods:

    The last two decades have witnessed a tremendous growth in the area of heuristic algorithms. Two benefits of heuristics have spearheaded this growth: simplicity and speed. This part presents the basic concepts of heuristic algorithms and some advanced meta-heuristics. Finally, a discussion about the application of heuristics to solve integer optimization problems is presented.
    Contents:
  • Constructive procedures.
  • Local search.
  • Meta-heuristics: GRASP, Simulated Annealing, Tabu Search, Genetic algorithms, Ant colony, Path Relinking, etc.

    4. Applications

    This part concludes the course centering the previously learned concepts into computers architecture, systems, and networks problems. Research level problems are presented and ILP modeling and algorithms to solve it are analyzed.


    • Organization and Grading

    Collaboration is encouraged on all aspects of the class. Groups of two may collaborate and hand in a single applied project. Each project consists on define a problem drawn from your own research area, design an ILP model, and design and implement some heuristic algorithm to solve the problem. Students should compare results obtained with both methods.
    The grading for the subject will be determined using the following weights, part assignments: 30%, applied project: 70%.


    Textbooks

    Basic Books

  • Hillier F.S., Lieberman G.J. Introduction to operations research. McGraw-Hill, 2005.
  • Ahuja, Magnanti, and Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.
  • Glover, F.; Kochenberger, G.A. Handbook of metaheuristics. Kluwer Academic Publishers, 2003.
  • Medhi, D; Ramasamy, K, Network Routing: Algorithms, Protocols, and Architectures. Elsevier Morgan Kaufmann, 2007

    Additional Books

  • Williams, H. P. Model building in mathematical programming. John Wiley & Sons, 1993.
  • Winston, Wayne L. Operations research: applications and algorithms. PWS-KENT, 2004.
  • Luenberger, D.G. Linear and nonlinear programming. Kluwer Academic Publishers, 2004.
  • Michalewicz, Z.; Fogel, D.B. How to solve it modern heuristics. Springer, 1999.


    • Lecturer

    Luis Velasco