Originally posted by: mremn

Dear forum,

I'm trying to write a knapsack constraint by using cp Optimizer. The program worked well for the problem with only one constraint. But when I tried to solve more than 2 constraints, it gave me a wrong result. Here is the log with some explanation for a small problem with 4 variables and 2 constraints:

 

1 is not in the domain of variable 0    //CPO tries to branch on variable 0 here

 

propagate constraint 1: variable 0 is processed (reduce 1 from variable 0)

remove 0 from variable 1

remove 0 from variable 2

remove 0 from variable 3

 

propagate constraint 2: variable 0 is processed (reduce 1 from variable 0)

//nothing here: constraint 2 cannot reduce any domain

 

propagate constraint 1: variable 1 is processed (reduce 0 from variable 1)

//nothing here

 

propagate constraint 2: variable 1 is processed (reduce 0 from variable 1)

//nothing here

 

Until here, the search is terminated, CPO returns a wrong solution without continuing to process variable 2 and 3. (the problem is in fact unfeasible). I tried both version of CPO 12.5.1 and 12.6, the phenomenon is still the same.

Could somebody explain me why this can happen?

Thank you very much for your help,

 

 

 

 

 

#CPOptimizer
#DecisionOptimization

Originally posted by: ol

Hello,

looks like you forgot some variables in the post() function of the new constraint. Can you send the code of the post?

Regards

Olivier

#CPOptimizer
#DecisionOptimization

Originally posted by: mremn

Hi Olivier,

Here is the code of the post:

#CPOptimizer
#DecisionOptimization

Originally posted by: ol

All the variables of the constraint are in _x?

If yes, maybe the problem comes from the propagate() method, does it guarantee that, when all the variables are assigned, it fails if the constraint is violated? 

The default search will give a value to each variable, do you use it or do you have defined your own search? In the latter case, maybe some variables are missing.  

Otherwise, try to post the propagate() function.

 

#CPOptimizer
#DecisionOptimization

Originally posted by: mremn

Dear Olivier,

Yes, all the variables are in _x. I used default deep first search of CPO. I don't have any my own search. If CPO continues to progress two remaining variables x2 and x3, the propagate() method will remove all the domains of x4 and the problem is unfeasible. But it's not the case here. After progressing x1, it stopped and gave a wrong solution.

#CPOptimizer
#DecisionOptimization

Originally posted by: ol

Can you send something to reproduce the problem?

Otherwise, I don't know how to help, at least try to set the log period to 1, and trace the call of the propagate() method. You also can reinject the wrong solution found as input to the solver.

 

#CPOptimizer
#DecisionOptimization

Originally posted by: mremn

Thank you Olivier,

I can send you the code. Please give me your email.

Regards,

 

Hoang

#CPOptimizer
#DecisionOptimization

Originally posted by: ol

Hello Hoang,

if you want a direct support, give me your email address, I will send you mine.

Regards,

Olivier

#CPOptimizer
#DecisionOptimization

Originally posted by: mremn

Hello Olivier,

Here is my email minhhoangha.vth@gmail.com

Thank you again,

 

Hoang

#CPOptimizer
#DecisionOptimization