The Multiobjective Discrete Optimization Problem: A Weighted Min-Max Two-Stage Optimization Approach and a Bicriteria Algorithm
研究多目标离散优化问题，提出两阶段子问题求解方法，并开发双准则离散优化算法，在背包问题上比切比雪夫方法表现更好，采样版本也很有前景。
We study the multiple objective discrete optimization (MODO) problem and propose two-stage optimization problems as subproblems to be solved to obtain efficient solutions. The mathematical structure of the first level subproblem has similarities to both Tchebycheff type of approaches and a generalization of the lexicographic max-ordering problem that are applicable to multiple objective optimization. We present some results that enable us to develop an algorithm to solve the bicriteria discrete optimization problem for the entire efficient set. We also propose a modification of the algorithm that generates a sample of efficient solutions that satisfies a prespecified quality guarantee. We apply the algorithm to solve the bicriteria knapsack problem. Our computational results on this particular problem demonstrate that our algorithm performs significantly better than an equivalent Tchebycheff counterpart. Moreover, the computational behavior of the sampling version is quite promising.