6
$\begingroup$

I have a MIP that runs for several different data sets. For each data set the MIP runs multiple times, once for each time period in the data set, and each time period is independent. I've experimented with grouping time periods into different sized batches to see how that affects overall run time, and I've found that the optimal batch size varies based on characteristics of the data set being utilized. For example, the more complex the data set being solved, the better it is to run time periods in smaller batches, while for simpler data sets I can run all the time periods at once in a single solve and get the fastest run time.

I have data on the total run time for each data set at various batch sizes, and I've put this info together with various statistics that describe the complexity of each data set. In theory, I'm thinking I should be able to predict the optimal batch size for a given data set based on the characteristics of that data set.

I'm trying to find a suitable algorithm for performing the above task. I've looked at regression, but the run time is highly nonlinear so using regression for prediction, in this case, does not do well. I've tried to utilize a regression tree in the hopes that it will tell me, based on the complexity of my data set, what batch size I should use. The problem I'm having with this approach is that batch size is not always selected as a splitting feature when the tree is grown. Some branches don't include batch size at all, so for some data sets the tree gives me no useful information.

Essentially, I need an algorithm that tells me what batch size to use for a given data set, with the batch size that minimizes run time being optimal. The optimal batch size seems to be a nonlinear function of some characteristics of the data set. I'm wondering about how I can go about solving this general problem, so I have a couple questions in particular:

  1. Are there other machine learning algorithms that would be better suited to this?

  2. If regression trees are one of the better ways to accomplish this, how should I force them to work for this purpose? One method I thought of would be to build a tree that excludes batch size as a variable, and then I could take the data from each leaf of that tree and build an additional regression tree on each, for which batch size is the only feature/independent variable.

Any feedback on this type of problem is appreciated.

$\endgroup$
3
$\begingroup$

Since you are already familiar with decision trees, you could try random forests.

Random forests build an ensemble of decision trees, using, for each tree, a random subset of the data and a random subset of features. Being an ensemble method, the resulting random forest is likely to be more robust and better performing than a single decision tree. In particular, with respect to the issue you mention, some trees will not consider batch size as a feature, but probably several others will, making a better prediction, and more consistently.

You can use packages for R or Python, they are easy to use and quite efficient.

| improve this answer | |
$\endgroup$
1
$\begingroup$

If the relationship is nonlinear and you don't have a feel for the right regression function, you could try support vector machine regression or neural network regression. There are packages for both in R (and I assume also in Python).

| improve this answer | |
$\endgroup$

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.