Cone contraction and reference point methods for multi-criteria mixed integer optimization

• Published in: European journal of operational research 2013-09, Vol.229 (3), p.645-653
• Main Authors: Kallio, Markku, Halme, Merja
• Format: Article
• Language: English
• Subjects: Cone contraction; Convergence; Hierarchies; Integer programming; Mathematical problems; Multi-criteria decision making; Multi-criteria optimization; Multiple criteria decision making; Optimization; Optimization techniques; Pareto optimum; Reference point method; Studies
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2013.03.006

•An interactive approach for a mixed integer multi-criteria optimization is introduced.•The DM makes pairwise comparisons of identified Pareto optimal points and gives reference points.•Assuming a quasi-concave value function pairwise comparisons are used to contract the cone of admissible objective vectors.•Numerical simulation tests indicate reasonably fast convergence.•Convergence is guaranteed for the pure integer case. Interactive approaches employing cone contraction for multi-criteria mixed integer optimization are introduced. In each iteration, the decision maker (DM) is asked to give a reference point (new aspiration levels). The subsequent Pareto optimal point is the reference point projected on the set of admissible objective vectors using a suitable scalarizing function. Thereby, the procedures solve a sequence of optimization problems with integer variables. In such a process, the DM provides additional preference information via pair-wise comparisons of Pareto optimal points identified. Using such preference information and assuming a quasiconcave and non-decreasing value function of the DM we restrict the set of admissible objective vectors by excluding subsets, which cannot improve over the solutions already found. The procedures terminate if all Pareto optimal solutions have been either generated or excluded. In this case, the best Pareto point found is an optimal solution. Such convergence is expected in the special case of pure integer optimization; indeed, numerical simulation tests with multi-criteria facility location models and knapsack problems indicate reasonably fast convergence, in particular, under a linear value function. We also propose a procedure to test whether or not a solution is a supported Pareto point (optimal under some linear value function).