r/optimization

I’m currently finishing an optimization contest, and I’m basically done competing at this point. What frustrates me much more than the ranking is that I still don’t understand what the scalable formulation was supposed to be.

I’ll avoid posting the contest name, datasets or exact instances while it is still running, but the structure of the problem is roughly this:

• There are many models. Each model has a value and an energy cost.
• A model has requirements over up to 4 resource/data types.
• Each requirement has a lower and upper bound on the total amount of data assigned to it.
• There are many datasets, each with a type, size and a copyrighted/non-copyrighted flag.
• Each dataset can be assigned to at most one model.
• A trained model scores its full value normally, but only half its value if copyrighted data or generated data is used.
• There is a global energy budget.

The part that makes the problem much harder is the existence of generator models.

Some models with a single requirement can be trained and then used as a source for another model. Instead of satisfying one of the target model’s requirements with datasets, the generator can satisfy that whole requirement.

However:

• the generator itself scores 0,
• it still consumes energy and data to be trained,
• it can only be used once,
• generators cannot themselves be generated, so there are no chains.

The objective is to maximize total score.

My first instinct was an exact MILP / CP-SAT formulation. The problem is that the explicit assignment graph becomes enormous. On one of the large instances I end up with around 200 million compatible dataset-group / requirement edges.

At that point, explicitly representing the full assignment problem becomes completely impractical in RAM.

I tried several approaches:

• MILP / LP relaxations
• CP-SAT
• separating model selection from the final assignment
• greedy heuristics based on resource scarcity
• heuristic packing
• multi-start / randomized search
• local search
• destroy-and-repair
• several parallel search portfolios

These approaches produce decent solutions, but they still leave a noticeable gap.

The interesting part is that some competitors appear to obtain essentially the same best scores across instances that differ massively in size. That makes me suspect I completely missed a structural reformulation or decomposition that scales much better than explicitly constructing the assignment graph.

The obvious idea of precomputing all feasible dataset combinations for each model also seems hopeless, because it simply moves the combinatorial explosion from edges to feasible patterns.

So my main question is:

How would you model/decompose this problem so that the large assignment graph never has to be explicitly materialized?

Would you think in terms of:

• column generation / branch-and-price,
• Benders decomposition,
• Lagrangian relaxation,
• some form of flow formulation,
• delayed constraint/column generation,
• or something completely different?

In particular, I feel like the generator mechanism is what prevents most obvious simplifications, because model selection, data packing and generator selection become coupled.

I’m not looking for code. I mostly want to understand what abstraction I failed to see.

If anyone recognizes the underlying class of problem or has a formulation that would remain practical when going from “medium” to “very large” instances, I’d love to hear how you would approach it.

edit : The exercise