In general, the problem of knowing if a
problem has a solution is the same as finding one such solution.
However, many times the preprocessor can
figure out if a problem does not have a solution. A preprocessor would do simple tests such
whether a lower bound on a variable is greater than it’s
upper bound. Good preprocessors (and I’m
not familiar enough with GLPK to state how sophisticated its preprocessor is)
do many reductions of the problem and find out that in the reduced problem a
(new) lower bound is greater than a (new) upper bound, while that is not
obvious from the original problem.
Preprocessors run very quickly. Unfortunately, if a preprocessor does not
find any infeasibility it does not imply that the problem is feasible. But at minimum, you should see if GLPK can
run the preprocessor without running the optimizer.
I know this isn’t quite the answer
you were hoping for.
-Marc
From: F. Javier Diego
Martín [mailto:address@hidden
Sent: Tuesday, October 10, 2006
10:08
To: Meketon,
Marc
Subject: RE: [Help-glpk] Check for
a solution
I do not want to find a solution; I just
want to know if the problem has at least one feasible solution, i.e.
the constraints are all compatible.
-----Mensaje original-----
De: Meketon,
Marc [mailto:address@hidden
Enviado el: martes, 10 de octubre
de 2006 16:03
Para: F. Javier Diego Martín; address@hidden
Asunto: RE: [Help-glpk] Check for
a solution
Theoretically, finding a feasible solution
takes a linear programming algorithm – they have the same
complexity. You could always express a
linear program optimization problem as simply finding any feasible solution of
the primal and dual problem with the added constraint that the objective value
of the primal is less than or equal to the objective value of the dual
(assuming the standard problem description).
The point is that there is no general way of finding a feasible solution
that is inherently faster than using a linear programming algorithm because if
there was such a technique it could be used for the general linear programming
optimization algorithm.
If all you are after is to find a feasible
solution you probably should just set the objective coefficients all to zero
and then solve that problem.
-Marc
From:
address@hidden [mailto:address@hidden
On Behalf Of F. Javier Diego
Martín
Sent: Tuesday, October 10, 2006
09:50
To: address@hidden
Subject: [Help-glpk] Check for a
solution
Hello
Is
it possible to create a LPX instance and know if the problem has a feasible
solution without solve it?
Thanks
____________________________________________________________
Grupo Gesfor S.A.
Avda. de Manoteras 32
Telf: 91 304 80 94
Fax: 91 754 50 52
address@hidden
La información
contenida en este mensaje y en cualquiera de sus anexos es
confidencial y sólo debe ser leída por la persona o entidad a la que va
dirigida. Si ha recibido este mensaje por error, le rogamos lo borre
inmediatamente, así como
todas las copias del mismo, de su
sistema y lo
comunique al remitente. Su uso no autorizado está prohibido y podría ser
ilegal. Si usted no es el destinatario no debe, directa o indirectamente,
usar, revelar, difundir, imprimir o copiar ninguna de las partes de este
mensaje
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged. If
you received this message in error or are not the intended recipient, you should
destroy the e-mail message and any attachments or copies, and you are
prohibited from retaining, distributing, disclosing or using any information
contained herein. Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.
----------------------------------------------------------------------------
____________________________________________________________
Grupo Gesfor S.A.
Avda. de Manoteras 32
Telf: 91 304 80 94
Fax: 91 754 50 52
address@hidden
La información
contenida en este mensaje y en cualquiera de sus anexos es
confidencial y sólo debe ser leída por la persona o entidad a la que va
dirigida. Si ha recibido este mensaje por error, le rogamos lo borre
inmediatamente, así como todas las copias del mismo, de su sistema
y lo
comunique al remitente. Su uso no autorizado está prohibido y podría ser
ilegal. Si usted no es el destinatario no debe, directa o indirectamente,
usar, revelar, difundir, imprimir o copiar ninguna de las partes de este
mensaje
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally privileged. If you received this message in error or are not the intended recipient, you should destroy the e-mail message and any attachments or copies, and you are prohibited from retaining, distributing, disclosing or using any information contained herein. Please inform us of the erroneous delivery by return e-mail.
Thank you for your cooperation.
----------------------------------------------------------------------------
|