Open Research Index

Efficient exact sequential lifting algorithm for binary knapsack set

Xintong Wang, Liang Chen, Yu-Hong Dai

arXivarxiv/2602.22640Feb 26, 2026math.OCscore 0

Lifting is a crucial technique in mixed integer programming (MIP) for generating strong valid inequalities, which serve as cutting planes to improve the branch-and-cut algorithm. We first propose an exact sequential lifting algorithm for the binary knapsack set, which employs the dominance list structure to remove redundant storage and computation in the dynamic programming (DP) array. This structure preserves scale invariance and effectively handles constraints with non-integer coefficients. Then, a reduction method is developed for the lifting procedure under some conditions, further…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2602.22640
curl -X POST /api/v1/records/arxiv/2602.22640/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.22640/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'