AnsweredAssumed Answered

Setting bounds on variables for heuristics

Question asked by pmlwd@leeds.ac.uk on Jun 29, 2016
Latest reply on Jun 30, 2016 by pmlwd@leeds.ac.uk

Hello there

 

I have been trying to produce an iterative heuristic that would try setting different bounds on a few decision variables, but I have encountered a problem. Below is a very simple example of the part with which I am having difficulties. Is anyone able to help me?

 

model setboundtest
uses "mmxprs"

 

declarations
     x:mpvar
     BOUND:integer
     Constr1:linctr
end-declarations

 

x>=5                                  ! Set lower bound
while (getprobstat<>integer(XPRS_OPT)) do
      BOUND+=1
      if BOUND=1 then         ! First time through...
           Constr1:=x<=1        ! ... put constraint on x
      elif BOUND=2 then      ! Second time through...
           Constr1:=0              ! ... remove constraint...
           setub(x,BOUND)     ! ... and add upper bound
      else                              ! Thereafter...
           setub(x,BOUND)     ! ... adjust upper bound
      end-if
      writeln("Bound before optimiser invoked:",getub(x))
      maximise(x)
      writeln("Bound after optimiser invoked:",getub(x),"\n")
end-do
if getprobstat=XPRS_OPT then writeln("Optimality reached. x=",x.sol);end-if

end-model

 

I expect for this to be feasible after the fifth iteration. The output I get is as follows:

 

Bound before optimiser invoked:1.79769e+308
Bound after optimiser invoked:1e+020

 

Bound before optimiser invoked:2
Bound after optimiser invoked:1e+020

 

Bound before optimiser invoked:3
Bound after optimiser invoked:3

 

Optimality reached. x=3

 

I think that the problem is resetting in the third run, but I am not sure why. Indeed, this doesn't happen with the Newton-barrier algorithm (as maximise(XPRS_BAR,x)); the output when it is used is as follows:

 

Bound before optimiser invoked:1.79769e+308
Bound after optimiser invoked:1e+020

 

Bound before optimiser invoked:2
Bound after optimiser invoked:1e+020

 

Bound before optimiser invoked:3
Bound after optimiser invoked:3

 

Bound before optimiser invoked:4
Bound after optimiser invoked:4

 

Bound before optimiser invoked:5
Bound after optimiser invoked:5

 

Optimality reached. x=5

 

My understanding for the run with the Newton-barrier algorithm is this: the first time through, the constraint indirectly puts a bound on x. Therefore, the bound initially equal to that of a real, before being limited to the default maximum by the optimiser. On the second iteration the constraint is removed, which resets the problem. Bounds cannot be placed using setub() or setlb() for problems not loaded, so the value taken in the optimiser is again the default. Thereafter, the same problem is re-run, but with different bounds, and setub() and setlb() can be used.

 

Why does this not work when an algorithm is not selected? One way around this is to add and delete constraints each time to force the problem to reload. Can this be done simply by setting the bounds?

 

Any help with this would be greatly appreciated.

 

Thanks

Outcomes