|
|
 |
|
Jeudi 20 Mars
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle C213 |
| Résumé: |
Nash bargaining solution for bi-objective combinatorial optimization |
| Description: |
Minh Hieu Nguyen Bi-objective combinatorial optimization (BOCO) arises in many real-world scenarios where a decision-maker (DM) must simultaneously optimize two conflicting objectives. BOCO poses significant challenges due to the discrete nature of the decision space and the inherent trade-offs between the objectives. Existing methods for BOCO can be broadly categorized into a posteriori methods, which explore the Pareto front comprehensively, and a priori methods, for which DM's preferences are defined beforehand and incorporated in the optimization phase. While a posteriori methods offer a variety of trade-off solutions, a priori methods are often preferred in practice due to their computational efficiency and compatibility with the decision-making process. Cooperative game theory and multi-objective optimization intersect in finding acceptable solutions amidst conflicting goals. The concepts in bargaining games are well-suited for solving multi-objective optimization problems because both involve resolving trade-offs among competing interests (players or objectives). In convex multi-player bargaining problems, the Nash Bargaining Solution (NBS), a fundamental concept introduced by Nash, offers a powerful framework for balancing multiple objectives by ensuring fairness and mutual benefit for the parties involved. Although the concept has been generalized for non-convex bargaining problems, there has been limited application of the NBS in multi-objective optimization, particularly in BOCO. Motivated by this gap, in this research, we aim to consider the NBS as a criterion for selecting preferred solutions within the Pareto front of BOCO. In multi-player bargaining problems, the NBS maximizes the product of the players' gains over their disagreement outcomes. In the BOCO context, the NBS maximizes the product of the objectives relative to a reference point, which can be chosen as the Nadir point. Notice that the Nadir point is obtained by computing each objective with the optimal decision vector of the other objective. Along with Utopia point, which is the (unfeasible) point where both objectives take maximum values, they are crucial for understanding the trade-offs between two objectives and guiding the decision-making process. For our purpose, we consider a more general version of the NBS in BOCO by incorporating the DM's point of view. Specifically, we introduce the generalized NBS (rho-NBS) where rho > 0 is a parameter reflecting the DM's priority to the first objective compared to the second one. Thus, the rho-NBS maximizes the product of the power rho of the first objective and the second objective relative to the Nadir point. It is important to note that the problem of maximizing the product of two functions, even when they are linear with binary variables, is NP-hard. In this research, we focus on identifying the rho-NBS within the set of supported efficient solutions instead of the whole Pareto front. These supported efficient solutions are located on the convex hull of the Pareto front and offer valuable insights into its structure in BOCO. We first introduce the rho-NBS concept for BOCO. Then, we develop a binary search algorithm to identify the rho-NBS within the set of supported efficient solutions. To the best of our knowledge, this is the first application of the Nash bargaining game to multi-objective combinatorial optimization, where an efficient algorithm has been developed. Finally, we apply our theory and algorithm to the Bi-Objective Assignment Problem (BOAP), a specific example of BOCO. |
|
|
