Seeking Help with an Real-World Optimization Problem
Difference between en1 and en2, changed 12 character(s)
Hello everyone,↵

I'm currently facing an optimization problem related to server requests and would greatly appreciate your assistance. To explain the issue more clearly:↵

Problem Statement:↵
We need to send multiple tickets to a server, and our goal is to minimize the number of requests made.↵

Here's an example to illustrate the problem:↵

~~~~~↵
Request Amount↵
1+3 2↵
1+2 1↵
1+4 3↵
2+3 4↵
2+4 1↵
2+5 2↵
3+4 1↵
3+5 2↵
3+6 5↵
~~~~~↵

In this example, each request combines specific tickets with corresponding amounts. For instance, the first request (1+3) means we are attempting to send ticket 1 and ticket 3, with a total amount of 2 for each.↵

We have two methods to reduce the number of requests:↵

**1. Banker Method:**↵

Combine multiple requests into one request.↵
For example, 1>2,3,4,5 corresponds to sending (1+2), (1+3), (1+4), (1+5).↵

**2. Permutation Method:**↵

Send all possible pairs of tickets as one request.↵
For example, 1+2+3+4 corresponds to sending (1,2), (1,3), ... (3,4).↵
In the example provided, here's one possible solution:↵

~~~~~↵
Request Amount↵
1>2,3,4 1↵
1>3,4 1↵
2>3,5 2↵
3>5,6 2↵
1+4 1↵
2+3+4 1↵
3+6 3↵
2+3 1↵
~~~~~↵

This solution achieves the same total amount, preserves the amount of each ticket, and uses only 8 requests instead of 9.↵

However, I'm seeking the optimal solution, which in this case is:↵

~~~~~↵
Request Amount↵
3>1,2,5,6 1↵
3>1,2,4,5 1↵
1+2+3+4+6 1↵
2+3+5 1↵
~~~~~↵

I've attempted a greedy solution using graphs and also explored a constraint-satisfaction approach, but neither has provided the optimal solution. I believe dynamic programming might hold the key, but I'm uncertain about how to think and implement it.↵

If you have any ideas or insights to help solve this challenge, please share them with me. Your assistance is greatly appreciated.↵

For more details, the constraint is relatively small. 1<= Ticket <=10. Number of initial requests <=30. Amount <= 1k. ↵

Thank you very much for your support.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English quocdat.le.insacvl 2023-09-26 19:08:54 12
en1 English quocdat.le.insacvl 2023-09-26 19:08:23 2040 Initial revision (published)