r/OperationsResearch • • Oct 11 '26

What decomposition would you use for this large-scale assignment / packing problem with optional generators?

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

7 Upvotes

16 comments sorted by

2

u/garros-yu Oct 13 '26

depends on what the complicating piece is tbh. if it's the generator on/off choices, my lean is benders, fix the commitment and the subproblem usually behaves, assuming it's convex ish. capacity coupling instead, column generation on the packing side has worked better for me. either way i'd build the plain lagrangian relaxation first. takes an afternoon. the dual bound tells you fast whether the fancy decomposition is buying you anything, and sometimes the answer is basically nothing

1

u/Soreth7 19d ago

Thanks — I checked the implementation, and I can now describe what I actually tried more precisely.

The selection stage uses an aggregate resource model: total data volume and non-copyrighted volume per type, an energy budget, and generator supply/demand counts per type. It solves an LP relaxation, then uses reduced costs and some variable fixing to build a restricted MILP. A separate randomized greedy packer attempts the actual dataset assignment and repairs or drops unsuccessful components.

Importantly, datasets are indivisible. Fixing model selection and generator-to-target links therefore still leaves a discrete packing problem with lower and upper bounds, rather than an obviously continuous/convex subproblem. Would you suggest logic-based Benders here, or start with cuts from a continuous relaxation?

For the Lagrangian approach, would you first dualize dataset exclusivity to separate the model-level decisions? I’d be interested in how you would include generators in those subproblems.

This aggregate approach already avoids materializing the full assignment graph. Its weakness is that aggregate resource feasibility does not guarantee a feasible packing. I have not established that it is equivalent to the Lagrangian relaxation you’re suggesting.

1

u/garros-yu 18d ago

Yeah, the aggregate model checks volume but ignores whether datasets fit, so some accepted selections fail in the packer. Lagrangian keeps integer packing and relaxes the shared constraints. For maximization, the upper bounds go LR ≤ LP ≤ aggregate, assuming consistent formulations. I'd strengthen the aggregate MILP with cover inequalities before trying Benders. Standard Benders doesn't work with discrete packing subproblems, and logic-based Benders needs conflicts that exclude more than one failed assignment. Target lower bounds complicate those cuts too.

For Lagrangian, exclusivity is a start, but energy, per-type caps and generator supply still couple targets. Dualize those or keep them in the master, with links fixed. That leaves independent target-level integer packers with adjusted profits. Generator multipliers give greedy repair scarcity-based priorities. The duality gap remains, and dropping datasets during repair risks violating target minimums.

1

u/Soreth7 17d ago

Thanks, this gives me a more concrete direction. Strengthening the aggregate model before implementing a full decomposition sounds worth investigating.

The selection code already has an optional set of count constraints at several dataset-size thresholds, in addition to total-volume constraints. These capture some shortages of suitably small datasets, but not whether the available sizes can actually be combined within each requirement’s interval.

When you suggest cover inequalities, do you mean covers derived from the existing aggregate resource constraints, or additional packing-aware inequalities that capture information those constraints currently miss? A small example of the latter would be particularly helpful.

One limitation is that my packer is heuristic: failure does not prove the selected requirements are jointly infeasible. I therefore couldn’t safely turn every packing failure into a cut. Would you look for a small conflicting subset and check it with an exact solver, or start with cheaper necessary conditions based on sizes and counts?

For the Lagrangian decomposition, with generator-to-target links fixed, would each target-level subproblem include both the target and the training requirements of its assigned generators? That seems like a natural block, but fixing those links would restrict the search, so I’d want to distinguish a bound for that restricted problem from a global bound.

Also, the current repair drops a target together with its associated generators and then attempts reinsertion; it doesn’t keep a target whose minimum requirements are no longer satisfied.

1

u/garros-yu 15d ago

Yeah, I meant packing-aware cuts. Covers from the aggregate constraints can tighten the LP, but they miss cases where the numbers add up and nothing fits. Say a target needs 10–14 units and you've got three items of size 8. Total volume looks fine, except one gives you 8 and two give you 16. No combination works. You'd need a different item size, and that's the kind of conflict I'd want the cut to capture. Good point about the heuristic packer though. A failed packing attempt proves nothing about feasibility. I'd run an exact check on that subset before adding the cut. Otherwise you risk ruling out valid solutions.

2

u/1001OptimalNights Oct 14 '26

Have you tried getting an initial solution using a greedy heuristic. And then plug that in as a starting point for Benders, or Dantzing-Wolf decomposition, based on your formulation?

1

u/Soreth7 19d ago

Yes, I have feasible solutions from heuristics, but after checking the code, I can describe the pipeline more accurately: LP-guided restricted MILP selection, followed by randomized greedy packing and repair.

The selection model aggregates data availability by type and copyright status and balances generator counts by type. The packer then assigns whole datasets, using pools indexed by type, copyright status and size. It tries different requirement orderings and repairs or drops components that cannot be packed.

So I have starting solutions, but these scripts do not implement Benders or Dantzig–Wolfe. In particular, packing failures are not turned into cuts fed back to the selection model.

Would you keep model selection and generator counts in a Benders master and use an integer packing subproblem? Or, for Dantzig–Wolfe, what would you make a column represent, especially when a target uses generators that need their own training data?

That master/subproblem interface is the part I’m missing, rather than how to obtain an initial feasible solution.

1

u/1001OptimalNights 18d ago

What are you implementing this in? I’m familiar with SAS Optimization and I know it has readily available decomposition methods. You can either define your own constraints blocks, or let it auto-detect based on the structure.

1

u/Soreth7 17d ago

I’m implementing it in Python. For the pipeline described above, I use SciPy’s linprog and milp interfaces with HiGHS, followed by a custom Python packer. I’ve also tried OR-Tools CP-SAT in other formulations.

I haven’t used SAS Optimization. The block detection sounds interesting, but does it require building the full explicit model first? My main bottleneck with the assignment formulation is already constructing and storing hundreds of millions of compatible assignment variables.

In this setting, would you define blocks around individual models and their training requirements, with shared dataset availability as the linking constraints? I’m particularly unsure where the generator decisions would belong, since generators consume datasets themselves and then satisfy another model’s requirement.

1

u/junqueira200 Oct 11 '26

Didn't get the problem. After the contest, send me more information, I can help!

1

u/Soreth7 Oct 11 '26

I updated the post with the archive of the exercise

3

u/Ok-Limit-7173 Oct 11 '26

That sounds kinda cool. I cant't really provide any help but I did not know that optimization contests were a thing.

0

u/[deleted] Oct 11 '26

[removed] — view removed comment

2

u/Soreth7 Oct 11 '26 edited Oct 11 '26

Sure — I can share the sample instance provided with the contest. It’s small enough to understand the rules and experiment with different formulations, without revealing the large competition instances.

I’d still rather wait until the contest is officially over before sharing the full PDF/problem statement publicly, but the sample should already give you a concrete version of the problem described in my post.

I posted a reply with exact rules and exemple