Tuning of problem solvers
AssigneeMicrosoft Corporation
InventorYoussef Hamadi
Life of this patent
Estimating the term…
Abstract
It is difficult to select parameter values for constraint programming problem solvers which will yield good performance. Automated tuning of such problem solvers on a per problem instance basis may be used and this involves learning a function for predicting the runtime of a problem solver depending on parameter values of the problem solver and features of the problem instance being solved. However, it takes time for such prediction functions to be learnt, either during operation of a problem solver or offline, using specified examples. To address this, information about such a prediction function is shared between two or more problem solvers to improve performance. A sharing system may be used to receive prediction function information and send this to problem solvers.
Claims16
A method at a first constraint programming problem solver comprising:
- receiving information about a problem instance for which a potential solution is sought;
- computing features of the problem instance, the features comprising at least one of:
- a variable, a constraint between a sub-set of variables, or a binary constraint;
- receiving information about a prediction function configured to predict a runtime to find the potential solution to the problem instance from a second constraint programming problem solver, separate from the first constraint programming problem solver, the prediction function having been learned at the second constraint programming problem solver using machine learning techniques comprising at least one of:
- linear regression, ridge regression, or Bayesian linear regression;
- selecting parameter values for use by the first constraint programming problem solver on the basis of at least the computed features and the received information about the prediction function;
- and
- confirming that the first and second constraint programming problem solvers are compatible with one another.
A method at a first constraint programming problem solver comprising:
- receiving information about a problem instance for which potential solution is sought;
- computing features of the problem instance, the features comprising at least one of:
- a variable, a constraint between a sub-set of variables, or a binary constraint;
- selecting parameter values for use by the first constraint programming problem solver on the basis of at least the computed features and information about a prediction function;
- implementing a training phase, the training phase being implemented offline, on-the-fly, or by a combination of offline and on-the-fly techniques comprising:
- using the constraint programming problem solver, with the selected parameter values, to find a solution to the problem instance;
- observing an indication of difficulty for the constraint programming problem solver to find the solution;
- updating the information about the prediction function on the basis of the selected parameter values, computed features and observed indication;
- and
- repeating a user defined number of times:
- the using the constraint programming problem solver, the observing an indication of difficulty,
- and the updating the information about the prediction;
- and
- sending the updated information to at least one other problem solver confirming that the first constraint programming problem solver and a second constraint programming problem solver are compatible with one another.
One or more computer-readable storage media storing computer-executable instructions for a first constraint programming problem solver that, when executed, configures a processor to perform acts comprising:
- receiving information about a problem instance for which a potential solution is sought;
- computing features of the problem instance, the features comprising at least one of:
- a variable, a constraint between a sub-set of variables, or a binary constraint;
- receiving information about a prediction function configured to predict a runtime to find the potential solution to the problem instance from a second constraint programming problem solver, separate from the first constraint programming problem solver, the prediction function having been learned at the second constraint programming problem solver using machine learning techniques comprising at least one of:
- linear regression, ridge regression, or Bayesian linear regression;
- selecting parameter values for use by the first constraint programming problem solver on the basis of at least the computed features and the received information about the prediction function;
- implementing a training phase, the training phase being implemented offline, on-the-fly, or by a combination of offline and on-the-fly techniques comprising:
- using the constraint programming problem solver, with the selected parameter values, to find a solution to the problem instance;
- observing an indication of difficulty for the constraint programming problem solver to find the solution;
- updating the information about the prediction function on the basis of the selected parameter values, computed features and observed indication;
- and
- repeating a user defined number of times:
- the using the constraint programming problem solver, the observing an indication of difficulty, and the updating the information about the prediction;
- confirming that the first and second constraint programming problem solvers are compatible with one another;
- and
- sending the updated information to at least one other problem solver.
Dependencies are inferred from the claim text.