Polyhedral approaches and bounding sets for bi-objective linear binary programming
Yue Zhang  1@  
1 : Laboratoire d'Informatique de Paris-Nord
Centre National de la Recherche Scientifique : UMR7030, Université Sorbonne Paris nord

We propose a Branch&Bound framework (BBBB) to enumerate every non-dominated solution of a Bi-objective Binary linear program. The efficiency of a BBBB is mainly based on the availability to prune the nodes using a comparison between the lower bound and upper bound sets. For purpose of strengthening the lower bound sets, we add valid inequalities using classical separation methods initially from mono-objective optimization background. In this bi-objective context, such a cutting plane approach could be enhanced by multi-point separation algorithms. Beyond that, we adapt our BBBB tree to a dynamic exploration both in objective and variable space parallelly. Using the VoptSolver framework in Julia, preliminary experimental results will be presented to show the efficiency of our algorithm.


Personnes connectées : 21 Vie privée
Chargement...