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

[Ashutosh Mahajan]

hi Prieto,

i looked into the problem and was not able to repeat your observation.
probably because im not changing the objective function like you are. are you
using an MPS or an LP file as an input? could you send me one if possible? it
would help me locate the problem more easily. otherwise, just send me the
output of symphony and i will try to guess from there. 

The find_tree_lb() function returns a lower bound equal to the upper bound
only when there are no more nodes left in the search-tree or when the lower
bound is actually equal to the upper bound. both seem to be correctly detected
in the function. could you tell me what was the optimal solution value in the
original problem?

ashu 


> From: 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
> 
> 
> 
> 
> -- 
> Regards
> Ashutosh Mahajan
> www.lehigh.edu/~asm4



--
regards
Ashutosh Mahajan
http://coral.ie.lehigh.edu/~asm4