[Coin-symphony] user_is_feasible() doesn't work

[Ted Ralphs]

francois dionne wrote:
> Dear mailing list,
> 
> First, I want to thank Dr. Ralphs and Mr. Guzelsoy for their reply to my
> "Three Questions" post. Thanks to their helpful advices and suggestions,
> I was able to work out most of the issues. Now I have a different problem.
> 
> I'm working on a series of MIP problems. All I want is a feasible solution
> or proof of infeasibility of each one. The objective function is not 
> important
> except that it helps me generate user cuts.
> 
> This routine sets my parameters:
> /*************************
> *       setparam.c       *
> **************************/
> 
> #include "horatio_mip.h"
> 
> sym_environment* setparam(sym_environment *env)
> {
> sym_set_defaults(env);
> 
> sym_set_int_param(env,"max_cp_num",1);
> sym_set_int_param(env,"use_cg",TRUE);
> sym_set_int_param(env,"node_selection_rule",DEPTH_FIRST_SEARCH);
> sym_set_int_param(env,"find_first_feasible",TRUE);
> sym_set_int_param(env,"problem_type",MIXED_INTEGER_PROBLEM);
> sym_set_int_param(env,"do_reduced_cost_fixing",TRUE);
> sym_set_int_param(env,"select_candidates_default",USER__CLOSE_TO_HALF);
> sym_set_int_param(env,"compare_candidates_default",LOWEST_LOW_OBJ);
> sym_set_int_param(env,"select_child_default",PREFER_LOWER_OBJ_VALUE);
> sym_set_int_param(env,"max_size",4*1024*1024);
> sym_set_int_param(env,"max_number_of_cuts",10000);
> sym_set_int_param(env,"verbosity",-1);
> 
> return env;
> }
> 
> I also wrote my own version of these callback routines: user_find_cuts(),
> user_select_child() and user_is_feasible() .
> 
> Here's the problem: my model allows solutions that are feasible
> but not interesting. This happens when a specific continuous variable is on
> its lower bound. What I did was, I set up an objective function that 
> maximizes
> this variable (actually, I minimize its negative) and in 
> user_find_cuts(), I use
> the solution of the LP relaxation to generate cuts.
> 
> Then in user_select_child(), I prune the child when the specified 
> variable in
> the child is on its lower bound, or I use RETURN_THIS_CHILD. 

I'm not sure I follow. If you want the child to be pruned, then you need 
to return PRUNE_THIS_CHILD, not RETURN_THIS_CHILD in the array of 
actions. See

http://branchandcut.org/SYMPHONY/man/node222.html

Finally in
> user_is_feasible(), I use the same test to declare a solution unfeasible,
> ie. I set *feasible=IP_INFEASIBLE and return USER_SUCCESS. Otherwise, It
> returns USER_DEFAULT.

This seems OK.

> In the end, Symphony outputs a solution that should not have passed the
> user_is_feasible() test. Is it a bug in Symphony? Should I instead test the
> output of sym_solve() and declare the entire problem unfeasible when this
> happens?

Do you have the primal heuristic turned on? I just realized that the 
primal heuristic does not check to see whether the solution it finds is 
user feasible. It only checks for integrality. If you have the primal 
heuristic turned on, then it is probably taking your rejected solution 
and turning it into something it thinks is feasible.

> I'm using Symphony downloaded by CVS checkout on 2005-8-17. My system is
> an Intel Celeron processor running Suse Linux 9.0 and g++ 3.3.1 .
> I hope you can help.

If you can't fix it based on the above, then please post another message 
and we'll get to the bottom of it.

Cheers,

Ted
-- 
Dr. Ted Ralphs
Assistant Professor
Industrial and Systems Engineering
Lehigh University
(610)758-4784
tkralphs at lehigh.edu
www.lehigh.edu/~tkr2