help-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] forall and exists?


From: Jeffrey Kantor
Subject: Re: [Help-glpk] forall and exists?
Date: Tue, 7 May 2013 10:44:03 -0400

Hi Jay,

This is a trickier issue than it might seem at first glace.  First off, the GMPL/MathProg language uses several syntactic constructs to facilitate modeling such as indexing and logical expressions.  These are different from the linear expressions used to express MILP constraints and objective functions.  The language definition doesn't allow you to mix them up as you can in some scripting languages (Matlab comes to mind). It's easy to miss these distinctions when quickly browsing the GMPL language reference.  As Xypron noted, mixing these would lead to nonlinear and nonconvex problems that are not trivially translated to LP's or MILP's.

Also note that the "Big M" technique commonly used to implement logical constraints as an MILP needs to be 'tuned' to work effectively. A proper value of M is data dependent, so the automatic translation of logical constraints to an MILP is not a trivial issue.

Second, with regard to your application, it sounds like you may need to introduce a binary decision variable -- say 

var y{B} binary;

that is one if b is in set B, and a parameter -- call it

param p{a in A} := some logical _expression_ regarding a

From here I'm not sure that I understand your problem, but something like

s.t. constr {a in A : p[a] = 1} : sum{b in B} y[b] >= x[a];

may be what you're looking for. But it's not at all clear to me that this is what you had in mind.

Hope that helps,
Jeff



On Tue, May 7, 2013 at 7:21 AM, Jay Hutfles <address@hidden> wrote:
I don't think you meant to address Andrew, but thanks for replying.

I realize if-then constraints aren't naturally supported in linear programming (or mixed integer programming).  But you can formulate constraints that are logically equivalent to if-then constraints.  See the whole part about "changing from the form 'if p then q' to 'not p or q.' "  The constraint is still true under the same conditions of the logical implication, so it constrains the binary variables in the same manner.  Yes, it may not be the most efficient, but it is a proper way to model such a constraint in a linear programming problem.


On Tue, May 7, 2013 at 5:54 AM, <address@hidden> wrote:
Hello Andrew,

GLPK is a linear programming solver. A constraint with an IF would not be linear.

In linear programming you might introduce binary variables for your purpose.

Or use a constraint programming solver.

Best regards

Heinrich Schuchardt

http://www.xypron.de

Am 07.05.13 um 07:48 schrieb Jay Hutfles

> Oh, I don't think there's anything wrong with them.  Well, except for how
>
> I'm trying to use them.
>
>
>
> I see that the examples only use them in computable parameters, though.  I
>
> was trying to use them in constraints, and was getting errors along the
>
> lines of "forall function does not exist" (sorry, I don't have the exact
>
> error with me).  The constraints were of the form:
>
>
>
>    for all a in A, if x[a] =1 then there exists a b in B such that
>
> (something or another based on a)
>
>
>
> I was having trouble directly implementing constraints of this form, so I
>
> changed the "if p then q" form to "not p or q" like this:
>
>
>
>    subject to C {a in A} :
>
>       (1 - x[a]) + (if exists {b in B} (...something or other based on a..)
>
> then 1 else 0) >= 1;
>
>
>
> I'll have to try again in the morning when I'm more awake.  Thanks for the
>
> guidance, Andrew.
>
>
>
>
>
>
>
> On Mon, May 6, 2013 at 11:36 PM, Andrew Makhorin <address@hidden> wrote:
>
>
>
> >
>
> > > Can you provide a link to an example of each?  Any help would be
>
> > > appreciated.
>
> > >
>
> >
>
> > Please see glpk/examples/color.mod (for 'exists') and
>
> > glpk/examples/egypt.mod (for 'forall').
>
> >
>
> > What is wrong with these operators?
>
> >
>
> >
>
> >
>
> _______________________________________________
>
> Help-glpk mailing list
>
> address@hidden
>
> https://lists.gnu.org/mailman/listinfo/help-glpk


_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk



reply via email to

[Prev in Thread] Current Thread [Next in Thread]