Decomposition approach for solving large-scale spatially disaggregated economic equilibrium problems

Abstract

This paper employs the Dantzig-Wolfe decomposition procedure to solve large-scale economic equilibrium problems formulated as nonlinear programs with block-diagonal linear constraints, where each block characterizes the supply possibilities in a region, and a set of unifying constraints that characterize the supply-demand balances. We derive lower and upper bounds for the value of the objective function at each step of the decomposition procedure, and use the percentage deviation between the two bounds as guidance for terminating the iterations to obtain an approximation of the equilibrium solution. Our computational results with moderate-size problems show that the decomposition procedure can reduce the solution time substantially compared to the direct solution approach without using decomposition. We present a large-scale empirical application where the impacts of the US biofuel mandates on agricultural and transportation fuel sectors were analyzed. Two powerful optimization solvers could not handle the problem due to the sheer size of the model and nonlinearity involved in the objective function, whereas we could solve the economic equilibrium successfully using the decomposition approach.

Keywords:

• Economic equilibrium
• nonlinear programming
• Dantzig-Wolfe decomposition
• US biofuel mandates

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Integrability of demand functions means that there exists a utility function from which the demand functions can be derived by utility maximization under a budget constraint (Carey, 1977; Samuelson, 1950). This is the case when the consumer demands are homogenous functions of prices and income, and cross-price derivatives of the demand functions form a symmetric matrix (Hurwicz & Uzawa, 1971).

2 Also called ‘social payoff’, defined as the total utility derived from consumption minus the total cost of production. The total utility and total cost values are given by the sum of definite integrals of the inverse demand functions and marginal cost functions, respectively, from zero to the endogenous demand quantities. When the demand and supply functions are linear, the resulting optimization model becomes a quadratic program.

3 Numerous empirical optimization studies presented in the literature assumed that the demands for individual commodities are functions of own prices only (i.e., cross-price effects are zero, thus the integrability assumption holds). This assumption is not based on econometric estimates, it is made mainly for model simplification and computational convenience purposes. Econometrically estimated demand functions usually reveal asymmetric, but relatively small cross-price effects compared to the own-price effects (see Baier et al., 2009); thus, the lack of symmetry may not impact the market equilibrium significantly. A second argument for the simplistic symmetry assumption is that inaccuracies in the data (in particular production costs and yield estimates) and aggregation errors that may occur when representing numerous producers by a small number of ‘average’ producers can be far more significant than the errors that may arise by ignoring small cross-price effects.

4 For example, Mathiesen (1985) states that “if an equilibrium problem can be posed as an optimization model, it will probably be computationally more efficient to solve it by a nonlinear programming algorithm.”

5 Nonzero cross-price effects can also be considered using the same modeling framework as long as the symmetry condition holds.

6 This characterization is consistent with agricultural production systems, for example, and has been the basis of numerous empirical price endogenous agricultural sector models.

7 See, for example, Gabriel et al. (2012).

8 For example, the Forestry and Agricultural Sector Optimization Model – FASOM (Adams et al., 1996) is used by the USDA and USEPA to analyze farm programs, renewable fuel standards, and climate change mitigation policies. See, https://www3.epa.gov/climatechange/Downloads/EPAactivities/peerreview_FASOM.pdf

9 For comprehensiveness we restate the theorem below:

Weak Duality Theorem: Consider the nonlinear programming problem $\text{Max} F\left(Y\right),\mathrm{ }\text{subject}\mathrm{ }\text{to}:\mathit{G}\left(Y\right)\le 0,\mathit{Y}\mathrm{ϵ}\mathrm{S}{\subseteq \mathbb{R}}^n,$ where $\mathit{G}=(G_i),$ and $F,G_i:{\mathbb{R}}^n\to \mathbb{R}.$ The optimum value of F is bounded above by the value of the Lagrangian dual function $H\left(\mathit{\mu }\right)={\mathrm{Sup}}_{\mathit{Y}ϵS} \left\{L\right(\mathit{Y},\mathit{\mu })=F(\mathit{Y})+\mathit{\mu }\mathit{G}(\mathit{Y})$} for any arbitrarily specified $\mathit{\lambda }=\left({\mathit{\lambda }}_{\mathit{i}}\right)\ge \mathbf{0}.$

10 Cellulosic biofuels can be produced from various feedstocks, including crop residues, forest residues, dedicated energy crops and woody biomass.

11 There are 295 CRDs in the US. An average CRD includes 9-10 counties.

12 When applying the DWD algorithm, the subproblems and the master problem were solved using GAMS/CPLEX and GAMS/MINOS, respectively.

13 By ‘optimality gap’ we mean the deviation between the upper and lower bounds obtained at each step of the decomposition procedure.

14 The GAMS code for the test problem described here (including the data) and the output file containing the SD and nonlinear DWD methods are made available as supplementary documents.

Additional information

Funding

This work was partially supported by the USDA National Institute of Food and Agriculture, CREES under Grand number ILLU05-0361 and the National Natural Science Foundation of China under Grant numbers 71822302, 71673224, and 72061147001.