Full Text: PDF
DOI: 10.23952/cot.2027.8
Received January 14, 2026; Accepted April 30, 2026; Published online July 28, 2026
Abstract. We introduce and study decomposition methods for linear programming (LP) problems with both linking and block constraints. The methods are based on the nonlinear rescaling (NR) theory. We rescale the linking constraints into an equivalent set of constraints using scalar functions of scalar argument with particular properties. The classical Lagrangian for the equivalent problem with only linking constraints, which we call truncated Lagrangian (TL), is our main tool. Using TL, we remove the linking constraints from the entire set of constraints, which decompose the LP. Each NR decomposition (NRD) step finds approximation for the primal TL maximizer under only blocks constraints. Then the approximation is used for updating Lagrange multipliers, which correspond to the linking constraints. We call it the master problem. To find the primal TL maximizer, we use conditional or projected gradient methods applied to the TL under block constraints only. It decomposes the original LP into LPs for blocks, which are independent, have much smaller sizes and can be solved simultaneously. The critical issue is the feasibility of the linking constraints, which is achieved due to the update of the correspondent Lagrange multipliers. In fact, the master problem finds the best economic outcome for each local branch under given local resource and prices for general resources. Then, the approximation for the primal maximizer is used to correct the prices for general resources. Thus, the NRD is a pricing mechanism for finding the best outcome for an economy that has limited general and local resources. The pricing mechanism leads to such allocation of general resources that the best outcome for branches turns out to be the best outcome for the entire economy.
How to Cite this Article:
R.A. Polyak, Linear programming decomposition via nonlinear rescaling, Commun. Optim. Theory 2027 (2027) 8.