Branch-and-cut solution approach for multilevel mixed integer linear programming problems
A multilevel programming problem is an optimization problem that involves multiple decision makers, whose decisions are made in a sequential (or hierarchical) order. If all objective functions and constraints are linear and some decision variables in any level are restricted to take on integral or d...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier
2023-01-01
|
| Series: | EURO Journal on Computational Optimization |
| Subjects: | |
| Online Access: | http://www.sciencedirect.com/science/article/pii/S2192440623000205 |
| _version_ | 1827582749993598976 |
|---|---|
| author | Ashenafi Awraris Berhanu Guta Wordofa Semu Mitiku Kassa |
| author_facet | Ashenafi Awraris Berhanu Guta Wordofa Semu Mitiku Kassa |
| author_sort | Ashenafi Awraris |
| collection | DOAJ |
| description | A multilevel programming problem is an optimization problem that involves multiple decision makers, whose decisions are made in a sequential (or hierarchical) order. If all objective functions and constraints are linear and some decision variables in any level are restricted to take on integral or discrete values, then the problem is called a multilevel mixed integer linear programming problem (ML-MILP). Such problems are known to have disconnected feasible regions (called inducible regions), making the task of constructing an optimal solution challenging. Therefore, existing solution approaches are limited to some strict assumptions in the model formulations and lack universality. This paper presents a branch-and-cut (B&C) algorithm for the global solution of such problems with any finite number of hierarchical levels, and containing both continuous and discrete variables at each level of the decision-making hierarchy. Finite convergence of the proposed algorithm to a global solution is established. Numerical examples are used to illustrate the detailed procedure and to demonstrate the performance of the algorithm. Additionally, the computational performance of the proposed method is studied by comparing it with existing method through some selected numerical examples. |
| first_indexed | 2024-03-08T22:57:08Z |
| format | Article |
| id | doaj.art-04cb72bb5662412eb250a9b29675c625 |
| institution | Directory Open Access Journal |
| issn | 2192-4406 |
| language | English |
| last_indexed | 2024-03-08T22:57:08Z |
| publishDate | 2023-01-01 |
| publisher | Elsevier |
| record_format | Article |
| series | EURO Journal on Computational Optimization |
| spelling | doaj.art-04cb72bb5662412eb250a9b29675c6252023-12-16T06:07:02ZengElsevierEURO Journal on Computational Optimization2192-44062023-01-0111100076Branch-and-cut solution approach for multilevel mixed integer linear programming problemsAshenafi Awraris0Berhanu Guta Wordofa1Semu Mitiku Kassa2Addis Ababa University, Department of Mathematics, Addis Ababa, P.O. Box 1176, Addis Ababa, EthiopiaAddis Ababa University, Department of Mathematics, Addis Ababa, P.O. Box 1176, Addis Ababa, EthiopiaBotswana International University of Science & Technology, Department of Mathematics and Statistical Sciences, Palapye, Private Bag 16, Central, Botswana; Corresponding author.A multilevel programming problem is an optimization problem that involves multiple decision makers, whose decisions are made in a sequential (or hierarchical) order. If all objective functions and constraints are linear and some decision variables in any level are restricted to take on integral or discrete values, then the problem is called a multilevel mixed integer linear programming problem (ML-MILP). Such problems are known to have disconnected feasible regions (called inducible regions), making the task of constructing an optimal solution challenging. Therefore, existing solution approaches are limited to some strict assumptions in the model formulations and lack universality. This paper presents a branch-and-cut (B&C) algorithm for the global solution of such problems with any finite number of hierarchical levels, and containing both continuous and discrete variables at each level of the decision-making hierarchy. Finite convergence of the proposed algorithm to a global solution is established. Numerical examples are used to illustrate the detailed procedure and to demonstrate the performance of the algorithm. Additionally, the computational performance of the proposed method is studied by comparing it with existing method through some selected numerical examples.http://www.sciencedirect.com/science/article/pii/S2192440623000205Multilevel optimizationMixed integer programmingBranch-and-cutValid inequalities |
| spellingShingle | Ashenafi Awraris Berhanu Guta Wordofa Semu Mitiku Kassa Branch-and-cut solution approach for multilevel mixed integer linear programming problems EURO Journal on Computational Optimization Multilevel optimization Mixed integer programming Branch-and-cut Valid inequalities |
| title | Branch-and-cut solution approach for multilevel mixed integer linear programming problems |
| title_full | Branch-and-cut solution approach for multilevel mixed integer linear programming problems |
| title_fullStr | Branch-and-cut solution approach for multilevel mixed integer linear programming problems |
| title_full_unstemmed | Branch-and-cut solution approach for multilevel mixed integer linear programming problems |
| title_short | Branch-and-cut solution approach for multilevel mixed integer linear programming problems |
| title_sort | branch and cut solution approach for multilevel mixed integer linear programming problems |
| topic | Multilevel optimization Mixed integer programming Branch-and-cut Valid inequalities |
| url | http://www.sciencedirect.com/science/article/pii/S2192440623000205 |
| work_keys_str_mv | AT ashenafiawraris branchandcutsolutionapproachformultilevelmixedintegerlinearprogrammingproblems AT berhanugutawordofa branchandcutsolutionapproachformultilevelmixedintegerlinearprogrammingproblems AT semumitikukassa branchandcutsolutionapproachformultilevelmixedintegerlinearprogrammingproblems |