Efficient computation of the search region in multi-objective optimization

Efficient computation of the search region in multi-objective optimization

Kerstin Dächert,

University of Wuppertal


 –

Abstract:

Multi-objective optimization methods often proceed by iteratively producing new solutions. For this purpose it is important to determine and update the search region efficiently. It corresponds to the part of the objective space where new nondominated points could lie and can be described by a set of so-called local upper bounds whose components are defined by already known nondominated points. In the bi-objective case the update of the search region is easy since a new point can dominate only one local upper bound. Moreover, the local upper bounds as well as the nondominated points can be kept sorted increasingly with respect to one objective and decreasingly with respect to the other. For more than two objectives these properties do no longer hold. In particular, several local upper bounds might have to be updated at once when a new nondominated point is inserted into the search region. In this talk we concentrate on how to design this update efficiently. Therefore we study a specific neighborhood structure among local upper bounds. Thanks to this structure we can quickly identify all local upper bounds that are affected by a new nondominated point, i.e. that have to be updated. We propose a new scheme to update the search region with respect to a new point more efficiently compared to existing approaches. Besides, the neighborhood structure provides new theoretical insight into the search region and the location of nondominated points for more than two objectives (cf. Dächert, K., Klamroth, K., Lacour, R., Vanderpooten, D.: Efficient computation of the search region in multi-objective optimization, European Journal of Operational Research 260(3):841–855, 2017).

Bio

Dr. Kerstin Dächert is a Research Associate (interim lecturer position) at the Department of Mathematics and Informatics, University of Wuppertal, Germany. Her interests include multicriteria optimization, combinatorial optimization and applications of operations research, e.g. in energy economics.

 

The event is finished.

About INESC-ID

INESC-ID, “Instituto de Engenharia de Sistemas e Computadores: Investigação e Desenvolvimento em Lisboa” is a Research and Development and Innovation Organization (R&D+i) in the fields of Computer Science and Electrical and Computer Engineering. INESC-ID mission is to produce added value to people and society, supporting the response of public policies to scientific, health, environmental, cultural, social, economic and political challenges. INESC-ID promotes cooperation between academia and industry by addressing research on daily life issues, such as healthcare, space, mobility, agri-food, industry 4.0, and smart grids. This high level of knowledge transfer is achieved through both competitive research projects and direct contracted research. Public and private entities have therefore access to a pool of knowledge, resources and services provided through the unique competencies available at the institution.

 

INESC-ID is supported by:

Join our newsletter

* indicates required

Subscriber consent

The data submitted through this form will be used exclusively for the sending of INESC-ID Newsletter, NEWS-ID, and will not, under any circumstances, be shared with third parties. If you choose to, you can easily unsubscribe from the newsletter by following the link presented in the footer. In that case, your data will be automatically deleted from our information system. If you need to update your contact information or clarify any questions related to the newsletter, please contact info@inesc-id.pt. By submitting this form, you give permission to the use of your personal data according to the conditions above.

We use Mailchimp as our marketing platform. By clicking below to subscribe, you acknowledge that your information will be transferred to Mailchimp for processing. Learn more about Mailchimp's privacy practices here.

});