help-glpk
[Top][All Lists]

## Re: [Help-glpk] Multiple LP problem solving

 From: Dorian Tourin-Lebret Subject: Re: [Help-glpk] Multiple LP problem solving Date: Wed, 8 Jun 2011 16:13:38 +0200

2011/6/8 Andrew Makhorin
> I mean I have several objective functions within one LP. I'm trying to
> find the values of the variables x1, x2, ..., xN that minimize the
> following functions:
> z1 = a1.x1 + b1.x2 + ...
> z2 = a2.x1 + b2.x2 + ...
> z3 = a3.x1 + b3.x2 + ...
>
>
> The variables are common to each function, but the coefficient are
> not. I'm basically trying to minimize "Cx - d", given a coefficient
> matrix C and a constant vector d.
>
>
> Btw, I'm used to working with MATLAB and the lsqlin() function to
> solve that kind of LP.
>
>
> Am I clear enough?

Now you are. Thanks.

There exist two main ways to solve multicriteria problems. The first one
is using a convolution of the objectives, and the second one is a
sequential optimization. I guess that Matlab's lsqlin implements the
first approach minimizing the sum of squares of the objectives. This
leads to a quadratic programming problem that is not supported by glpk,
however, instead you might minimize the maximum of the objectives, i.e.

minimize obj: z;

s.t. z >= z1;
z >= z2;
z >= z3;
. . .

The latter differs from the least squares approach only in the metrics.

Sounds good!

I guess I have to define the objective z as z1, then add the constraints for z2..zN, right? Otherwise, I don't know how I could define an objective z without specifying the coefficients for each variable, i.e. the columns in GLPK.

Am I right?