Start
Jan 15, 2015 - 17:00
End
Jan 15, 2015 - 18:00
Venue
LC-102
Event Type
Speaker
Mr. Yash Puranik PhD Student Carnegie Mellon University
Title
Constraint propagation and relaxation techniques for global MINLP optimization
Abstract: With increase in the computing power available optimization models used to make business and engineering decisions are becoming more and more complex.As the size of such models continues to increase analysing models giving erroneous results and correcting them becomes increasingly difficult. Identification of Irreducible Infeasible Sets (IIS) in a model can help speed up the process of correcting infeasible models. Identifying an IIS provides the modeller with a set of inconsistencies that need to be corrected. While several algorithms have been proposed efficient implementations are only available for IIS isolation in linear programs(LPs). We propose a novel algorithm for IIS identification that is applicable to NLPs and MINLPs. The proposed algorithm makes use of feasibility-based reduction techniques in a computationally inexpensive preprocessing stage to test for infeasibility for subparts of the infeasible model. This stage allows for rapid elimination of a large number of constraints in the model providing a significant speedup in IIS identification. We implement our proposed algorithm within the global solver BARON. The utility of this algorithm is demonstrated through computational experiments on a test set of 805 infeasible problems. Computational results demonstrate that the algorithm is effective on allproblem classes. The preprocessing step is able to speed up IIS identification by 4 times on average and by as high as 100 times for some problems. For 65% of the test problems the preprocessing step is able to eliminate all constraints not part of an IIS. In a complementary research direction in order to strengthen relaxations for global optimization we propose explicit use of first order optimality conditions in problem formulation. For problems with edge concave intermediates we also investigate cutting plane generation techniques.Note : Attendance is mandatory for CL702/ CL704 Participants.