[Feature Request] Optimization over high-dim discrete / combinatorial search spaces

[toshihikoyanase]

Thank you for the great library!

I'm new to Ax and trying it with simple benchmark functions. I found that the EHVI might be less effective than simple Sobol sampling when I test it with the multi-objective knapsack problem. As can be seen in the following plots, EHVI found fewer solutions. In addition, it tended to violate the constraints (objective1 < 479 and objective2 < 545) and tried to maximize the objectives.

I'm not sure, but this is partly because EHVI-based method sample the same points multiple times, and partly because it samples infeasible region. It samples -1 while the range of the parameters is 0 or 1 as follows:

Parameter definition:

parameters = [RangeParameter(f"x{i}", ParameterType.INT, lower=0, upper=1) for i in range(20)]

Log message:

[WARNING 01-21 12:06:27] ax.modelbridge.transforms.int_to_float: Unable to round {'x0': 1, 'x1': -1, 'x2': -1, 'x3': 1, 'x4': 2, 'x5': 1, 'x6': 0, 'x7': -1, 'x8': 1, 'x9': 1, 'x10': -1, 'x11': 1, 'x12': 0, 'x13': 1, 'x14': 0, 'x15': 0, 'x16': 0, 'x17': -1, 'x18': 0, 'x19': -1}to meet constraints of SearchSpace(parameters=[RangeParameter(name='x0', parameter_type=INT, range=[0, 1]), RangeParameter(name='x1', parameter_type=INT, range=[0, 1]), RangeParameter(name='x2', parameter_type=INT, range=[0, 1]), RangeParameter(name='x3', parameter_type=INT, range=[0, 1]), RangeParameter(name='x4', parameter_type=INT, range=[0, 1]), RangeParameter(name='x5', parameter_type=INT, range=[0, 1]), RangeParameter(name='x6', parameter_type=INT, range=[0, 1]), RangeParameter(name='x7', parameter_type=INT, range=[0, 1]), RangeParameter(name='x8', parameter_type=INT, range=[0, 1]), RangeParameter(name='x9', parameter_type=INT, range=[0, 1]), RangeParameter(name='x10', parameter_type=INT, range=[0, 1]), RangeParameter(name='x11', parameter_type=INT, range=[0, 1]), RangeParameter(name='x12', parameter_type=INT, range=[0, 1]), RangeParameter(name='x13', parameter_type=INT, range=[0, 1]), RangeParameter(name='x14', parameter_type=INT, range=[0, 1]), RangeParameter(name='x15', parameter_type=INT, range=[0, 1]), RangeParameter(name='x16', parameter_type=INT, range=[0, 1]), RangeParameter(name='x17', parameter_type=INT, range=[0, 1]), RangeParameter(name='x18', parameter_type=INT, range=[0, 1]), RangeParameter(name='x19', parameter_type=INT, range=[0, 1])], parameter_constraints=[ParameterConstraint(47*x0 + 22*x1 + 82*x2 + 19*x3 + 85*x4 + 15*x5 + 89*x6 + 74*x7 + 26*x8 + 11*x9 + 86*x10 + 81*x11 + 16*x12 + 35*x13 + 60*x14 + 30*x15 + 28*x16 + 94*x17 + 21*x18 + 38*x19 <= 479), ParameterConstraint(39*x0 + 24*x1 + 60*x2 + 78*x3 + 97*x4 + 97*x5 + 96*x6 + 23*x7 + 19*x8 + 17*x9 + 73*x10 + 71*x11 + 32*x12 + 67*x13 + 11*x14 + 10*x15 + 70*x16 + 91*x17 + 18*x18 + 98*x19 <= 545)])

I'm wondering whether it was expected behavior or I configured the EHVI wrongly. Here's a notebook to reproduce the experiment. Could you give me any comments about it?

[Balandat]

This is a combinatorial optimization problem, for which many of our current models / optimization approaches are not well suited. Specifically, under the hood we by perform a continuous relaxation of the integer parameters and optimize in that relaxed space using gradient-based optimization (this is where EHVI shines in more conventional problems with continuous parameters). As a result, the optimizer often ends up re-evaluating the same point, which likely results in the poor performance you're seeing.

For problems like this one generally wants to use alternative modeling and, more importantly, optimization approaches. @dme65 and @sdaulton have been working on related problems, we plan to eventually make these available in Ax as well.

[toshihikoyanase]

@Balandat Thank you for your response. I understand that the performance degradation can be expected when I apply EHVI to the combinatorial optimization including the knapsack problem. I'm looking forward to new models/optimization methods for the problem.

Can I close this issue since my question was answered. Or, should I keep it open as a tracker of the feature request?

[Balandat]

Feel free to leave it open. I'll rename it to make it more clear that this is a feature request.

[lena-kashtelyan]

We will now be tracking wishlist items / feature requests in a master issue for improved visibility: #566. Of course please feel free to still open new feature requests issues; we'll take care of thinking them through and adding them to the master issue.

[lena-kashtelyan]

Methodology for this is in-progress; we don't yet have a clear timeline, but we'll update this issue when we have one! cc @sdaulton, @dme65

[lena-kashtelyan]

Putting this back on the wishlist for now, but we are planning to open-source models for this in the long-term