5
$\begingroup$

After creating my model for a problem, what steps should I take to test if a change in the model is actually helpful or not?

In Python, print(solver.ResponseStats()) returns:

CpSolverResponse:
status: FEASIBLE
objective: 4661700
best_bound: 9876900
booleans: 108186
conflicts: 6415
branches: 3173794
propagations: 7757468
integer_propagations: 24021224
walltime: 21.7395
usertime: 21.7395
deterministic_time: 6.71619
primal_integral: 4.72458e+06

Some ideas that I have are (with a small problem instance):

  • Compare the time to solve it.
  • Compare the number of conflicts.
  • Compare the best objective bound given a time limit.
Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Some suggestions: Time to first solution (possible with some measurement in gap for quality), number of feasible solutions, the area between lower and upper bound over time (small is good) $\endgroup$
    – Simon Spoorendonk
    Feb 27, 2020 at 13:12

2 Answers 2

Reset to default
9
$\begingroup$

Time to solve (to proven optimality) is certainly a good choice. I don't know that I would be excited about number of conflicts.

You could look at the ratio of objective value on that problem instance to the best known value for that problem instance (across all model variants), given a time limit. A similar ratio of best bounds to best overall bound (by problem instance) might be useful. You could also look at the fraction of problem instances reaching proven optimality (across all problem instances, again with a common time limit) for different model variants.

Improve this answer
$\endgroup$
-1
$\begingroup$

In information theory, perplexity is a measurement of how well a probability distribution or probability model predicts a sample. It may be used to compare probability models. A low perplexity indicates the probability distribution is good at predicting the sample.

https://en.wikipedia.org/wiki/Perplexity

Improve this answer
$\endgroup$
2
  • $\begingroup$ Welcome to OR.SE! I'm not sure if this applies to my problem as it is about solving speed of a CP model... $\endgroup$
    – Stradivari
    Feb 24, 2020 at 16:26
  • $\begingroup$ It sure does, but on a lower level I guess. It calculates the entropy of your decision process (if you implement it yourself) and evaluates it in the space of your hypothesis's. In your case, if you use a framework to solve it, it would be of interest to know what kind of a problem you are mapping to the model solver. Some problems for example get intractable once the amount of instances in the problem gets larger. $\endgroup$
    – Eugen
    Mar 13, 2020 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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