[Symphony] Warm Start problems detected when changing Objective function and running with Gap Limit>=0 and correction proposal

[Ted Ralphs]

Sorry for the delay in responding---the whole development team has
been traveling recently. We are getting ready to make a release 5.2.0
and will take a look at this to make sure it's fixed before we make
the release. It's entirely possible that it's a bug since our testing
doesn't currently exercise the code in the way that you are
describing.

Cheers,

Ted

2009/4/17 Prieto Vivanco, Juan <jprietov at indra.es>:
> We are using SYMPHONY’s version 5.1.8, for solving a MIP problem with warm
> start, and we have found the following problem:
>
> ·         We do a first solving keeping warm-start information and once a
> feasible solution is found, we modify the objective function and call
>  sym_warm_solve with a certain Gap_limit>=0.
>
> If we set a Gap_limit>0 the call to sym_warm_solve returns immediately with
> the message of “Optimal solution found” and the same initial solution
> without further optimization.
>
> If we run the same case with Gap_Limit= -1 the solver iterates several times
> with gaps in each iteration much greater than the Gap_limit parameter.
>
>
>
> I have traced the problem comparing execution with and without Gap_limit and
> everything is the same up to the first call to function “shall_we_dive” were
> the tm->ub=1e7 and the tm->lb=infinity.
>
> At the beginning of the function the call to find_tree_lb(tm) makes
> tm->lb=tm->ub.
>
> Having ub and lb equal and Gap_limit>=0 makes  always the function return
> the value DO_NOT_DIVE and stopping the optimization, does not matter with
> value of Gap_limit you use.
>
>
>
> If Gap_limit=-1 the function returns CHECK_BEFORE_DIVE and optimization
> continues.
>
>
>
> I have also tested the last version 5.1.10 and the same problem appears.
>
>
>
> The only way I have found of solving the problem is modifying the function
> “shall_we_dive” included in the file “tm_func.c”  of the TreeManager
> directory.
>
> I include adjoin the modification proposed marked with ‘>>>’.
>
>
>
>
>
> ________________________________________________________
>
> char shall_we_dive(tm_prob *tm, double objval)
>
> {
>
>    char dive;
>
>    int i, k;
>
>    double rand_num, average_lb;
>
>    double cutoff = 0;
>
>
>
>    find_tree_lb(tm);
>
>
>
>    if (tm->par.time_limit >= 0.0 &&
>
>         wall_clock(NULL) - tm->start_time >= tm->par.time_limit){
>
>       return(FALSE);
>
>    }
>
>
>
>    if (tm->par.node_limit >= 0 && tm->stat.analyzed >= tm->par.node_limit){
>
>       return(FALSE);
>
>    }
>
>
>
>    if (tm->has_ub && (tm->par.gap_limit >= 0.0)){
>
>>>>            if (tm->ub>tm->lb) {// PVJ 13/04/2009
>
>             if (100*(tm->ub-tm->lb)/tm->ub <= tm->par.gap_limit){
>
>                   return(FALSE);
>
>                   }
>
>>>>            }
>
>    }
>
> _______________________________________________________________
>
>
>
>
>
> I also included detail of the calling program.
>
>
>
> int error_user = sym_explicit_load_problem(env, n_cols, n_rows, start,
> index, value, col_lb,
>
>                        col_ub, int_vars, objective1, NULL, row_sense,
>
>                        row_rhs, row_range, TRUE);
>
>
>
> sym_set_str_param(env,"gap_limit",gap_limit);
>
> sym_set_int_param(env, "keep_warm_start", TRUE);
>
> sym_set_int_param(env, "find_first_feasible", TRUE);
>
> sym_set_int_param(env, "node_selection_strategy", DEPTH_FIRST_SEARCH);
>
>
>
> int cp_num;
>
> int ncutpools = sym_create_permanent_cut_pools(env, &cp_num);
>
>
>
> int rvalue = sym_solve(env);
>
> ws = sym_get_warm_start(env,true);
>
>
>
> sym_set_int_param(env, "node_selection_strategy", LOWEST_LP_FIRST);
>
> sym_set_int_param(env,"do_reduced_cost_fixing",FALSE);
>
>
>
> sym_set_int_param(env, "find_first_feasible", FALSE);
>
> rvalue = sym_set_int_param(env, "node_limit", -1);
>
>
>
> for (int i=0; i<n_cols; i++){
>
>            sym_set_obj_coeff(env, i, objective2[i]);
>
> }
>
> rvalue = sym_warm_solve(env);
>
>
>
>
>
> Please if posible confirm if there is any other possible way of avoiding the
> problem without modifying the code or if considered adecuate include the
> correction in next version.
>
>
>
> Please contact me for any further clarification.
>
>
>
> Thanks for the help and the  excelent work done in the library.
>
>
>
> Best Regards.
>
>
>
>
>
>
>
> Juan Prieto Vivanco
>
>
>
> Forecast & Optimization Manager
>
> Energy Technologies.
>
>
>
> Parque empresarial La Finca, Edificio 4
>
> Avda de la Finca s/n
>
> 28223 Pozuelo de Alarcon
>
> MADRID
>
> SPAIN
>
> Tlf directo : 912 579 023
>
> Móvil: 691 513 017
>
> Tlf centralita: 912 102 000 (ext: 49023).
>
> Fax: 91 210 20 10
>
> jprietov at indra.es
>
> www.indra.es
>
> P Por favor, considere su responsabilidad medioambiental antes de imprimir
> este e-mail
>
>
>
> _______________________________________________
> Symphony mailing list
> Symphony at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/symphony
>
>



-- 
Dr. Ted Ralphs
Associate Professor, Lehigh University (permanent)
Visiting Professor, Monash University (current)
(610) 628-1280
ted 'at' lehigh 'dot' edu
coral.ie.lehigh.edu/~ted

Sent from Melbourne, Vic, Australia