Master of Science
In this thesis, we discuss two problems that involve concave minimization problems with binary variables.For the first problem, we compare the Lagrangian relaxation method and our reformulation method in solving the location model with risk pooling (LMRP) with constant customer demand rate and equal standard deviation of daily demand.Our new method is to reformulate the original non-linear model for the LMRP as a linear one. In the reformulation, we introduce a set of parameters representing the increase in the cost of the non-linear part for each additional cost assigned to a potential facility site, and a set of new decision variables indicating how many customers are assigned to each facility. Then we get a linear model by replacing the none-linear part of the original objective function by the sum of the additional costs from 0 to the number of customers assigned.The algorithms are tested on problems with 5 to 500 potential facilities and randomly generated locations. The computation time of the Lagrangian method grows slower as the number of potential sites increases than the linear method does. Though the new method takes more time than the Lagrangian method, it may have better efficiency for solving problems with special patterns in the distance matrix or other special structure.In the second half of this thesis, we discuss a general multiple-square-root pricing problem. We test a heuristic that involves sorting, similar to the method for solving the Lagrangian sub-problem for the LMRP, and we explore conditions under which the heuristic could be optimal. The accuracy rates for this method are decreasing at a slow rate as the number of the square root terms grows, while it stays high when the number is not too big.
Li, Tao, "Algorithmic Methods for Concave Optimization Problems with Binary Variables" (2017). Theses and Dissertations. 2683.