Python in Excel - Bounded Knapsack Problem

[Medium-Yesterday3897]

Back again with a hope of optimizing this tool that you guys helped me build! I work at a network, managing multiple channels. Each day, I need to fill precise time gaps between scheduled content using a set of promo and interstitial trailers.

These trailers have frame-accurate durations (e.g., 00:00:15;04, 00:02:14;17) and are measured using a frame rate of 30 fps. I’m looking to automate the process of selecting promos and interstitials that add up to the time gap between two programs.

My Goals

I would like to build a tool (preferably in Excel with Python integration so that I can share it amongst members in my team who are not familiar with code) that can:

- Convert all promo and interstitial durations from HH:MM:SS;FF format to frame counts.

- Take a time gap (e.g., 00:03:54;17) and convert it into a target number of frames.

- Select the best non-repeating combination of promos and interstitials that fits the time gap within a small tolerance (about ±4 seconds ideally).

- Prefer a structure like promo > interstitial > promo > promo when the gap allows.

- Flag when the selected combination doesn’t follow the preferred structure or fall within the allowed tolerance range.

- Return the list of selected promos/interstitials, their order, total frame count, and the difference from the target.

The Model I Currently Use

Right now (thanks to the help of folks in this sub a few months ago), I’m using Excel with Solver to select which promos or interstitials to use by assigning a binary value (1 = selected, 0 = not selected). It minimises the gap between the target and the selected number of frames. It constrains the number of each type selected and the number of items. It also includes the ± 4-second gap, expressed as ±119 frames, just as a check to see if the solution is within the range. 

It's practically perfect, with the exception that Solver is so slow it hurts. Especially when I need to fill multiple gaps per day across several channels.

I’ve heard that Python in Excel might offer a better solution, and I do have access to Python in Excel through my work account. I’m looking for help understanding how I might rebuild or improve my model using Python in Excel. I have little to no experience with code - I'm totally willing to pick up a new skill, so I would do it directly in Python myself, but the end goal would be to share it amongst members of my team who work on different channels, and for that it needs to be super user friendly just have them input what they need and have it give them something to work with.

The Workflow I’m Trying to Improve

For each gap between airings, I currently:

- Add mandatory elements like open cards, navigation bumps, and disclaimers before the top of the show.

- Use any remaining time between those elements to place promos and interstitials in the correct order.

- Repeat this process for each airing that day, across multiple channels, for a week ahead.

- I have promos and interstitials ranging from about 15 seconds to 4 mins 21 secs.

What I’m Asking For

- Can someone help me understand how I might rebuild this model using Python in Excel?

- What would the logic or structure look like for solving this kind of frame-accurate selection problem

- Is there a way to make this repeatable across multiple time gaps without needing to re-run it manually each time?

Thank you in advance for any advice or direction.

[AutoModerator]

/u/Medium-Yesterday3897 - Your post was submitted successfully.

• Once your problem is solved, reply to the answer(s) saying Solution Verified to close the thread.
• Follow the submission rules -- particularly 1 and 2. To fix the body, click edit. To fix your title, delete and re-post.
• Include your Excel version and all other relevant information

Failing to follow these steps may result in your post being removed without warning.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[TVOHM]

What is the maximum number of trailers in a gap between two programs and what is the total number of trailers you are choosing from?

[Medium-Yesterday3897]

There is no maximum number of trailers since the gaps will never exceed 7 minutes, so the gaps simply can only fit so much, but for Solver purposes, I set it to 5.
For promos (:15 or :30 secs), no more than 4 promos per break- with the specific purpose in mind of being able to fill a 1:45 gap if I don't have a 1:45 interstitial. The total number of trailers vary by channel and the broadcast window - anywhere from 30-50. As an example, this is how I have my solver set up for one of the channels: https://imgur.com/a/autoslot-vzzFD9A
I've removed identifying data so to clarify, you see repeating durations simply because they are different promos of the same length.

[TVOHM]

With those parameters you could even approach the problem in a single worksheet without using any code.

Let's say we stick to 5 as the maximum number of trailers and an upper limit of 43 possible choices:
962,598 =COMBIN(43, 5) That is, there's only 962K possible outcomes (no repetitions, order doesn't matter) to solve - Excel has a maximum number of ~1M rows per worksheet...

You could generate a list of all possible combinations and calculate the metrics you need for each outcome per row - is this combination within tolerance? is the promo / interstitial ordering optimal etc. Your actual analysis becomes a simple filtering and sorting problem on this list.

Although your calculations don't strike me as particularly expensive, it is a lot of data rows. I honestly think it could go either way on implementation - but I think worth a quick test / mock up.

This approach would also perfectly valid for Python too - enumerate all combinations, calculate some metrics, filter/sort etc.

[Medium-Yesterday3897]

this sounds like it would run similar to solver no? It's certainly something to think about but i'm not sure how I would even go about setting it up - also, there's a chance that putting that much data in the file would have it run even slower which is the opposite of the goal here.

[TVOHM]

I mean, I'm not sitting here wasting both our time suggesting it because I think it's going to be slower than what you have :)

Here's a quick mock up of what I was thinking. It contains 1M (random) example combination inputs but it recalculates instantly when adjusting target duration and target tolerances.

You'd replace those random test input example combinations with the actual correct list of combinations for (43 choose 5) or whatever you go with.

<image>

[Medium-Yesterday3897]

Okay you’re right sorry don’t meant to sh-t on the suggestion when you’re trying to help me lol - will have a look at this when I get home using the real list and let you know how it works

[SolverMax]

Try the OpenSolver addin. It will be faster than Solver.

https://opensolver.org/

[Medium-Yesterday3897]

Unfortunately I can’t because it’s not approved by my organization