Originally posted by: istenc

Hi,

I want to solve a relaxed mip model by cpoptimizer. Once all variables are fully instantiated at a node, i want to check if domains / values of the variables satisfy constraints of the original mip model. if they do, i can update the the incumbent if possible, otherwise i should regard the corresponding node as infeasible.

I am considering to write my own constraint for the relevant purpose, but i am wondering if there is an easier / more effective way to do it?

Thanks in advance,

İstenç

Originally posted by: Petr Vilím

Hello,

if I understand right, you want to execute normal search of CP Optimizer but check each leaf node that normally represents a solution and refuse some of them by checking additional constraints that are not part of the model. In this case I see three possible ways:

1. If there is no objective expression to minimize or maximize then it is enough to enumerate all solutions (using cp.next() function) and check them outside of the search. It is probably the simplest solution to implement, but there cannot be objective because CP Optimizer wouldn't know that some solutions were refused.
2. Create custom constraint as you suggest. In order to minimize CPU time spent by your constraint and check it only for leaf nodes you may use whenValue instead of whenRange when monitoring an integer variable (there is nothing similar for interval variables). Furthermore you can use whenValue for only one of the involved variables and do not monitor the others. Only when the monitored variable becomes bound then you may check the remaining variables, if there is still some variable unbound then you may call whenValue for that variable (note that whenValue is reversible, i.e. after backtrack the variable is again not monitored). This way your constraint will wake up very rarely.
3. You may consider using custom inferencer. It works though only if there is no interval variables in the problem. See the documentation here: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/refcppcplex/html/inferencer.html and here: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/refcppcplex/html/classes/IlcCustomInferencerI.html . In manual mode and with very high numberOfSkippedNodes your inferencer will be called just for leaf nodes.

Best regards, Petr

Originally posted by: istenc

My problem has an objective and interval variables, so i will go with the second option.

Thanks for your help,

İstenç

Originally posted by: istenc

I wrote my own customer as you suggested. Now, the problem is that:

At some leaf nodes, I employ a heuristic and obtain a lower bound on the objective value ( of maximization problem).  I want to update the best  objective value found during the search if the objective value found by the heuristic is better than that. Basically,I want to update the bounds on the objective value (globally, not locally) manually during the search. .

Is it possible to do what I want?

Best,

İstenç

Originally posted by: Petr Vilím

Do I understand right that in the leaf you take the solution provided by CP Optimizer and heuristically improve so that its objective is even better (since lower bound on maximization problem is actually a value of solution)? And then you want CP Optimizer to look only for solutions with even better cost.

I'm afraid that there is no user-level API to do that. I'll ask my colleagues provided I understand your question right.

You can of course stop the search, provide your heuristically found solution as starting point and start the search again. The engine then restores your solution and then looks only for better ones. It could work quite well but of course it is less efficient than what you suggest because some information is lost by restarting the search.

Best regards, Petr