help with removing objects in a set

[pnt1990]

Hi all,

I have been asked to solve the following problem in a better way by
the use of a greedy algorithm. It is called a vertex cover problem,
some of you might have heard of that one. You have to keep removing
elements from a set until it is not a vertex cover anymore. How can I
put this in MOSEL? The Mosel code looks loke this at the moment:

model "Heuristic for vertex cover"
uses "mmxprs","mmsystem"
options noimplicit;

parameters
DATAFILE="set14_3.dat"
end-parameters
forward function is_feasible(theset: set of string):boolean

declarations
VERTICES : set of string
VERTEXWEIGHT : array (VERTICES) of real
ADJACENT: dynamic array(VERTICES,VERTICES) of boolean
cutbound: real
Objective:linctr
end-declarations

initializations from DATAFILE
VERTEXWEIGHT
ADJACENT
end-initializations

finalize(VERTICES)

declarations
x: array(VERTICES) of mpvar
edges: array( ALLEDGES:range ) of set of string ;
neighborhoods: array(VERTICES) of set of string ;
noofedges: integer ;
end-declarations

noofedges := 0
forall(v,w in VERTICES| exists(ADJACENT(v,w))and ADJACENT(v,w)) do
if ( v< w) then
neighborhoods(v)+= {v,w};
neighborhoods(w)+= {v,w};
noofedges +=1 ;
edges(noofedges):={v,w}
end-if
create(ADJACENT(w,v))
ADJACENT(w,v):=true
end-do


if(false) then
setparam("XPRS_VERBOSE", true)
setparam("XPRS_LPLOG", 0)
setparam("XPRS_MIPLOG", 3)
end-if

Objective:=sum(v in VERTICES) VERTEXWEIGHT(v)*x(v) ;

forall(v,w in VERTICES|ADJACENT(v,w) and v<w)
x(v)+x(w)>=1

forall(v in VERTICES) x(v) is_binary

minimize(Objective)
if getprobstat<>XPRS_OPT then writeln("Something is odd!
\nTerminating!");exit(-1); end-if
writeln("The IP-OPTIMUM is: ", getobjval )

setparam("XPRS_MAXNODE", 0)
minimize(Objective)
if getprobstat<>XPRS_OPT then writeln("Something is odd!
\nTerminating!");exit(-1); end-if
writeln("Mosel found a lower bound determined: ", getobjval )
cutbound := getobjval

exportprob(0,"",Objective)

declarations
verticestocheck : set of string
mysolution : set of string
valuemysolution : real
candidate : string
candidatevalue : real
end-declarations


verticestocheck := VERTICES
mysolution := VERTICES
valuemysolution:=sum(v in mysolution)(VERTEXWEIGHT(v))

while (verticestocheck <> {}) do
writeln("Current feasible candidate: ", mysolution, " of value: ",
valuemysolution)
candidatevalue := max(v in verticestocheck)(VERTEXWEIGHT(v))
writeln(candidatevalue)
forall(v in verticestocheck)
if(VERTEXWEIGHT(v)=candidatevalue) then
candidate:= v;
break
end-if
verticestocheck-={candidate}
write("Trying to remove: ", candidate, " of value: ",
candidatevalue," ")
if (is_feasible(mysolution-{candidate})) then
mysolution -={candidate};
valuemysolution -=candidatevalue;
writeln("succeeded")
else
writeln("failed")
end-if
end-do

writeln("\nThe best solution we found is: ", mysolution,
" of value: ", valuemysolution, "\nand the bound is ", cutbound)
if valuemysolution=cutbound then
writeln("Congratulations, this proves we found the optimal solution")
else
writeln("Sorry, the bound or heuristic solution could be improved\n",
"another time")
end-if

function is_feasible(theset: set of string):boolean
returned:= true
returned:= false
(This is the part in which a solution must come. I hope you can help
me.)

end-function
end-model

Thanks in advance

[morgoth]

Hi,

I think what you are looking for is a list, not a set. In a list you
may add and remove elements as you wish. I hope this helps a bit.

Greets,

David