Preprocessing and cut generation techniques for multi-objective binary programming

Natashia Boland, Hadi Charkhgard and Martin Savelsbergh

European Journal of Operational Research, 2019, vol. 274, issue 3, 858-875

Abstract: We present the theoretical foundations for a number of preprocessing and cut generation techniques for multi-objective binary programs. The techniques are based on a characterization of conditions under which the objective functions of a multi-objective binary program guarantee the existence of an ideal point in criterion space, i.e., the existence of a feasible solution that simultaneously minimizes all objectives. Even though few multi-objective binary programs of interest have objective functions satisfying these conditions, the conditions are likely to be satisfied for a subset of the objective functions and/or be satisfied when the objective functions are restricted to a subset of the variables. We show that recognizing whether or not this occurs is NP-hard, but can be done in pseudo-polynomial time. The preprocessing and cut generation techniques can be incorporated in any decision or criterion space search algorithm for multi-objective binary programs. Preliminary computational tests demonstrate their potential in practice.

Keywords: Multi-objective binary program; Ideal point; Computational complexity; Preprocessing; Cut generation (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718308877
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:274:y:2019:i:3:p:858-875

DOI: 10.1016/j.ejor.2018.10.034

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().