d4-conf-ecai-2023-0097 (d4-conf-ecai-2023-0097)

Given vehicle types \(r=1,\ldots,\tau\) with fleet masses \(\mu_r\), \(k\) charging stations, a fixed station-mass profile \(q_1,\ldots,q_k\) with \(\sum_j q_j=1\), and rational workload coefficients \(h_{rj}\), choose allocations \(x_{rj}\geq 0\) satisfying \(\sum_j x_{rj}=\mu_r\) and \(\sum_r x_{rj}=q_j\) to minimize the maximum station workload \(\max_j \sum_r h_{rj}x_{rj}\).

A society is given by its support: the list of \(\tau\geq1\) vehicle types with positive masses \(\mu_r\) encoded as binary rationals, with \(\sum_r\mu_r=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m=k\geq1\) labeled charging stations. The input includes binary rational station masses \(q_j\geq0\), with \(\sum_jq_j=1\), and finite nonnegative rational workload coefficients \(h_{rj}\), already incorporating charging time and station capacity. Empty stations are allowed.
Mass may be split arbitrarily: choose real allocations \(x_{rj}\geq0\) satisfying \(\sum_jx_{rj}=\mu_r\) and \(\sum_rx_{rj}=q_j\). The objective is to minimize \(\max_j\sum_rh_{rj}x_{rj}\); there is no secondary objective. Let \(L\) be the total binary input length.

Is exact minimization of the maximum station workload solvable in time polynomial in \(m=k\), \(\tau\), and \(L\), or is it NP-hard?

For discrete agents, PISA has a stated \(O(n^4k^2)\) search bound for one prescribed ordered coalition-size profile; it samples that profile and does not guarantee its optimum. [Source](https://journals.sagepub.com/doi/pdf/10.3233/FAIA230527)
No result settling this exact continuous problem was located in the literature search.

Proven claim. Exact minimization is solvable in time polynomial in \(m=k\), \(\tau\), and \(L\). Both the optimal value and an optimal allocation can be returned as binary rationals.

1. Feasibility and attainment. Let
\[ \mathcal X=\left\{x\in\mathbb R_{\geq0}^{\tau\times m}: \sum_{j=1}^{m}x_{rj}=\mu_r\ \text{for every }r,\quad \sum_{r=1}^{\tau}x_{rj}=q_j\ \text{for every }j \right\}. \]
This set is nonempty: \(x_{rj}=\mu_rq_j\) satisfies both families of equalities because both mass vectors sum to \(1\).

Every feasible coordinate satisfies \(0\leq x_{rj}\leq\mu_r\leq1\). Thus \(\mathcal X\) is closed and bounded, hence compact. The function
\[ W(x)=\max_{1\leq j\leq m}\sum_{r=1}^{\tau}h_{rj}x_{rj} \]
is continuous, being the maximum of finitely many linear functions. Consequently its minimum is attained.

Set \(H=\max_{r,j}h_{rj}\). For every feasible allocation and every station,
\[ 0\leq\sum_{r=1}^{\tau}h_{rj}x_{rj} \leq H\sum_{r=1}^{\tau}x_{rj} =Hq_j\leq H. \]
In particular, \(0\leq W(x)\leq H\), including when \(H=0\).

2. Exact linear-programming formulation. Introduce one real variable \(t\) and consider
\[ \begin{aligned} \text{minimize}\quad &t\\ \text{subject to}\quad &\sum_{j=1}^{m}x_{rj}=\mu_r &&(1\leq r\leq\tau),\\ &\sum_{r=1}^{\tau}x_{rj}=q_j &&(1\leq j\leq m),\\ &\sum_{r=1}^{\tau}h_{rj}x_{rj}\leq t &&(1\leq j\leq m),\\ &x_{rj}\geq0 &&(1\leq r\leq\tau,\ 1\leq j\leq m),\\ &0\leq t\leq H. \end{aligned} \]

For every \(x\in\mathcal X\), the pair \((x,W(x))\) is feasible for this program. Conversely, every feasible pair satisfies \(x\in\mathcal X\) and \(W(x)\leq t\). These two implications prove that the program’s optimal value equals \(\min_{x\in\mathcal X}W(x)\).

Moreover, if \((x^*,t^*)\) is an optimal solution, then
\[ \min_{x\in\mathcal X}W(x)\leq W(x^*)\leq t^* =\min_{x\in\mathcal X}W(x). \]
Hence \(x^*\) solves the original problem exactly.

Empty stations cause no difficulty: if \(q_j=0\), nonnegativity and the column-sum equality force every \(x_{rj}=0\), so that station’s workload is zero.

3. Polynomial complexity and exactness. We use the rational linear-programming theorem: a linear program with binary rational data can be solved in polynomial time in its total encoding length; when feasible with a finite optimum, an exact rational optimal solution can be produced. This is the standard bit-complexity result of [Khachiyan, *Polynomial algorithms in linear programming*](https://www.mathnet.ru/eng/zvmmf5239).

All its hypotheses hold here:

• There are \(\tau m+1\) variables and \(O(\tau m+\tau+m)\) constraints, counting nonnegativity and replacing equalities by pairs of inequalities.
• Every coefficient belongs to the input or is one of \(0,1,-1\); \(H\) is an input coefficient selected by rational comparisons.
• Consequently, the total LP encoding length \(S\) is polynomial in \(m,\tau,L\), even with a dense encoding.
• The feasible region is nonempty and compact by the preceding bounds, so the optimum is finite and attained.

Exact output also has polynomial length. To see this directly, choose an optimal vertex of the feasible polytope and put \(N=\tau m+1\). Its coordinates solve a nonsingular system of \(N\) tight constraints. Clearing denominators in each selected equation produces integer entries of magnitude at most \(2^{O(S)}\). Cramer’s rule and Hadamard’s determinant bound then give numerator and denominator bit lengths \(O(N(S+\log N))\) for every coordinate. This establishes polynomial output size; the cited theorem supplies the polynomial-time algorithm to find it.

Thus exact continuous optimization is polynomial-time solvable for every prescribed station-mass vector. The discrete PISA search bound is unnecessary for this conclusion. Under standard polynomial-time reductions, NP-hardness of the associated threshold decision problem would therefore imply \(\mathrm P=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover resolves the assigned problem correctly. The linear program models the continuous objective exactly, has polynomial encoding length, and falls within the stated exact rational linear-programming theorem. No major or minor mathematical issues were found.

• Feasibility and attainment. The proposed allocation \(x_{rj}=\mu_rq_j\) is nonnegative and satisfies both prescribed marginals using their normalization. The coordinate bound \(0\leq x_{rj}\leq\mu_r\leq1\) is valid. The constraints define a closed set in a finite-dimensional space, so boundedness establishes compactness. The objective is continuous because it is a finite maximum of linear functions. Attainment therefore follows correctly.

• Workload bounds. The maximum \(H=\max_{r,j}h_{rj}\) exists because both index sets are nonempty and all coefficients are finite. Nonnegativity gives the lower bound, while \(h_{rj}\leq H\) and the column-sum constraint give the upper bound \(Hq_j\leq H\). These bounds remain valid when \(H=0\).

• Exact equivalence of the linear program. Each feasible original allocation extends to the feasible pair \((x,W(x))\). Conversely, the workload inequalities imply \(W(x)\leq t\) for every feasible LP pair. Together, these establish equality of the optimal values. The displayed inequality chain also correctly establishes that the allocation component of any optimal LP solution is optimal for the original objective. No secondary objective or restriction on splitting has been introduced.

• Empty stations and boundary cases. If \(q_j=0\), a sum of nonnegative allocations equaling zero forces every allocation in that column to vanish. Its workload is consequently zero. The arguments also cover \(m=1\), \(\tau=1\), and all-zero workload coefficients. Redundant marginal equalities do not invalidate the formulation or the LP theorem.

• Polynomial encoding and construction. The variable count \(\tau m+1\) and the stated constraint bound are correct. Replacing equalities by paired inequalities requires only sign changes. Thus the assertion that coefficients come from the input or are \(0,1,-1\) is correctly understood before that conversion; conversion does not increase coefficient lengths materially. Selecting \(H\) by exact rational comparisons takes polynomial time. Both the dense LP encoding and its construction have size polynomial in \(m,\tau,L\).

• Application of the rational LP theorem. The prover states the required theorem with the relevant encoding model and exact-output guarantee. Its hypotheses are satisfied: the data are rational, the formulation is explicitly finite, and its feasible region is nonempty and bounded. Lower-dimensional feasible regions and zero coefficients require no additional hypothesis. The invoked exact polynomial-time LP result is standard; exact rational recovery and the bit-length interpretation are also described in [Trevisan’s linear-programming lecture, Sections 2.4–2.5](https://lucatrevisan.github.io/cs261/lecture05.pdf). This is verification of the theorem invoked, rather than an additional argument repairing the proof.

• Rational output size. A linear objective on a nonempty compact polytope has an optimal vertex. At such a vertex, \(N=\tau m+1\) independent tight constraints determine the coordinates, including when the polytope is lower-dimensional. Clearing denominators includes the right-hand sides and yields the claimed integer-entry bound. Cramer’s rule and Hadamard’s inequality then give the stated coordinate bit-length bound \(O(N(S+\log N))\). Zero coordinates pose no denominator problem because the selected system is nonsingular. The bound is polynomial, and the prover correctly distinguishes output-size existence from the algorithmic guarantee supplied by the LP theorem.

• Final complexity conclusion. The result concerns the prescribed station-mass vector in the task and establishes exact polynomial-time computation of both the value and an allocation. The discrete PISA bound is unnecessary. The conditional statement about NP-hardness is also correct under standard polynomial-time reductions: the associated rational-threshold decision problem is in \(\mathrm P\).

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩