Timeline for Matching algorithm in an order batching problem
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 28, 2023 at 2:10 | comment | added | Ying | Right, I have tested the problem with SCIP. The formulation works, thank you. @RobPratt However, it is preferable not to rely on other third-party packages for the deployment. Therefore, I believe that dynamic programming or backtracking may be the best choice. | |
| Aug 26, 2023 at 19:19 | history | edited | Sutanu Majumdar | CC BY-SA 4.0 |
added 73 characters in body
|
| Aug 26, 2023 at 14:32 | history | edited | Sutanu Majumdar | CC BY-SA 4.0 |
added 416 characters in body
|
| Aug 26, 2023 at 14:06 | comment | added | RobPratt | No reason to introduce $z_b$ or several of the constraints. It suffices to minimize $\sum_{s,b} y_{s,b}$ subject to $\sum_b x_{o,b}=1$ for all $o$ and $\sum_o x_{o,b}\le M$ for all $b$ and $x_{o,b}\le y_{s,b}$ if $s \in S_o$. Applying Dantzig-Wolfe decomposition by batch then would yield identical blocks, leading to a column generation approach that proposes one new batch at a time. | |
| Aug 26, 2023 at 13:12 | comment | added | Ying | You inspire me. The problem seems to be a MCP. I still have some questions. In the graph, a node means an Order, en edge links two nodes mean that two orders share a common storage area. If two orders share several areas, how to explain this relationship in the graph? In this problem, if two orders have completely different areas, they may be grouped into the same batch, either, to satisfy the M constraint. However, it is impossible if two nodes have no links at all in the MCP. The MIP formulate the problem well, can we solve it with a domain spesific algorithm, instead of MIP solvers? | |
| Aug 25, 2023 at 18:16 | history | answered | Sutanu Majumdar | CC BY-SA 4.0 |