Metaheuristic Search with Inequalities and Target Objectives for Mixed Binary Optimization Part I: Exploiting Proximity

Recent adaptive memory and evolutionary metaheuristics for mixed integer programming have included proposals for introducing inequalities and target objectives to guide the search. These guidance approaches are useful in intensification and diversification strategies related to fixing subsets of variables at particular values, and in strategies that use linear programming to generate trial solutions whose variables are induced to receive integer values. In Part I (the present paper), we show how to improve such approaches by new inequalities that dominate those previously proposed and by associated target objectives that underlie the creation of both inequalities and trial solutions. Part I focuses on exploiting inequalities in target solution strategies by including partial vectors and more general target objectives. We also propose procedures for generating target objectives and solutions by exploiting proximity in original space or projected space. Part II of this study (to appear in a subsequent issue) focuses on supplementary linear programming models that exploit the new inequalities for intensification and diversification, and introduce additional inequalities from sets of elite solutions that enlarge the scope of these models. Part II indicates more advanced approaches for generating the target objective based on exploiting the mutually reinforcing notions of reaction and resistance. Our work in the concluding segment, building on the foundation laid in Part I, examines ways our framework can be exploited in generating target objectives, employing both older adaptive memory ideas of tabu search and newer ones proposed here for the first time.