A mixed integer linear programming formulation of the maximum betweenness problem |
| |
| Authors: | Aleksandar Savić Jozef Kratica Marija Milanović Djordje Dugošija |
| |
| Institution: | 1. Faculty of Mathematics, University of Belgrade, Studentski trg 16/IV 11 000 Belgrade, Serbia;2. Mathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36/III, 11 000 Belgrade, Serbia |
| |
| Abstract: | This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time. |
| |
| Keywords: | Integer programming Linear programming Betweenness problem |
| 本文献已被 ScienceDirect 等数据库收录！ |
