Algorithms for generating Pareto fronts of multi-objective integer and mixed-integer programming problems

Abstract

Multi-objective integer or mixed-integer programming problems typically have disconnected feasible domains, making the task of constructing an approximation of the Pareto front challenging. The present article shows that certain algorithms that were originally devised for continuous problems can be successfully adapted to approximate the Pareto front for integer, and mixed-integer, multi-objective problems. Relationships amongst various scalarization techniques are established to motivate the choice of a particular scalarization in these algorithms. The proposed algorithms are tested by means of two-, three- and four-objective integer and mixed-integer problems, and comparisons are made. In particular, a new four-objective algorithm is used to solve a rocket injector design problem with a discrete variable, which is a challenging mixed-integer programming problem.

Keywords:

• Multi-objective optimization
• mixed-integer programming
• scalarization
• Pareto front
• numerical methods

Acknowledgments

The authors would like to thank Jörg Fliege once again for pointing to the challenging multi-objective rocket injector design problem, which was earlier used by the authors in Burachik, Kaya, and Rizvi (2017). In the present article, the rocket injector problem has been modified/altered so as to make it a multi-objective mixed-integer problem, yielding an even more challenging instance.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Replication of results

Appendix A, provided in the online supplemental data, contains a detailed explanation of all steps in Algorithms 1 and 7. These explanations ensure that readers can replicate the results presented in Section 4, should they so wish.