04 JULY, 2021: The Decision Sciences Area at IIM Bangalore will host a webinar titled, ‘On solving a fractional programming formulation to determine the independence number of a graph’,  by Professor Jitamitra Desai, between 3pm and 4 pm, on July 09 (Friday).

He will speak on a research study of the NP-Hard maximum independent set problem from a continuous fractional programming (FP) formulation perspective, and compare and contrast this FP formulation with the well-known 0-1 linear programming formulation.

In this context, he will explain how a new class of clique sets is defined, and the structure of these clique sets is utilized to derive explicit characterizations of the number of alternate optima present in both discrete and continuous formulations. Moreover, these clique sets also enable a simple, yet powerful, construction procedure to efficiently determine maximal independent sets. He and his fellow researchers also developed a global optimization algorithm to solve the FP formulation, and they demonstrate that this continuous approach stays on par with the 0-1 discrete formulation with respect to various performance metrics. As seen in their numerical experiments, they showed that the computational time required per optimal solution is comparable and in some instances lower for the continuous formulation as compared to its discrete variant (as the number of alternate optima for Problem FP is significantly greater when compared to Problem MIS).