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."
Collections
- Thesis and Dissertations [470]