Optimization Online


Tighter McCormick Relaxations through Subgradient Propagation

Jaromił Najman (Jaromil.Najman***at***avt.rwth-aachen.de)
Alexander Mitsos (amitsos***at***alum.mit.edu)

Abstract: Tight convex and concave relaxations are of high importance in the field of deterministic global optimization. We present a heuristic to tighten relaxations obtained by the McCormick technique. We use the McCormick subgradient propagation (Mitsos et al., SIAM J. Optim., 2009) to construct simple affine under- and overestimators of each factor of the original factorable function. Then, we minimize and maximize these affine relaxations in order to obtain possibly improved range bounds for every factor resulting in possibly tighter final McCormick relaxations. We discuss the heuristic and its limitations, in particular the lack of guarantee for improvement. Subsequently, we provide numerical results for benchmark cases found in the COCONUT library and case studies presented in previous works and discuss computational efficiency. We see that the presented heuristic provides a significant improvement in tightness and decrease in computational time in many cases.

Keywords: Global optimization; McCormick; Range Reduction; Bounds Tightening

Category 1: Global Optimization

Category 2: Global Optimization (Theory )

Category 3: Global Optimization (Applications )

Citation: RWTH Aachen University,Aachener Verfahrenstechnik, Process Systems Engineering, Forckenbeckstraße 51, D-52074 Aachen

Download: [PDF]

Entry Submitted: 10/25/2017
Entry Accepted: 10/26/2017
Entry Last Modified: 05/24/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society