Bi-criteria optimization

In the following paper http://nvlpubs.nist.gov/nistpubs/jres/111/2/V111.N02.A05.pdf a two objective model is developed. The usual way I see such models implemented is by adding weights in some linear fashion, e.g.:

Here a somewhat unusual form is used:

Indeed when β=0 we get a single objective scheduling problem:

Here the slack z_k in bin k is maximized using a quadratic objective. This is not a trivial problem to solve in itself as the problem is non-convex and we need a global solver. The authors use Lingo but other suitable solvers are Baron and GloMiQo. (Looking at the data – all integer – it should not be too difficult to linearize this at the expense of extra binary variables).

When we look at the 2-objective problem formulation we can observe this can be written as:

When β is fixed the last term is constant, so we are left with:

Note that the paper want to maximize the slacks z_k, but minimize the start time x_i,kt_k. I did not immediately understand how this objective can actually work. The more direct approach I would use is:

or may be:

Actually what is proposed in the paper is quite clever. Observe that minimizing the t_ks_ix_i,k's is equivalent to maximizing t_kz_k (as the z is a slack indicating unused capacity).

The paper indicates it finds three different solutions. They probably use a scheme trying beta=0,0.01,0.02,.., or may be some bisection. There is a much better approach where we solve a single problem for each non-dominated point (plus one problem to detect there are no more such points). Using the separable formulation with:

we can add some equations that allow us to trace the efficient frontier. This actually gives us 4 non-dominated solutions:

The second solution was not found in the paper.

For a second data set the paper reports 8 different solutions. My model generates 18 non-dominated solutions:

My conclusion: although the proposed formulation is quite clever, a more traditional formulation allows us to better trace the efficient frontier.