Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

Bi-objective Branch-and-Cut Algorithms Based on LP Relaxation and Bound Sets.

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ على الانترنت اقرأ أكثر حفظ في قائمتي
  • معلومة اضافية
    • الموضوع:
      COMBINATORIAL optimization; LINEAR programming; BILEVEL programming; ALGORITHMS; POINT set theory; RELAXATION for health
    • نبذة مختصرة :
      Most real-world optimization problems are multi-objective by nature, with conflicting and incomparable objectives. Solving a multi-objective optimization problem requires a method that can generate all rational compromises between the objectives. This paper proposes two distinct bound set-based branch-and-cut algorithms for general bi-objective combinatorial optimization problems based on implicit and explicit lower-bound sets. The algorithm based on explicit lower-bound sets computes, for each branching node, a lower-bound set and compares it with an upper-bound set. The other fathoms branching nodes by generating a single point on the lower-bound set for each local nadir point. We outline several approaches for fathoming branching nodes, and we propose an updating scheme for the lower-bound sets that prevents us from solving the bi-objective linear programming relaxation of each branching node. To strengthen the lower-bound sets, we propose a bi-objective cutting-plane algorithm that adjusts the weights of the objective functions such that different parts of the feasible set are strengthened by cutting planes. In addition, we suggest an extension of the branching strategy "Pareto branching." We prove the effectiveness of the algorithms through extensive computational results. [ABSTRACT FROM AUTHOR]
    • نبذة مختصرة :
      Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)