2. Professors
  3. Teaching

OPTIMIZATION METHODS

Francesco CARRABS OPTIMIZATION METHODS

0522500054
COMPUTER SCIENCE
EQF7
COMPUTER SCIENCE
2024/2025



YEAR OF DIDACTIC SYSTEM 2016
SPRING SEMESTER
CFUHOURSACTIVITY
648LESSONS
RAFFAELE CERULLI T Curriculum
FRANCESCO CARRABS Curriculum
Objectives
THE OPTIMIZATION METHODS COURSE AIMS TO PROVIDE THE KNOWLEDGE FOR SOLVING CONTINUOUS LINEAR PROGRAMMING (LP) PROBLEMS WITH A VERY LARGE NUMBER OF DECISION VARIABLES. FURTHERMORE, IT INTRODUCES TECHNIQUES FOR FORMULATING REAL PROBLEMS WITH LINEAR INTEGER PROGRAMMING (ILP) MODELS AND PRESENTS THE MAIN EXACT AND HEURISTIC ALGORITHMS FOR SOLVING PLI PROBLEMS. DURING THE COURSE, DIFFERENT CLASSES OF OPTIMIZATION PROBLEMS WILL BE DESCRIBED, WITH PARTICULAR ATTENTION TO THOSE OF GREATEST APPLICATIVE INTEREST.
KNOWLEDGE AND UNDERSTANDING
AT THE END OF THE COURSE THE STUDENT WILL KNOW:
- ALGORITHMS, THAT ARE ALTERNATIVES TO THE SIMPLEX METHOD, FOR SOLVING LP PROBLEMS WITH A VERY LARGE NUMBER OF DECISION VARIABLES;
- THE BASIC CONCEPTS OF COMPLEXITY THEORY THAT ARE NECESSARY TO IDENTIFY THE COMPLEXITY OF THE OPTIMIZATION PROBLEMS ADDRESSED;
- THE MAIN FOUNDATIONS OF MATHEMATICAL MODELING OF THE OPTIMIZATION PROBLEMS WITH INTEGER DECISION VARIABLES AND THE TECHNIQUES FOR EVALUATING THE EFFECTIVENESS OF THE PROPOSED MATHEMATICAL MODELS;
- THE MAIN ALGORITHMS, BOTH EXACT AND HEURISTIC/METAHEURISTIC, FOR SOLVING ILP PROBLEMS.

APPLYING KNOWLEDGE AND UNDERSTANDING
AT THE END OF THE COURSE THE STUDENT WILL BE ABLE TO:
- FORMULATE OPTIMIZATION PROBLEMS USING MATHEMATICAL MODELS WITH CONTINUOUS, INTEGER OR MIXED DECISION VARIABLES;
- APPLY THE CONCEPTS OF COMPLEXITY THEORY, PRESENTED DURING THE COURSE, TO EVALUATE THE POSSIBLE INTRACTABILITY OF AN OPTIMIZATION PROBLEM;
- DEVELOP AND APPLY ALGORITHMS FOR SOLVING LP PROBLEMS WITH MANY DECISION VARIABLES;
- DEVELOP AND APPLY EXACT ALGORITHMS FOR SOLVING ILP PROBLEMS;
- DEVELOP AND APPLY HEURISTIC AND/OR METAHEURISTIC ALGORITHMS FOR SOLVING ILP PROBLEMS.
MAKING JUDGMENTS
AT THE END OF THE COURSE THE STUDENT WILL BE ABLE TO:
- INDEPENDENTLY AND EFFECTIVELY RECOGNIZE THE MOST SUITABLE MODELS AND OPTIMIZATION METHODS FOR SOLVING THE PROBLEM ADDRESSED, EVEN IN THE PRESENCE OF MANY DECISION VARIABLES, AND TO CORRECTLY UNDERSTAND THE MEANING OF THE RESULTS;
- RECOGNIZE THE INTRINSIC COMPUTATIONAL COMPLEXITY OF THE OPTIMIZATION PROBLEM ADDRESSED AND, BASED ON IT, BE ABLE TO IDENTIFY THE MOST EFFECTIVE ALGORITHMS TO USE TO SOLVE THE PROBLEM.

COMMUNICATION SKILLS
AT THE END OF THE COURSE THE STUDENT WILL HAVE ACQUIRED ADEQUATE SKILLS IN ANALYZING AN OPTIMIZATION PROBLEM AND ITS POSSIBLE SOLUTION SCENARIOS USING AN ADEQUATE NOTATION AND AN APPROPRIATE LANGUAGE THAT HIGHLIGHTS THE SKILLS OF THE METHODOLOGIES ACQUIRED. MOREOVER, IT WILL BE ABLE OF TRANSMITTING IN A CLEAR AND CONCISE WAY TO INTERLOCUTORS, BOTH SPECIALISTS AND NON-SPECIALISTS, THE CONCEPTS NECESSARY FOR UNDERSTANDING THE MODELS AND ALGORITHMS DEVELOPED. FINALLY, HE WILL BE ABLE TO DISCUSS ISSUES CONCERNING THE RESOLUTION OF OPTIMIZATION PROBLEMS WITH OTHER INTERLOCUTORS.

LEARNING SKILLS
THE STUDENT WILL BE ABLE TO:
- APPLY THE KNOWLEDGE ACQUIRED TO CONTEXTS DIFFERENT FROM THOSE PRESENTED DURING THE COURSE;
- DELVE DEEPER INTO THE TOPICS COVERED USING TEACHING OR SCIENTIFIC MATERIALS DIFFERENT FROM THE ONES USED DURING THE COURSE;
- LEARN, EVEN INDEPENDENTLY, FURTHER KNOWLEDGE OF APPLIED MATHEMATICS PROBLEMS.
Prerequisites
THE OPERATIONS RESEARCH COURSE IS OFFICIALLY REQUIRED TO ATTEND THIS COURSE.
Contents
1. LINEAR PROGRAMMING (PL) (LECTURES 6 HOURS; EXERCISE 2H)
- RECALLS OF THE MAIN RESULTS OF LINEAR PROGRAMMING;
- PATHOLOGIC CASE OF THE SIMPLEX METHOD: KLEE E MINTY CUBE;
- ELLIPSOID METHOD;
- SIMPLEX TABLEAU.
2. ALTERNATIVE ALGORITHMS TO THE SIMPLEX METHOD (LECTURES 6 HOURS; EXERCISE 2H)
- DUAL-SIMPLEX METHOD;
- PRIMAL-DUAL ALGORITHM;
- DELAYED COLUMN GENERATION ALGORITHM.
3. INTEGER LINEAR PROGRAMMING (PLI) (LECTURES 14 HOURS; EXERCISE 2H)
- COMPLEXITY THEORY: CLASSIFICATION OF THE OPTIMIZATION PROBLEMS ACCORDING TO THEIR DIFFICULTY;
- LOGIC VARIABLES AND CONSTRAINTS; MULTI-OBJECTIVE PROBLEMS;
- CLASSICAL COMBINATORIAL OPTIMIZATION PROBLEMS;
- LAGRANGIAN RELAXATION;
- VALID INEQUALITIES.
4 EXACT APPROACHES (LECTURES 6 HOURS; EXERCISE 2H)
- BRANCH AND BOUND;
- CUTTING PLANE;
- BRANCH AND CUT.
5 HEURISTIC APPROACHES (LECTURES 6 HOURS; EXERCISE 2H)
- LOCAL SEARCH;
- GREEDY ALGORITHM;
- TABU SEARCH;
- SIMULATED ANNEALING;
- GENETIC ALGORITHM.
Teaching Methods
THE COURSE IS ORGANIZED IN 48 HOURS OF FRONTAL LESSONS (6 CFU), USING PROJECTED SLIDES. AT THE END OF EACH TOPIC, SOME EXAMPLES AND CLASSROOM EXERCISES ARE PRESENTED. THE SOLUTION OF THE EXERCISE, WHICH IS CARRIED OUT UNDER THE SUPERVISION OF THE TEACHER, SEEKS TO DEVELOP AND STRENGTHEN THE STUDENT CAPACITY OF IDENTIFYING THE MOST APPROPRIATE TECHNIQUES TO SOLVE IT.
Verification of learning
THE FINAL EXAM IS DESIGNED TO EVALUATE AS A WHOLE: THE KNOWLEDGE AND UNDERSTANDING OF THE CONCEPTS PRESENTED IN THE COURSE, AS WELL AS THE ABILITY TO APPLY SUCH KNOWLEDGE FOR THE RESOLUTION OF OPTIMIZATION PROBLEMS.
THE ORAL EXAMINATION WILL COVER ALL THE TOPICS OF THE COURSE AND ASSESSMENT WILL TAKE INTO ACCOUNT THE KNOWLEDGE DEMONSTRATED BY THE STUDENT CONCERNING BOTH THE THEORETICAL AND APPLICATIVE ASPECTS FOR THE RESOLUTION OF THE OPTIMIZATION PROBLEMS.
THE EVALUATION OF ORAL, EXPRESSED IN THIRTIES, TAKES INTO ACCOUNT THE ABILITY TO DESCRIBE THE OPTIMIZATION ALGORITHMS AND THE OTHER CONCEPTS, PRESENTED IN THE COURSE, IN A CLEAR AND CONCISE MANNER.
THE MINIMUM ASSESSMENT LEVEL (18) IS AWARDED WHEN THE STUDENT SHOWS A FRAGMENTARY KNOWLEDGE OF THEORETICAL CONTENTS AND A LIMITED ABILITY TO FORMULATE OPTIMIZATION PROBLEMS AND TO APPLY ALGORITHMS TO SOLVE THEM.
THE MAXIMUM ASSESSMENT LEVEL (30) IS ATTRIBUTED WHEN THE STUDENT SHOWS A COMPLETE AND IN-DEPTH KNOWLEDGE OF THE COURSE TOPICS AND A REMARKABLE ABILITY TO IDENTIFY THE MOST APPROPRIATE METHODS TO SOLVE THE OPTIMIZATION PROBLEMS FACED.
THE LAUDE IS ATTRIBUTED WHEN THE CANDIDATE SHOWS A SIGNIFICANT MASTERY OF THE THEORETICAL AND OPERATIONAL CONTENTS AND SHOWS THE ABILITY TO PRESENT THE TOPICS WITH REMARKABLE PROPERTIES OF LANGUAGE AND AUTONOMOUS PROCESSING CAPACITY EVEN IN CONTEXTS DIFFERENT FROM THOSE PROPOSED BY THE TEACHER.
Texts
- CHRISTOS H. PAPADIMITRIOU, K. STEIGLITZ: COMBINATORIAL OPTIMIZATION: ALGORITHMS AND COMPLEXITY, 1998;
- M.S. BAZARAA, J.J. JARVIS & H.D. SHERALI, LINEAR PROGRAMMING AND NETWORK FLOWS, FOURTH EDITION, JOHN WILEY, 2010;
- GEORGE L. NEMHAUSER, LAURENCE A. WOLSEY, INTEGER AND COMBINATORIAL OPTIMIZATION, 1999.
- LECTURE NOTES PROVIDED BY THE TEACHER.
OTHER RECOMMENDED BOOK:
LAURENCE A. WOLSEY, INTEGER PROGRAMMING, 1998.
More Information
- EMAIL: RAFFAELE@UNISA.IT, FCARRABS@UNISA.IT
- THE COURSE LANGUAGE IS ITALIAN;
- THE ATTENDANCE OF THE LESSONS IS HIGHLY RECOMMENDED;
- OFFICE HOURS FOR STUDENTS ARE AVAILABLE ON THE WEBPAGE: HTTPS://DOCENTI.UNISA.IT/001227/HOME
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2024-11-18]