CIRIACO D'AMBROSIO | OPTIMIZATION ALGORITHMS
CIRIACO D'AMBROSIO OPTIMIZATION ALGORITHMS
cod. 0622600026
OPTIMIZATION ALGORITHMS
| 0622600026 | |
| DIPARTIMENTO DI INGEGNERIA INDUSTRIALE | |
| EQF7 | |
| MANAGEMENT ENGINEERING | |
| 2021/2022 |
| YEAR OF COURSE 2 | |
| YEAR OF DIDACTIC SYSTEM 2018 | |
| AUTUMN SEMESTER |
| SSD | CFU | HOURS | ACTIVITY | |
|---|---|---|---|---|
| MAT/09 | 6 | 60 | LESSONS |
| Objectives | |
|---|---|
| THE OPTIMIZATION COURSE AIMS TO INCREASE THE KNOWLEDGE CONCERNING THE RESOLUTION OF CONTINUOUS LINEAR PROGRAMMING (LP) PROBLEMS, INTRODUCED IN THE OPERATIONS RESEARCH COURSE, AND TO PRESENT THE FORMULATION TECHNIQUES, THROUGH THE INTEGER LINEAR PROGRAMMING MODELS (ILP), AND THE ALGORITHMS FOR INTEGER-VARIABLE OPTIMIZATION PROBLEMS. DURING THE COURSE, VARIOUS CLASSES OF OPTIMIZATION PROBLEMS ARE PRESENTED. KNOWLEDGE AND UNDERSTANDING AT THE END OF THE COURSE, THE STUDENT WILL KNOW: - ALTERNATIVE ALGORITHMS TO THE SIMPLEX METHOD FOR SOLVING LARGE-SCALE LP PROBLEMS; - THE BASIC CONCEPTS OF COMPLEXITY THEORY, NECESSARY TO IDENTIFY THE COMPLEXITY OF OPTIMIZATION PROBLEMS; - THE MAIN ASPECTS OF MATHEMATICAL MODELING OF INTEGER-VARIABLE OPTIMIZATION PROBLEMS AND THE TECHNIQUES TO EVALUATE THE EFFECTIVENESS OF THE PROPOSED MATHEMATICAL MODELS; - THE MAIN SOLUTION ALGORITHMS OF BOTH EXACT AND HEURISTIC/METAHEURISTIC TYPES FOR SOLVING ILP PROBLEMS. APPLYING KNOWLEDGE AND UNDERSTANDING AT THE END OF THE COURSE, THE STUDENT WILL BE ABLE TO: - FORMULATE OPTIMIZATION PROBLEMS THROUGH MATHEMATICAL MODELS WITH CONTINUOUS OR INTEGER VARIABLES ACCORDING TO REQUIREMENTS; - APPLY ALGORITHMS FOR SOLVING LARGE-SCALE LP PROBLEMS; - RECOGNIZE THE COMPUTATIONAL COMPLEXITY INHERENT IN THE OPTIMIZATION PROBLEM FACED AND, BASED ON IT, BE ABLE TO IDENTIFY THE MOST EFFECTIVE ALGORITHMS TO BE USED TO SOLVE THE PROBLEM; - DESIGN EXACT ALGORITHMS FOR SOLVING ILP PROBLEMS. - DESIGN HEURISTIC AND/OR METAHEURISTIC ALGORITHMS FOR SOLVING ILP PROBLEMS. |
| Prerequisites | |
|---|---|
| THE OPERATIONS RESEARCH COURSE IS OFFICIALLY REQUIRED TO ATTEND THIS COURSE. |
| Contents | |
|---|---|
| 1. LINEAR PROGRAMMING (PL) (LECTURES 8 HOURS; EXERCISE 4H) - 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 4H) - DUAL-SIMPLEX METHOD; - PRIMAL-DUAL ALGORITHM; - DELAYED COLUMN GENERATION ALGORITHM. 3. INTEGER LINEAR PROGRAMMING (PLI) (LECTURES 12 HOURS; EXERCISE 4H) - 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 8 HOURS; EXERCISE 4H) - BRANCH AND BOUND; - CUTTING PLANE; - BRANCH AND CUT. 5 HEURISTIC APPROACHES (LECTURES 8 HOURS; EXERCISE 2H) - LOCAL SEARCH; - GREEDY ALGORITHM; - TABU SEARCH; - SIMULATED ANNEALING; - GENETIC ALGORITHM. |
| Teaching Methods | |
|---|---|
| THE COURSE IS ORGANIZED IN 60 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 | |
|---|---|
| - 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/025487/HOME |
BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2022-11-21]
