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

[Prieto Vivanco, Juan]

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 <mailto:jprietov at indra.es> 

www.indra.es <http://www.indra.es/>                                                                                                                                                                                                                                                                                                                                                                                                       

P Por favor, considere su responsabilidad medioambiental antes de imprimir este e-mail     

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20090417/976fc238/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 1657 bytes
Desc: image001.jpg
URL: <http://list.coin-or.org/pipermail/symphony/attachments/20090417/976fc238/attachment.jpg>