A mixed integer linear programming formulation of the maximum betweenness problem

作者：Savic Aleksandar; Kratica Jozef^*; Milanovic Marija; Dugosija Djordje

来源：European Journal of Operational Research, 2010, 206(3): 522-527.

DOI：10.1016/j.ejor.2010.02.028

• Integer programming
• Linear programming
• Betweenness problem

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.

• 出版日期2010-11-1