Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only

  • 1.  doubt Local Branching

    Posted 04/05/11 09:10 AM

    Originally posted by: dbaena


    hello,
    I’m trying to develop the local branching method (of Andrea Lodi and Mateo Fischetti) and I have a doubt when I apply the procedure REFINE, in order to improve the solution found when the solution found is because of TIME LIMIT or another reason.
    I don’t know if someone knows about this …
    I do:
    when I obtain a new integer solution (xtil). I call the method REFINE with this solution and I create the constraint dist(x,xtil)=0 that I add in the same model what I obtained xtil. Is to say, I fix the value of binary variables.
    After I solve this problem.
    Firstly, I want to be sure that it is right. Secondly, I am having problems because when I solve the problem with the new constraint dist(x,xtil)=0 I obtain a infeasible problem. I think that it isn’t normal…

    Thanks a lot!
    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: doubt Local Branching

    Posted 04/12/11 08:09 AM

    Originally posted by: SystemAdmin


    The following is from Andrea Lodi, which I am posting on his behalf:

    Hi, the idea of the REFINE is the following.
    Because the neighborhood has not been explored fully, one would like to prove that the solution xtil with binary variables fixed is the best possible. If that is the case either because xtil is already the best or because running REFINE improves it, then one can at least add a constraint forcing the binary part to be different (what is known as no-good, dist(x,xtil) >= 1).
    NOTE THAT I assume the "dist" operator is always imposed on the binary part ONLY (and in the symmetric version, i.e., both considering variables at 0 and 1).

    So, yes, imposing dist(x,xtil)=0 is the right choice. If you get an infeasible problem AND you put a cutoff then you have proven what you wanted (and can add the no-good). If instead no cutoff has been imposed, then something is wrong because at least solution xtil should be feasible.

    I hope this answer your question, otherwise drop me a line (andrea.lodi "at" unibo "dot" it).

    Andrea

    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: doubt Local Branching

    Posted 04/12/11 04:03 PM

    Originally posted by: dbaena


    Thanks a lot Tobias and Andrea,

    OK, I do it so I understood it right.

    I had one thing wrong and for this reason my problem (after refine) was infeasible. Now, it runs OK.

    Thank you!
    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: doubt Local Branching

    Posted 04/16/11 11:26 AM

    Originally posted by: dbaena


    Hi,

    in Local Branching, in paper of Fischetti and Lodi, in Figure 6, where they show the overall local branching function the said:

    block 3:
if (stat="feasible_sol_found") then
if (rhs < inf) then
if (first) then
delete the last local br. constraint ...
else
replace the last local br. constraint..
endif
endif
REFINE(x)


    I think that REFINE have to be put before the block where we delete and replace the last local br. constraint. It is right? Else, We can have problems with infeasible problem...

    I hope you confirmation.

    Thanks a lot!
    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: doubt Local Branching

    Posted 04/18/11 05:00 AM

    Originally posted by: SystemAdmin


    I guess this gets a little bit off topic here. Unfortunately, with his professor and CPLEX dev job, Andrea has no time to read the CPLEX forum. I suggest that you contact him directly at andrea(dot)lodi(at)unibo(dot)it.
    #CPLEXOptimizers
    #DecisionOptimization


  • 6.  Re: doubt Local Branching

    Posted 04/18/11 06:03 AM

    Originally posted by: dbaena


    Hi Tobias,
    I agree with you. I'll contact him directly.

    Thanks a lot Tobias!
    #CPLEXOptimizers
    #DecisionOptimization


  • 7.  Re: doubt Local Branching

    Posted 01/08/14 09:46 AM

    Originally posted by: Ibmuser


    Hi,

    The local branching presented in the paper of  Fischetti and Lodi, is it the same heuristic implemented in IBM Ilog Cplex studio (link below) with the OPL name 'lbheur'.

    http://pic.dhe.ibm.com/infocenter/odmeinfo/v3r4/index.jsp?topic=%2Filog.odms.ide.odme.help%2FContent%2FOptimization%2FDocumentation%2FODME%2F_pubskel%2FODME_pubskels%2Fstartall_ODME34_Eclipse1647.html

    Is there any documentation and examples of using Local Branching in IBM Ilog Cplex studio.

    Thanks,


    #CPLEXOptimizers
    #DecisionOptimization


  • 8.  Re: doubt Local Branching

    Posted 01/10/14 01:33 AM

    The exact same question was asked and answered here.


    #CPLEXOptimizers
    #DecisionOptimization


Related Content