GAMS World Forum

Hi, all,
As known to all, minimum spanning tree problem can be modeled as a 0-1 integer problem, but how to model it in GAMS?
If possible, I hope you can give me an example.
Thanks
Hu

At 2011-05-10 02:27:59，"Fabián Mancilla" wrote:

Hello,

The solution of your problem is described in http://yetanothermathprogrammingconsult ... h-log.html. I copied the post of Erwin Kalvelagen:

> When I run my GAMS model I get
> *** Error at line 36749: log: FUNC SINGULAR: x = 0
> How can I fix this?

This means that you have a function log(x) in your model (see line 36749 in the listing file), where x assumes the value x=0.

There are several ways to fix this.

Apply a bound X.LO=0.0001;. Of course if you have LOG(EXPRESSION) then this is a little bit more complicated. In that case you need to introduce a new variable Y, and an equation Y =E= EXPRESSION; after which you can add Y.LO=0.0001 and use LOG(Y). The NLP solvers under GAMS will never evaluate a nonlinear function with the arguments outside their bounds. Note that adding a bound also changes the default initial point. Usually the default initial point is zero, but when there are bounds the default initial point becomes the closest bound from zero.
If it is just an intermediate point during the solve you can as a short-cut increase the DOMLIM option to allow a few domain errors. The initial point must be valid, otherwise GAMS will not start the solver (this can be fixed by a better initial point). In general I use this if option 1 is too complicated to implement quickly or if the addition of extra variables and equations makes the model (much) more difficult.
If you have POSITIVE VARIABLE X, then LOG(X+0.0001) is quick way to bypass the problem. The advantage of this formulation is that we still allow X=0 which may improve the readability of the solution reports.

Note that solvers may allow variables to be slightly outside their bounds due to different feasibility tolerances. The suggested value 0.0001 is sufficiently large not to be bothered by this.

Regards




--
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.



--
To post to this group, send email to gamsworld@googlegroups.com.
To unsubscribe from this group, send email to gamsworld+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/gamsworld?hl=en.

Dear Hu and Arne

MST is a very easy problem to formulate as a BIP model. Defining a
binary variable representing selecting or not selecting an arc, the
objective function would be weighted sum of arc selection variables.
Finally, since every connected tree on a graph with n nodes has
exactly n-1 arcs, the only needed constraint is to limit the sum of
selected arcs to be exactly n-1. I hope this helps you.

Bests,
Ehsan

On May 12, 12:44 pm, "Arne Stolbjerg Drud" wrote:
> > Hu:
> >
> > If it is known to all you should not have to ask this question.
> >
> > Anyway, the best way to solve a minimum spanning tree (MST) problem is probably not using a MIP formulation. MST is one of the combinatorial problems that has a very good algorithm based on building the tree step by step. The GAMS library has a model, mst, that shows this tree-building algorithm. It is done directly without using binary variables, a model or a solve statement.
> >
> > I am not aware of a formulating of the MST problem as a MIP. The difficulty is to define a set of constraints that characterize a tree. The characteristics of a tree, connectedness or equivalently lack of cycles, is not easy to represent. All kinds of tricks can be used (many similar to those used in The Traveling Salesman Problem), but you end up with a complex model.
> >
> > If I am wrong I will be happy to learn about.
> >
> > Regards
> >
> > Arne
> >
> > -------------------------------------------
> >
> > Arne Stolbjerg Drud
> >
> > ARKI Consulting & Development A/S
> >
> > Bagsvaerdvej 246A, DK-2880 Bagsvaerd, Denmark
> >
> > Phone: (+45) 44 49 03 23, Fax: (+45) 44 49 03 33, email: ad...@arki.dk
> >
> > Fra: gamsworld@googlegroups.com [mailto:gamsworld@googlegroups.com] PÃ¥ vegne af ??
> > Sendt: 11. maj 2011 04:17
> > Til: gamsworld@googlegroups.com
> > Emne: How to model minimum spanning tree in GAMS
> >
> > Hi, all,
> >
> > As known to all, minimum spanning tree problem can be modeled as a 0-1 integer problem, but how to model it in GAMS?
> >
> > If possible, I hope you can give me an example.
> >
> > Thanks
> >
> > Hu

Dear Arne

First, I must note that last time I forgot to mention another
necessary constraint which is "at least one arc entering or leaving
each node must be selected". Now, back to your response. You're right.
It seems the model still lacks a constraint for breaking the subtours.
However, the model in this condition still gives the correct objective
function but not the solution.

If you add the famous Dantzig-Fulkerson-Johnson subtour elimination
constraint, you're right because it requires 2^(n-1) constraints.
However, if you add the Miller-Tucker-Zemlin subtour elimination
constraint which requires n^2 constraints, the model becomes easy to
implement and use. I must note that if you might implement the Dantzig-
Fulkerson-Johnson subtour elimination constraint in a cutting plane
algorithm and add them sequentially, you might have a good algorithm.
However, as there are two optimal polynomial algorithms for solving
this problem (Prim and Kruskal), all of these discussion are as good
as theory (if we were able to solves MIP faster than sorting numbers,
then these discussions would be useful). For an implementation of such
algorithms, you might see the GAMS model library.

Bests,
Ehsan


On May 13, 10:51 am, "Arne Stolbjerg Drud" wrote:
> > Dear Ehsan:
> >
> > And how do you ensure that the selected set of arcs form a tree? The n-1
> > arcs-constraint is fine, but how do you ensure that all nodes must be
> > connected or, equivalently, that there are no cycles? You can add the usual
> > cycle-breaking constraints but the number becomes huge.
> >
> > Arne
> >
> > -------------------------------------------
> > Arne Stolbjerg Drud
> > ARKI Consulting & Development A/S
> > Bagsvaerdvej 246A, DK-2880 Bagsvaerd, Denmark
> > Phone: (+45) 44 49 03 23, Fax: (+45) 44 49 03 33, email: ad...@arki.dk
> >
> > -----Oprindelig meddelelse-----
> > Fra: gamsworld@googlegroups.com [mailto:gamsworld@googlegroups.com] PÃ¥ vegne
> > af Ehsan
> > Sendt: 12. maj 2011 23:07
> > Til: gamsworld
> > Emne: Re: How to model minimum spanning tree in GAMS
> >
> > Dear Hu and Arne
> >
> > MST is a very easy problem to formulate as a BIP model. Defining a binary
> > variable representing selecting or not selecting an arc, the objective
> > function would be weighted sum of arc selection variables.
> > Finally, since every connected tree on a graph with n nodes has exactly n-1
> > arcs, the only needed constraint is to limit the sum of selected arcs to be
> > exactly n-1. I hope this helps you.
> >
> > Bests,
> > Ehsan
> >
> > On May 12, 12:44 pm, "Arne Stolbjerg Drud" wrote:> Hu:
> >
>> > > If it is known to all you should not have to ask this question.
> >
>> > > Anyway, the best way to solve a minimum spanning tree (MST) problem is
> >
> > probably not using a MIP formulation. MST is one of the combinatorial
> > problems that has a very good algorithm based on building the tree step by
> > step. The GAMS library has a model, mst, that shows this tree-building
> > algorithm. It is done directly without using binary variables, a model or a
> > solve statement.
> >
>> > > I am not aware of a formulating of the MST problem as a MIP. The
> >
> > difficulty is to define a set of constraints that characterize a tree. The
> > characteristics of a tree, connectedness or equivalently lack of cycles, is
> > not easy to represent. All kinds of tricks can be used (many similar to
> > those used in The Traveling Salesman Problem), but you end up with a complex
> > model.
> >
> >
> >
> >
> >
>> > > If I am wrong I will be happy to learn about.
> >
>> > > Regards
> >
>> > > Arne
> >
>> > > -------------------------------------------
> >
>> > > Arne Stolbjerg Drud
> >
>> > > ARKI Consulting & Development A/S
> >
>> > > Bagsvaerdvej 246A, DK-2880 Bagsvaerd, Denmark
> >
>> > > Phone: (+45) 44 49 03 23, Fax: (+45) 44 49 03 33, email: ad...@arki.dk
> >
>> > > Fra: gamsworld@googlegroups.com [mailto:gamsworld@googlegroups.com] PÃ¥
> > vegne af ??
>> > > Sendt: 11. maj 2011 04:17
>> > > Til: gamsworld@googlegroups.com
>> > > Emne: How to model minimum spanning tree in GAMS
> >
>> > > Hi, all,
> >
>> > > As known to all, minimum spanning tree problem can be modeled as a 0-1
> >
> > integer problem, but how to model it in GAMS?
> >
> >
> >
>> > > If possible, I hope you can give me an example.
> >
>> > > Thanks
> >
>> > > Hu
> >
> > --
> > "gamsworld" group.
> > To post to this group, send email to gamsworld@googlegroups.com.
> > To unsubscribe from this group, send email to
> > gamsworld+unsubscribe@googlegroups.com.
> > For more options, visit this group athttp://groups.google.com/group/gamsworld?hl=en.- Hide quoted text -
> >
> > - Show quoted text -

Hello dear all,
we don't understand this solution of Bmatrix. can you explain us? thanx.

14 Mayıs 2011 Cumartesi 11:40:52 UTC+3 tarihinde Matthias yazdı:

Dear all:

Here is a GAMS formulation of MST using network techniques:

/// GAMS
START //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
$title Minimum Spannung Tree Formulation
$ontext

A Node-arc incidence matrix of type (num.of nodes) x (num.of
edges)

an example of a conservation of flow constraint:
Ax = b := (1,0,0,0,0,0,-1)'
where one unit external in-flow at 1st node and one unit out-flow at
last node
and -1 <= x(k) <= +1 for each arc k, flow vector x
* 1st node and last node are connected if and only if Ax = b has a
solution
* network flow theory considers directed arcs. LOWER BOUND[x(k)] =
-1 and
UPPER BOUND[x(k)] = +1 allows to represent an undirected graph,
i.e. from-to
is just a definition of sign.
An n node connected graph has n(n-1)/2 pairs of nodes to be connected,
so:
matrix equation AX = B
where X of type (num.of edges) x (n(n-1)/2)
the h-th column of X is a flow vector and
B of type (num.of nodes) x (n(n-1)/2) provides all
combinations
of external flows.

$offtext

set i Node / n1 * n7 /,
k Edge / e1 * e12 /,
h column index of matrix B / 1 * 21 /;

table A(i,k) 'Node-arc incidence matrix'
e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12
n1 1 1
n2 -1 1 1 1
n3 -1 -1 1 -1
n4 -1 -1 1 1 1
n5 -1 -1 1
n6 -1 1 1
n7 -1 -1 -1

parameter c(k) /
e1 = 8, e2 = 5, e3 = 10, e4 = 2, e5 = 18, e6 = 3,
e7 = 12, e8 = 30, e9 = 4, e10 = 14, e11 = 16, e12 = 26 /;

parameter B(i,h) /
n1.(1*6)=1, n2.1=-1, n3.2=-1, n4.3=-1, n5.4=-1, n6.5=-1,
n7.6=-1,
n2.(7*11)=1, n3.7=-1, n4.8=-1, n5.9=-1, n6.10=-1, n7.11=-1,
n3.(12*15)=1, n4.12=-1, n5.13=-1, n6.14=-1, n7.15=-1,
n4.(16*18)=1, n5.16=-1, n6.17=-1, n7.18=-1,
n5.(19,20)=1, n6.19=-1, n7.20=-1,
n6.21=1, n7.21=-1
/;

option decimals=0; display B;

variable z obj.fun.val,
x(k,h) flow variable;
binary variable y(k) edge k in MST;

x.LO(k,h) = -1;
x.UP(k,h) = 1;

equation OBJ objective function,
FLOW conservation of flow constraints,
EDGE1, EDGE2 if flow in arc k then k edge in MST,
NEDGE n-1 edges make up a tree;

OBJ .. z =E= sum(k, c(k) * y(k));
FLOW(i,h) .. sum(k, A(i,k)*x(k,h)) =E= B(i,h);
EDGE1(k,h) .. y(k) =G= x(k,h);
EDGE2(k,h) .. y(k) =G= -x(k,h);
NEDGE .. sum(k, y(k)) =E= 6;

model MSTFORMUL / ALL /;
solve MSTFORMUL using MIP min z;
display y.L;
/// GAMS
END //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Best wishes,
Matthias

--
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at https://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.