help-glpk
[Top][All Lists]

## Re: [Help-glpk] Can this problem be solved in LP without binary conditio

 From: glpk xypron Subject: Re: [Help-glpk] Can this problem be solved in LP without binary condition? Date: Sat, 02 Oct 2010 18:47:30 +0200

```Hello Xiaomi,

in linear programming, the objective function is linear and
the solution space is bounded by a convex polyhedron. Hence
you cannot formulate your problem as an LP with x, y as variables.

Of cause reformulating the problem with binaries takes more
effort then writing down the solution algorithm for this problem
with GLPK.

param xmin := 2;
param xmax := 6;
param xrange := 10;
param ymin := 1;
param ymax := 6;
param yrange := 10;
printf "x = %f\n", if (xmin <= xrange - xmax ) then xmin else xmax;
printf "y = %f\n", if (ymin <= yrange - ymax ) then ymin else ymax;
end;

If you are not interested in the unique values of x, y you can of
cause introduce new variables:

u, >= min( xmin, xrange - xmax ) := min( x, xrange - x );
v, >= min( ymin, yrange - ymax ) := min( y, yrange - y );

This allows you to define an LP giving you the correct objective
value.

Best regards

Xypron

-------- Original-Nachricht --------
> Datum: Fri, 01 Oct 2010 18:58:55 -0400
> Betreff: [Help-glpk] Can this problem be solved in LP without binary
> condition?

>   The problem is: Given a total area, let's say, from (0,0) to (10,10);
> given an area for one point(x,y) that movable, let's say 2<=x<=6,
> 1<=y<=6. Find the closest position of (x,y) to the boundary of the total
> area. In the example, the solution should be (x,1), x can be any in the
> constraint.
>
> Can this problem be solved in LP without binary condition?
> Thanks.
>
> _______________________________________________
> Help-glpk mailing list