Polynomial-time optimization and exact separation for rational mixed-integer bipartite covers

Abstract

We give polynomial-time exact linear optimization, strong separation and membership for mixed-integer bipartite covers with arbitrary rational edge demands, unrestricted variable signs and any selected integer coordinates. All data and query points are rational in the total binary-input model; dimension and demand denominators vary. This resolves the finite rational interpretation of Conforti’s 2008 hull-membership problem. A direct specialized proximity proof localizes integer labels to intervals of length 2n and proves attainment. Exact continuous completion yields a submodular value oracle on a polynomial-size threshold lattice. A bounded-core argument establishes closedness of the actual hull and a polynomial facet-encoding bound, allowing classical optimization–separation equivalence to apply. The result is an explicit application of classical mixed proximity, discrete-convex and submodular-minimization ideas. It does not prove the separate subtree-hull conjecture or assert a compact formulation or strongly polynomial total algorithm.

The idea in plain English

A bipartite graph has two groups of vertices, with edges only between the groups. Assign a number to each vertex so that the two numbers at each edge add up to at least its prescribed demand. Some chosen vertices must receive integers; the other values may be fractional, and negative values are allowed.

The paper gives a polynomial-time method to minimize any rational linear cost under these rules, or certify that the cost can decrease without limit. It also decides exactly whether a rational point is an average of feasible assignments, including points on the boundary of that convex hull.

Large denominators are the key complication. Earlier formulations could require work proportional to a numerical common denominator, which may be exponentially larger than its binary description. Here each integer coordinate needs only a short interval of candidate values around a continuous optimum, and established submodular optimization handles the combined choices.

The contribution is a complete application and bit-complexity argument for this precise rational model. The proximity, partial-minimization and optimization–separation tools are classical and receive explicit credit; a separate conjecture about intersecting subtree hulls is not proved.

The precise result

Let U and V be disjoint vertex sets, E ⊆ U × V a finite bipartite edge set, I any subset of vertices, and b a rational demand for each edge. The feasible set is S = {x ∈ Rⁿ : x_u + x_v ≥ b_uv for uv ∈ E, x_i ∈ Z for i ∈ I}. Variables have unrestricted signs.

For every rational objective c, Theorem 1 gives an exact rational minimizer of cᵀx on S, or a feasible point and an integral improving recession direction when the objective is unbounded below. The time is polynomial in the total binary encoding of the graph, demands, objective and integer-coordinate choices. Dimension, integer-coordinate count and denominators may all vary.

The actual convex hull conv(S) is a closed rational polyhedron with a polynomially computable bound on the binary encoding of each facet inequality. Exact strong separation and membership at every rational query point, including boundary points, follow in polynomial total binary-input time.

After changing signs on one vertex class, at least one mixed optimum lies at sup-distance less than n from a continuous optimum. Integer labels consequently lie in intervals of width at most 2n. A threshold representation uses at most 2n|I| nodes and exact rational linear-programming completion values.

The finite rational interpretation of Conforti’s Problem 1 in Oberwolfach Report 51/2008 is the stated target. The result allows empty edge or integer-coordinate sets and handles the zero-dimensional case separately.

Why the result holds

Changing signs on one side of the graph turns sums into difference constraints. A signed-threshold argument moves feasible mixed assignments toward a continuous optimum without worsening their cost and proves that an optimum is attained nearby.

Fixing the short-range integer labels leaves an exact rational linear program. Its optimum value is submodular because the difference-constraint system is closed under coordinatewise minima and maxima.

Threshold nodes and implication arcs encode all feasible label choices in a polynomial-size ring family. Established submodular minimization then searches that family without enumerating every assignment or denominator residue.

A uniformly bounded mixed core plus the recession cone equals the actual convex hull. The resulting closedness and facet-encoding bound make classical exact optimization–separation applicable, including rational boundary queries.

Scope and limitations

The theorem uses explicit rational inputs and rational query points measured in binary. It does not claim an algorithm for arbitrary unencoded real data or a strongly polynomial total running time.

The graph is bipartite and the variables have unrestricted signs. The proof uses that structure to complete integer assignments and compare boundedness with the continuous relaxation; arbitrary additional constraints or bounds are not included.

Only existence of at least one nearby mixed optimum is asserted. Coordinatewise minimum/maximum closure applies after the bipartite sign change, and only constraints joining two integer coordinates are rounded upward.

The closed-hull and facet-encoding proofs do not enumerate all vertices or facets and do not supply a polynomial-size extended formulation or a facet classification. The separate subtree-hull Conjecture 2 remains unaddressed.

Classical mixed proximity, hybrid partial minimization, ring-family submodular minimization and exact optimization–separation are inherited ingredients. The note supplies the explicit rational application, denominator-independent label count and actual-hull encoding argument; exhaustive novelty and historical first priority are not certified.

The supplied exact-arithmetic checkers enumerate small cases and boundary examples. They do not implement the full polynomial-time LP, submodular-minimization and separation algorithm, and their observed runtime is not a proof of the complexity claim.

Status and AI use

AI tools were used extensively in solving, verifying, source auditing and preparation. The adversarial reviews are AI reviews. Conventional human peer review, journal acceptance and formal proof-assistant certification are not claimed.

Read the paper

Open PDF in a full window · Download the original from Zenodo

Collaborate on this result

I welcome substantive collaboration on an independent review of the rational optimization and exact separation interfaces, comparison with the discrete-convex and bipartite-cover literature, or a carefully engineered implementation. Expertise in mixed-integer optimization, submodular minimization and polyhedral complexity would be especially useful.

Authorship and responsibilities would be discussed in relation to the substantive contributions made.

Cite this paper

Alec Kriebel. (2026). Polynomial-time optimization and exact separation for rational mixed-integer bipartite covers (Version 1.0) [Preprint]. Zenodo. https://doi.org/10.5281/zenodo.23352246

Download BibTeX

Background and prior work

• Conforti, Combinatorial Mixed-Integer Programming (2008): Printed pp. 2904–2905 pose the hull-membership problem and a separate subtree-hull conjecture. This note addresses the finite rational version of Problem 1.
• Cook, Gerards, Schrijver and Tardos, Sensitivity theorems in integer linear programming: The mixed-integer proximity result in p. 258, Remarks (1), is an established predecessor. The note gives a direct specialization that also supplies attainment.
• Takamatsu, Hara and Murota, Continuous/Discrete Hybrid Convex Optimization and Its Optimality Criterion: Proposition 2 gives the prior hybrid partial-minimization mechanism; the linked text is the authors’ English translation.
• Murota, On Steepest Descent Algorithms for Discrete Convex Functions: Section 4.1 records the earlier scaling and polynomial-size ring-family lineage. The note does not claim to invent that abstract method.
• Conforti, Di Summa, Eisenbrand and Wolsey, Network Formulations of Mixed-Integer Programs: Earlier network formulations give polynomial bounds in a numerical common denominator and identify settings with short fractional-part lists.
• Conforti, Wolsey and Zambelli, Projecting an extended formulation for mixed-integer covers on bipartite graphs: The revised November 2009 author manuscript explicitly distinguishes its pseudopolynomial formulation from a binary-encoding polynomial bound.
• Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time: Section 6 supplies the ring-family interface; the current note makes its required closure data explicit and accounts for the bit cost of rational LP oracle values.
• Grötschel, Lovász and Schrijver, Geometric Algorithms and Combinatorial Optimization: The classical exact rational submodular and strong optimization–separation framework is imported, with the needed hull-description and encoding bounds established in the note.