SALPMPE
Class ApproxLP

java.lang.Object
  SALPMPE.ApproxLP

public class ApproxLP
extends java.lang.Object

Defines an instance of SALP program, builds model and recovers coefficients in approximation.

Version:

2.0

Nested Class Summary

static class

ApproxLP.prob Defines the transition dynamics for the model (subclass).

Field Summary

(package private) strategy	compact Initial strategy (compact representation)
(package private) int[]	exeHi First level of differentiation in coarseness of approximation
(package private) int	exeLow Second level of differentiation in coarseness of approximation
(package private) int[]	exeMid Third level of differentiation in coarseness of approximation
(package private) java.util.Random	generator Random number generator for simulating chain evolution
(package private) int	jini Auxiliary variable (keeps track of initial simulation point)
(package private) ilog.cplex.IloCplex	model CPLEX LP model
(package private) int[][]	nodes Coarseness of linear interpolation of separable functions
(package private) ApproxLP.prob	P Transition probability class
(package private) Profit	profit Profit auxiliary array
(package private) ilog.concert.IloNumVar	v_const Model decision variable (base value)
(package private) ilog.concert.IloNumVar[][][]	v_sep Model decision variables (separable functions generalization)
(package private) ilog.concert.IloNumVar[][]	v_slack Slack variable for SALP implementation
(package private) int	xini Auxiliary variable (keeps track of initial simulation point)

Constructor Summary

ApproxLP()
Defines a new IloCplex model, loads profit function, sets coarseness of approximation and loads initial strategy.

Method Summary

state[]	allStates(sol_sep[] q_sep, double[] frecuency) Returns all states in state space, and their strategies.
void	buildModel(state[] sample, state[] altsample, double[][] exit, double[][] altexit, boolean[] constraint) Constructs and solves the approximating linear program using the sampled set of states.
boolean	CoefTaken(state[] sample, int x, int k, int n) Indicates whether a particular basis function is being covered by the set of sampled states.
boolean	CompareExit(state[] sample, sol_sep q_firm, sol_sep q_aux, int i, java.io.BufferedWriter out_sum) Compare exit strategies implied by successive LP solution and decide on convergence of LP heuristic.
double[][]	computeCoeff(int[] s, strategy Strat, int out) Computes coefficients necessary to calculate the Bellman operator.
double	ComputeV(state[] sample, sol_sep[] q_sep, java.lang.String mode, boolean[] constraint) Simulates performance of an strategy against the incumbent strategy.
double	EntryFromR(int[] s, strategy Strat, sol_sep q_sep) Computes greedy response against a solution for the approximate linear program.
void	expectedValue(int x, int[] s, strategy Strat, double pi, double exit, int sample_index) Construct the constraints for the approximate linear program associated to particular industry state.
(package private) static boolean[]	getConstraints(state[] sample, int maxSize) Limits size of sampled states used in LP formulation.
double[][]	getExit(state[] sample, sol_sep q_firm, int i) Returns exit strategy implied by LP solution.
double[][]	getmulti(int n, int k, double Pexit) Compute multinomial probabilities for possible transitions.
double[]	getmultiEntry(double Pentry, int n) Compute entry probabilities as a function of number of entrants.
double	getSlack(state[] sample, state[] altsample, boolean[] constraint) Returns value of slack variable in SALP implementation.
sol_sep	getSolution() Returns the solution to the approximate linear program.
int[]	inverseIndex(int j, double[][] Combinatorial) Index for states when dealing when small instances.
strategy	IterativeStrategy(int[] s, sol_sep[] q_sep, int period) Oracle M: Computes incumbent strategy based on previous solutions to the approximate linear programs.
void	loadCompact() Loads initial strategy from compact.txt file.
void	reduceBaseFunctions() Reduces size of approximating architecture.
void	reportMemory(int i, int n) Reports memory usage.
int	returnIndex(int[] s, double[][] Combinatorial) Returns index of a state when dealing with small instances.
state[]	sampleRest(sol_sep[] q_sep, state[] sample, boolean[] constraint) Add states to set of sampled states so that all basis functions appear in the objective function of the LP.
state[]	sampleStates(sol_sep[] q_sep, double inGamma, double obli) Sampling routine.
void	setExeNodes() Sets coarseness of approximating architecture.
double[]	StratFromR(int x, int[] s, strategy Strat, sol_sep q_sep) Computes greedy response against a solution for the approximate linear program.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

model

ilog.cplex.IloCplex model

CPLEX LP model

compact

strategy compact

Initial strategy (compact representation)

v_sep

ilog.concert.IloNumVar[][][] v_sep

Model decision variables (separable functions generalization)

v_const

ilog.concert.IloNumVar v_const

Model decision variable (base value)

v_slack

ilog.concert.IloNumVar[][] v_slack

Slack variable for SALP implementation

P

ApproxLP.prob P

Transition probability class

profit

Profit profit

Profit auxiliary array

generator

java.util.Random generator

Random number generator for simulating chain evolution

xini

int xini

Auxiliary variable (keeps track of initial simulation point)

jini

int jini

Auxiliary variable (keeps track of initial simulation point)

nodes

int[][] nodes

Coarseness of linear interpolation of separable functions

exeHi

int[] exeHi

First level of differentiation in coarseness of approximation

exeLow

int exeLow

Second level of differentiation in coarseness of approximation

exeMid

int[] exeMid

Third level of differentiation in coarseness of approximation

Constructor Detail

ApproxLP

public ApproxLP()

Defines a new IloCplex model, loads profit function, sets coarseness of approximation and loads initial strategy.

Method Detail

buildModel

public void buildModel(state[] sample,
                       state[] altsample,
                       double[][] exit,
                       double[][] altexit,
                       boolean[] constraint)

Constructs and solves the approximating linear program using the sampled set of states.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

altsample - Additional set of states that complete use of basis functions.

exit - Exit strategies for states in sample set.

altexit - Exit strategies for states in additional sample set.

constraint - indicates if a state in sample set will generate a set of constraints in the LP (limits size of LPs without affecting sampling).

reportMemory

public void reportMemory(int i,
                         int n)

Reports memory usage. Motivated by CPLEX bug. Adjust and un-comment code according to account and system specifics.

Parameters:

i - iteration count.

n - inner iteration count.

getSolution

public sol_sep getSolution()

Returns the solution to the approximate linear program.

Returns:

Solution to the approximate linear program.

getSlack

public double getSlack(state[] sample,
                       state[] altsample,
                       boolean[] constraint)

Returns value of slack variable in SALP implementation.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

altsample - Additional set of states that complete use of basis functions.

constraint - indicates if a state in sample set will generate a set of constraints in the LP (limits size of LPs without affecting sampling).

Returns:

slack variable in SALP implementation.

getExit

public double[][] getExit(state[] sample,
                          sol_sep q_firm,
                          int i)

Returns exit strategy implied by LP solution.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

q_firm - solution to LP program.

i - iteration count.

Returns:

exit strategy for states in LP formulation.

CompareExit

public boolean CompareExit(state[] sample,
                           sol_sep q_firm,
                           sol_sep q_aux,
                           int i,
                           java.io.BufferedWriter out_sum)

Compare exit strategies implied by successive LP solution and decide on convergence of LP heuristic.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

q_firm - solution to previous LP program.

q_aux - solution to current LP program.

i - iteration count.

out_sum - report file handle.

Returns:

true when exit strategies converge.

expectedValue

public void expectedValue(int x,
                          int[] s,
                          strategy Strat,
                          double pi,
                          double exit,
                          int sample_index)

Construct the constraints for the approximate linear program associated to particular industry state.

Parameters:

x - Firm quality state.

s - Competitors quality state.

strategy - Incumbent strategy followed by competitors.

pi - Profit for the incumbent firm.

exit - incumbent firm's exit strategy.

sample_index - index of current state within the sampled states.

sampleStates

public state[] sampleStates(sol_sep[] q_sep,
                            double inGamma,
                            double obli)

Sampling routine. Generates the set of states to be used to formulate the approximate linear program.

Parameters:

q_sep - History of solutions to the approximate linear programs.

inGamma - appreciation factor in transition dynamics.

obli - probability that a firm will select to use initial (compact) strategy.

Returns:

Set of sampled states to be used to formulate the approximate linear program.

sampleRest

public state[] sampleRest(sol_sep[] q_sep,
                          state[] sample,
                          boolean[] constraint)

Add states to set of sampled states so that all basis functions appear in the objective function of the LP.

Parameters:

q_sep - History of solutions to the approximate linear programs.

sample - Sampled set of states used to construct the approximating linear program.

constraint - indicates if a state in sample set will generate a set of constraints in the LP (limits size of LPs without affecting sampling).

Returns:

Set of sampled states to be used to formulate the approximate linear program.

ComputeV

public double ComputeV(state[] sample,
                       sol_sep[] q_sep,
                       java.lang.String mode,
                       boolean[] constraint)

Simulates performance of an strategy against the incumbent strategy. Used to compute the convergence criteria.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

q_sep - History of solutions to the approximate linear programs.

mode - "Base" to test incumbent strategy, "R" to test approximate best response.

constraint - indicates if a state in sample set will generate a set of constraints in the LP (limits size of LPs without affecting sampling).

Returns:

Simulated expected value function for a firm using a strategy assuming everyone else is using the incumbent strategy.

IterativeStrategy

public strategy IterativeStrategy(int[] s,
                                  sol_sep[] q_sep,
                                  int period)

Oracle M: Computes incumbent strategy based on previous solutions to the approximate linear programs.

Parameters:

s - Incumbent industry state.

q_sep - History of solutions to the approximate linear programs.

period - Iteration for which one wants to reconstruct approximate best response.

Returns:

Approximate best response strategy for specified iteration.

StratFromR

public double[] StratFromR(int x,
                           int[] s,
                           strategy Strat,
                           sol_sep q_sep)

Computes greedy response against a solution for the approximate linear program.

Parameters:

x - Firm state.

s - Competitors state.

q_sep - Solution for the approximate linear program.

Returns:

Greedy response against a solution for the approximate linear program.

EntryFromR

public double EntryFromR(int[] s,
                         strategy Strat,
                         sol_sep q_sep)

Computes greedy response against a solution for the approximate linear program.

Parameters:

s - Industry state.

strategy - industry strategy.

q_sep - Solution for the approximate linear program.

Returns:

New entry threshold based on value function approximation.

computeCoeff

public double[][] computeCoeff(int[] s,
                               strategy Strat,
                               int out)

Computes coefficients necessary to calculate the Bellman operator.

Parameters:

s - Industry state.

strategy - Strategy.

Returns:

Array of coefficients associated to each base function.

getmulti

public double[][] getmulti(int n,
                           int k,
                           double Pexit)

Compute multinomial probabilities for possible transitions.

Parameters:

n - Number of firms.

k - Quality of the firm.

exit - Exit probability.

Returns:

Array of probabilities for possible transitions.

getmultiEntry

public double[] getmultiEntry(double Pentry,
                              int n)

Compute entry probabilities as a function of number of entrants.

Parameters:

Pentry - Individual firm's entry probability.

n - number of potential entrants.

Returns:

distribution of possible entrants.

inverseIndex

public int[] inverseIndex(int j,
                          double[][] Combinatorial)

Index for states when dealing when small instances.

Parameters:

j - Index of the state.

Combinatorial - Combinatorial numbers (pre-computed for efficiency).

Returns:

Industry state associated to index j.

returnIndex

public int returnIndex(int[] s,
                       double[][] Combinatorial)

Returns index of a state when dealing with small instances.

Parameters:

s - Industry state.

Combinatorial - Combinatorial numbers (pre-computed for efficiency).

Returns:

Index associated to industry state s.

allStates

public state[] allStates(sol_sep[] q_sep,
                         double[] frecuency)

Returns all states in state space, and their strategies.

Parameters:

q_sep - History of solutions to the approximate linear programs.

frequency - sample frequency associated (uniformly) to each state.

Returns:

set of possible states in the state space with their strategies.

getConstraints

static boolean[] getConstraints(state[] sample,
                                int maxSize)

Limits size of sampled states used in LP formulation.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

maxSize - maximum number of states used in LP formulation.

Returns:

binary vector indicating if associated state is to be used when formulating the LP.

CoefTaken

public boolean CoefTaken(state[] sample,
                         int x,
                         int k,
                         int n)

Indicates whether a particular basis function is being covered by the set of sampled states.

Parameters:

sample - Sampled set of states used to construct the approximating linear program.

x - firm's quality state.

k - basis function's quality state.

n - number of firms in quality state k.

Returns:

true if basis function is being covered by the sample.

reduceBaseFunctions

public void reduceBaseFunctions()

Reduces size of approximating architecture.

setExeNodes

public void setExeNodes()

Sets coarseness of approximating architecture. customize for capacity competition model with 40 firms. Modify according to model specifics or set reducearch=false.

loadCompact

public void loadCompact()

Loads initial strategy from compact.txt file. first line contains entry threshold. next K lines contain investment decision for each quality level. next K lines contain exit thresholds for each quality level.