This thesis presents efficient algorithms that give optimal or near-optimal solutions for problems with non-linear objective functions that arise in discrete, continuous and robust optimization.
First, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two or more linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multi-objective optimization problems, and assortment optimization problems with logit choice models. For many of these problems, we give the first fully polynomial time approximation scheme using our framework.
Next, we present approximation schemes for optimizing a rather general class of non-linear functions of low rank over a polytope. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity of the objective function. For the special case of minimizing a quasi-concave function of low-rank, we give an alternative algorithm which always returns a solution which is an extreme point of the polytope. This algorithm can also be used for combinatorial optimization problems where the objective is to minimize a quasi-concave function of low rank. We also give complexity-theoretic results with regards to the inapproximability of minimizing a concave function over a polytope.
Finally, we consider the problem of appointment scheduling in a robust
optimization framework. The appointment scheduling problem arises in
many service operations, for example health care. For each job, we are
given its minimum and maximum possible execution times. The objective is
to find an appointment schedule for which the cost in the worst case
scenario of the realization of the processing times of the jobs is
minimized. We present a global balancing heuristic, which gives an easy
to compute closed form optimal schedule when the underage costs of the
jobs are non-decreasing. In addition, for the case where we have the
flexibility of changing the order of execution of the jobs, we give
simple heuristics to find a near-optimal sequence of the jobs.
Thesis defense presentation
Slides (PDF)