Column Generation is a very useful approach to solve large-scale linear programming problems. This is the column generation framework that I developed during my Ph.D study, written in OPL. Interested readers are encouraged to see Column Generation.
This source is published under MIT licence. If you use it, it is very appreciate to drop me a few lines.
-
model.ini: define states that will be loaded. Each line is formatted as MODEL "NAME" "modelxxx.mod" [relax]. If parameter relax appears, then the model is relaxed when it is solved.
-
params.mod: contain the definition of your data. sysmsg.mod need to be included in this file. The definition of the data as well as the data itself are available to all loaded states.
-
params.dat: define some parameters or initialize some variables used in the program.
The following paragraphs give more information.
oplrun -D input="datafile" -D output="resultfile" [path-to]/solver.mod in your directory.
Actually, the program is just a state machine. At the initial step, it loads a list of states from model.ini, each state is assigned to an OPL model. First, the program starts processing a special state named ROOT. The state will decide which is the next state to be solved. It can also return empty state which means the process is finished. The overall optimization process is described as follows.
load states from model.ini
state = ROOT
while state != empty
state = empty
if solving( state.model )
state = solving.nextmodel
There is only one predefined state:
Model ROOT: will be called first
otherwise, you can create whatever state you want. Notice that each state must define by itself the next state to be solved. The final state is responsible to compute the GAP and other metrics by it own. The system provides the following state-related functions that can be used inside each model:
- isModel( X ) = true if the current solving model is X, false otherwise.
- getModel() : return the current model.
- setNextModel( X ): set X the next model to be solved. Parameter is undefined.
- setModelStatus( s ): if s > 0 then display infos of the solving process of each model after it is solved, otherwise do nothing.
Extra functions:
-
GAP( X , Y ) : return difference in percentage between X and Y in comparison to X.
-
timeMarker() : return the current time object.
-
elapsedTime( marker ): calculate the elapsed time from marker in seconds.
-
AVATAR() : return signature of the program.
-
lineSep( label , sep ): display a line of sep with label in middle on screen.
-
leftWrite( st , len ) : display a string with length len on screen with st aligned to the left.
-
rightWrite( st , len) : display a string with length len on screen with st aligned to the right.
-
maxLength( n , st ) : return MAX( n , len( st ) ).
-
assertExisted( name ) : check if file name existed or not.
-
getPWDPath() : return the directory where you are standing.
The output file has INI format for which the following functions are provided:
- empty_output(): clear the output.
- output_section( txt ): start writing new Section txt.
- output_value( param , value ): write Param param with Value value to the output.