AnsweredAssumed Answered

Find integer solution in cut generation

Question asked by figen.kas on Dec 27, 2016
Latest reply on Jan 10, 2017 by figen.kas

Hello,

 

I want to ask a question about Branch and cut generation in MOSEL. The following algorithm find false route and after that it add a cut. The algorithm add cut throughout all branching. But in our routing problem, it have to add cut only when algorithm find integer solution and when route is not true. What do i need to do to find the integer solution along the branch to start the loop? Algortihm is below;

 

public function cb_hata:boolean

declarations

   ncut:integer ! Counter for cuts

   cut: array(range) of linctr ! Cuts

   cutid: array(range) of integer ! Cut type identification

   type: array(range) of integer ! Cut constraint type

   objval: real

  end-declarations

 

depth:=getparam("XPRS_NODEDEPTH")

 

if((TOPONLY and depth<1) or (not TOPONLY and depth<=CUTDEPTH)) then

   ncut:=0

 

   forall(b in SIRA|b<K)do

  forall(i in NODE)do

  forall(j in PICKUP)do

  if getsol(R(i,j,b))>0 then

   p:=j

  end-if

  end-do

  end-do

  forall(h in SIRA|h>b)do

  forall(k in NODE)do

  if getsol(R(k,INDIS(p),h))>0 then

  writeln(h," D: ",INDIS(p))

  H:=h

  end-if

  end-do

  end-do

  forall(i in NODE)do

  forall(j in PICKUP)do

  if getsol(R(i,j,b+1))>0 then

  writeln(b+1," P: ",j)

  p:=j

  end-if

  end-do

  end-do

  forall(h1 in SIRA|h1>b+1)do

  forall(k in NODE)do

  if getsol(R(k,INDIS(p),h1))>0 then

  writeln(h1," D: ",INDIS(p))

  H1:=h1

  end-if

  end-do

  end-do

  forall(j in PICKUP|j<>p)do

  if getsol(R(j,p,b+1))>0 then

  if H<H1 then

  writeln("route is false","   ", INDIS(p),"   ", H1)

  end-if

  end-if

  end-do

!Add cut

  if(H<H1) then

  cut(ncut):= sum(i in NODE|i>0 and i<K)R(i,INDIS(p),H1)

  cutid(ncut):= 0

      type(ncut):= CT_GEQ

      ncut+=1

  end-if

  end-do

returned := false

!*******************************

!add cuts to problem

if(ncut>0) then

addcuts(cutid, type, cut);

writeln("Cuts added : ", ncut, " (depth ", depth, ", node ", getparam("XPRS_NODES"),

", obj. ", getparam("XPRS_LPOBJVAL"), ")")

end-if

 

 

end-if

end-function

! ****Optimizer settings for using the cut manager****

procedure tree_cut_gen

setparam("XPRS_PRESOLVE", 0) ! Switch presolve off

setparam("XPRS_ROOTPRESOLVE", 0)    ! Switch B&B root presolve off

setparam("XPRS_EXTRAROWS", 5000)    ! Reserve extra rows in matrix

setparam("XPRS_CUTSTRATEGY", 0)

setcallback(XPRS_CB_CM, "cb_hata")  ! Set the cut-manager callback function

end-procedure

  end-model

 

Thanks a lot in advance!

Outcomes