Exact solution methods for non-convex optimization problems

Abstract

"The thesis focuses on the development of efficient algorithms for solving the non-convex problems arising in different application areas involving operations and supply chains. In the first essay, we propose an exact method for solving a general class of mixed integer concave minimization problems. The piecewise linear inner-approximation of the concave function is achieved using an auxiliary linear program leading to a bilevel program, which is solved using CPLEX after reducing it to a single level using KKT conditions. Using the proposed method, we solve two different classes of problems: the concave knapsack problem and the concave production-transportation problem. It is observed that the proposed method computationally outperforms the benchmark methods by an order of magnitude in most of the test cases for both problems. In the second essay, we propose an exact algorithm for solving non-convex optimization problems in which the presence of an inverse S-shaped function makes the problem non-convex. Using a similar approach used in the first essay, the concave part of the inverse S-shaped function is inner-approximated before solving it using the cutting plane technique. The method converges to global optima through piecewise linear inner and outer approximations. To test the computational efficiency of the algorithm, we solve a facility location problem with an inverse S-shaped production cost function. We also report some important managerial insights. In the third essay, we report exact methods to solve the hub location problem involving concave interhub transportation costs. The flows between non-hub nodes are usually routed through one or two hubs. The transportation of flows through inter-hub links results in the bundling of flows leading to economies of scale. Hence, the inter-hub transportation cost acts as a concave function forming a mixed-integer concave minimization problem. In this essay, we exactly solve the concave uncapacitated hub location problems (CUHLP) with single allocation and multiple allocations. Here, we discuss two exact methods. The first one is the same method as discussed in the first essay. We solve CUHLP with single allocation and multiple allocations using this algorithm. The other approach is a mixed integer second-order conic programming (MISOCP) approach, using which we solve a special case of CUHLP with single allocation. We present the computational results for both methods."