Entropic Column Generation and Lehmer Branch-and-Price for Bin Packing Problem
We introduce Lehmer branch-and-price, an exact algorithm for bin packing and cutting stock problems built on the Lehmer transform, the ratio of Mellin transforms of item weights at consecutive orders. The transform maps each bin, a finite multiset of item weights, to a smooth increasing curve, and so gives the discrete problem a continuous representation on which the tools of analysis, such as convexity, exponential families and smoothing, can act. Read along this curve, the problem yields an explicit dual solution, a monotone representation of the dominance order, a family of constructive…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01251
curl -X POST /api/v1/records/arxiv/2611.01251/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01251/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'