Network format

Generalized network problems have mathematical descriptions and constraint matrices of special type. They are often much simpler than general linear programs, and the SMPS format permits input in the network format proposed by Klingman et al. [1].

The problem in this section is taken from Mulvey and Vladimirou [2]. It represents a simplified investment problem. The arcs have stochastic gains and losses, representing random investment returns. The problem has three time periods, but it is set up as a two-stage problem.

The algebraic formulation of the problem is as follows.

where:

F is the set of risky assets,

T is the set of time stages, T = {0,1,…,T},

S is the set of scenarios,

h_t(s) is the history up to (and including) period t under scenario s,

H_t is the set of all possible histories up to period t, ,

B_f are the initial holdings in asset f in F,

B_b is the initial liability,

x_ft is the transaction cost for selling one unit of asset f in period t,

h_ft is the transaction cost for buying one unit of asset f in period t,

R_ft(h_t(s)) is the rate of return for risky asset f in period t,

R_bt(h_t(s)) is the interest rate for borrowing in period t,

R_pt(h_t(s)) is the rate of return for the riskless asset purchased at time p and maturing at time t,

C_t(h_t(s)) is the cash inflow (if > 0) or outflow (if < 0) in period t under scenario s,

x_ft(h_t(s)) is the amount of risky asset f sold in period t under scenario s,

y_ft(h_t(s)) is the amount of risky asset f carried forward (held) in period t under scenario s,

u_ft(h_t(s)) is the amount of risky asset f purchased in period t under scenario s,

x_bt(h_t(s)) is the amount of liability paid back at time t under scenario s,

y_bt(h_t(s)) is the amount of liability carried forward at time t under scenario s,

u_bt(h_t(s)) is the amount of new borrowing in period t under scenario s,

v_pt(h_t(s)) is the amount of riskless asset purchased at time p and maturing at time t under scenario s,

z_ft(h_t(s)) are the holdings in asset f after the portfolio revision of stage t under scenario s,

z_bt(h_t(s)) is the amount of debt after the portfolio revision of stage t under scenario s,

w(s) is the net wealth at the end of the horizon in scenario s,

p_s is the probability that scenario s occurs.

This problem can also be represented by a generalized network, as follows.

Time file

Core file

Stoch file

References

1. D. Klingman, A. Napier and J. Stutz, “NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems”, Management Science 20 (1974) 814–821.

2. J.M. Mulvey and H. Vladimirou, “Stochastic network optimization models for investment planning”, Annals of Operations Research 20 (1989) 187–217.