2
$\begingroup$

I'm trying to feed information retrieved from my neural network to my CP model to help narrow down the search on big instances of my problem. However, I also want to remove the additional imposed constraints to the model and solve it to the optimum, once the best possible solution given the additional constraints from NN is found. This can be done by model.remove_expressions() function but I've noticed that the search starts from beginning without using any knowledge acquired in the previous search.

Is there a way how to transfer the already searched space from more constrained model to less constrained one (i.e. remove constraints and search only the remaining space, not all of it)?

I've considered warm starting (using the best solution from more constrained problem) and also instead of adding additional conditions, using the data from neural network to guide the search phases. However, from my experience both of these are not so efficient, so they are only my backup options.

$\endgroup$

1 Answer 1

2
$\begingroup$

I am fairly certain that you cannot resume solution from the previous final state after altering the model. This is a known fact with CPLEX, presumably the same with CPOptimizer for essentially the same reason: the final state of the previous solve may not be valid for the modified problem. For instance, if you were to drop constraints and resume, the true optimal solution might never be found because it might have been eliminated during the first solve by one of the subsequently dropped constraints.

$\endgroup$
6
  • $\begingroup$ Thank you for your answer. However, I either don't fully understand or I think this doesn't have to apply every time. In my problem, the part of my model influenced by this is simple ordering of tasks given some precedences. While some precedences are given by the problem specification, others are predicted by machine learning to help narrow down the search (improve propagation). So firstly, I constrain the model by both and then I remove the ML ones and I want to re-solve the more relaxed problem. Thus the solutions in the first search all lie in the solution space of the second search. $\endgroup$
    – eXPRESS
    Aug 31, 2021 at 13:35
  • $\begingroup$ So it would make sense to me to keep the searched space labeled as searched, because all those solutions checked are actually valid solutions to the relaxed model and they have the same value in both models. There is no reason why explore the same space. Also it would make sense to keep the best solution, bounds and other internal knowledge which the CPOptimizer uses and this is also clearly not happening. $\endgroup$
    – eXPRESS
    Aug 31, 2021 at 13:40
  • 1
    $\begingroup$ The issue is that solutions removed in the first search would be feasible after you drop the ML constraints. You might be OK with leaving them removed, but CPO has no way of knowing that. Warm starting after modifying the model would in general have the potential to result in suboptimal solutions (or even declarations of infeasibility when the modified problem is actually feasible). To avoid such errors, CPO (and CPLEX) do not warm start after model changes. $\endgroup$
    – prubin
    Aug 31, 2021 at 15:08
  • 1
    $\begingroup$ Hypothetically, it should be possible (I think) to allow resumption of a search after certain model changes, with the user required to sign a digital blood oath that they are accepting the risk of getting a wrong answer and will not sue IBM, nor bad-mouth the products, if that happens. Apparently it's not a feature in great enough demand to have been implemented so far. $\endgroup$
    – prubin
    Aug 31, 2021 at 15:10
  • $\begingroup$ Thank you, I think I understand why simply removing the conditions would not work. However, this leads me to a different thought of achieving what I need. Let's say I have sets of conditions A, B and C=A∪B (variables stay the same). When I run Branch and Bound with C, I expand some but not all branches related to set A but all of the expanded branches are feasible solutions for A. If I somehow denoted in the search where I stopped expanding because of conditions from B, then if I relaxed from C to A, I could just expand the remainder losing non of the work. Is this somehow achievable in CP? $\endgroup$
    – eXPRESS
    Sep 1, 2021 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.