Research map / Learning theory and algorithms / Combinatorial and search optimization
Partial Optimality in the Linear Ordering Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives efficiently testable partial optimality conditions (transposition, grouping, conditional grouping, shifting, generalized shifting) for the linear ordering problem via improving maps, and uses them to fix variables and speed up a Gurobi branch-and-cut solver on synthetic and LOLIB instances.
Problem
The linear ordering problem is NP-hard and APX-hard; the task is to efficiently decide, for some pairs (a,b), whether a < b holds in some optimal solution without solving the whole problem.
Approach
Constructs improving maps on the feasible set of linear orders (transposition, grouping, conditional grouping, shifting, generalized shifting) and derives cost-based sufficient conditions under which these maps imply partial optimality of variable assignments, testable via enumeration or min-cut.
Key results
- On LOLIB IO instances, partial optimality reduces branch-and-cut time by up to a factor of 13.18; on Spec, up to 33.74.
- Between 10% and 90% of variables are fixed for IO instances, 0% to 70% for Spec, and about 3% for SGB.
- On synthetic instances, nearly all variables are fixed at alpha=0.4 and nearly none at alpha=1.0; runtime does not exceed four minutes for n=200.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply partial optimality conditions before branch-and-cut | Branch-and-cut for the linear ordering problem · LOLIB IO | speed-up: 13.18; 0.77 | Mixed |
| Apply partial optimality conditions before branch-and-cut | Branch-and-cut for the linear ordering problem · LOLIB Spec instances solvable within 60 minutes | speed-up: 33.74; 0.69 | Mixed |
| Apply partial optimality conditions before branch-and-cut | Branch-and-cut for the linear ordering problem · Synthetic instances, α = 0.65 | speed-up: about 3 to 4 | Helped |
| Apply partial optimality conditions before branch-and-cut | Branch-and-cut for the linear ordering problem · Synthetic instances, α = 0.7 | speed-up: about 1 to 3 | Helped |
| Test Proposition 4.8 separately (ablation) | Partial optimality algorithm · Synthetic instances | fixed variables | Helped |
| Test Proposition 4.4 separately (ablation) | Partial optimality algorithm · Synthetic instances | fixed variables | Helped |
| Test Proposition 4.11 separately (ablation) | Partial optimality algorithm · Synthetic instances | fixed variables | Helped |
| Use Proposition 4.11 instead of Proposition 4.8 for separate testing (ablation) | Partial optimality algorithm · Synthetic instances | runtime: three orders of magnitude longer | Hurt |
Surprising findings
- Partial optimality conditions from different propositions need not hold simultaneously (Example 2), and the grouping and conditional-grouping conditions cannot always be combined.
- The conditional grouping condition (Prop. 4.11) fixes at least as many variables as grouping (Prop. 4.8) but takes about three orders of magnitude longer to test.
Limitations
- Conditions fix only a fraction of variables; SGB instances fix only about 3%.
- Conditional grouping testing is costly (about three orders of magnitude slower than grouping).
- Partial optimality conditions from some propositions cannot be applied simultaneously.
Experimental setup
Datasets: LOLIB (IO, Spec, SGB) synthetic linear ordering instances
Benchmarks: LOLIB IO LOLIB Spec LOLIB SGB synthetic instances
Metrics: percentage of fixed variables runtime speed-up of branch-and-cut
Baselines: Gurobi branch-and-cut without partial optimality
Builds on: improving maps (Shekhovtsov 2013) partial optimality for correlation clustering (Lange et al. 2018)
Closest papers by meaning
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.83)
- Linear Equations with Min and Max Operators: Computational Complexity (AAAI 2025 · similarity 0.82)
- Active Set Ordering (NeurIPS 2024 · similarity 0.82)
- Are Greedy Task Orderings Better Than Random in Continual Linear Regression? (NeurIPS 2025 · similarity 0.82)
- On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition (ICML 2024 · similarity 0.81)
- Approximation algorithms for combinatorial optimization with predictions (ICLR 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.