org.jorlib.frameworks.columnGeneration.master

Class AbstractMaster<T extends ModelInterface,U extends AbstractColumn<T,V>,V extends AbstractPricingProblem<T>,W extends MasterData<T,U,V,?>>

java.lang.Object

org.jorlib.frameworks.columnGeneration.master.AbstractMaster<T,U,V,W>

Type Parameters:

T - Type of data model

V - Type of pricing problem

U - Type of columns

W - Type of Master Data

All Implemented Interfaces:

BranchingDecisionListener

public abstract class AbstractMaster<T extends ModelInterface,U extends AbstractColumn<T,V>,V extends AbstractPricingProblem<T>,W extends MasterData<T,U,V,?>>
extends Object
implements BranchingDecisionListener

Main class represting the Master Problem.

Version:

13-4-2015

Author:

Joris Kinable

Field Summary

Fields

Modifier and Type	Field and Description
protected Configuration	config Configuration file for this class
protected CutHandler<T,W>	cutHandler Handle to a cutHandler which performs separation
protected T	dataModel Data model
protected org.slf4j.Logger	logger Logger for this class
protected W	masterData Data object which stores data from the Master Problem
protected OptimizationSense	optimizationSenseMaster Defines whether the master problem is a minimization or a maximization problem
protected List<V>	pricingProblems Pricing Problems

Constructor Summary

Constructors

Constructor and Description
AbstractMaster(T dataModel, List<V> pricingProblems, CutHandler<T,W> cutHandler, OptimizationSense optimizationSenseMaster) Creates a new Master Problem This implementation will invoke the buildModel() buildModel} method.
AbstractMaster(T dataModel, List<V> pricingProblems, OptimizationSense optimizationSenseMaster) Creates a new Master Problem.
AbstractMaster(T dataModel, V pricingProblem, CutHandler<T,W> cutHandler, OptimizationSense optimizationSenseMaster) Creates a new Master Problem This implementation will invoke the buildModel() buildModel} method.
AbstractMaster(T dataModel, V pricingProblem, OptimizationSense optimizationSenseMaster) Creates a new Master Problem This implementation will invoke the buildModel() buildModel} method.

Method Summary

Modifier and Type	Method and Description
abstract void	addColumn(U column) Add a column to the model
void	addColumns(List<U> columns) Add an initial solution (list of columns)
void	addCuts(Collection<AbstractInequality> cuts) Adds inequalities to this master.
void	branchingDecisionPerformed(BranchingDecision bd) Method invoked when a branching decision is executed.
void	branchingDecisionReversed(BranchingDecision bd) Method invoked when a branching decision is reversed due to backtracking in the Branch-and-Price tree.
protected abstract W	buildModel() Build the master problem
abstract void	close() Close the master problem
void	exportModel(String name) Export the master problem to a file e.g.
double	getBoundComponent() To compute a bound on the optimal solution of the relaxed master problem, multiple components are required, including information from the master problem.
Set<U>	getColumns(V pricingProblem) Returns all columns generated for the given pricing problem.
List<AbstractInequality>	getCuts() Returns all the inequalities in the master model.
int	getIterationCount() Returns the number of times the master problem has been solved
double	getObjective() Returns the objective value of the current master problem.
OptimizationSense	getOptimizationSense() Returns the optimization sense of the Master Problem (minimization or maximization).
abstract List<U>	getSolution() After the master problem has been solved, a solution has to be returned, consisting of a set of columns selected by the master problem, i.e the columns with a non-zero value.
boolean	hasNewCuts() Method which can be invoked externally to check whether the current master problem solution violates any inequalities.
abstract void	initializePricingProblem(V pricingProblem) Get the reduced cost information required for a particular pricingProblem.
boolean	isOptimal() Returns true if the master problem has been solved to optimality
abstract void	printSolution() Give a textual representation of the solution
void	solve(long timeLimit) Solve the master problem
protected abstract boolean	solveMasterProblem(long timeLimit) Method implementing the solve procedure for the master problem

Methods inherited from class java.lang.Object

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

Field Detail

logger

protected final org.slf4j.Logger logger

Logger for this class

config

protected final Configuration config

Configuration file for this class

dataModel

protected final T extends ModelInterface dataModel

Data model

pricingProblems

protected final List<V extends AbstractPricingProblem<T>> pricingProblems

Pricing Problems

masterData

protected W extends MasterData<T,U,V,?> masterData

Data object which stores data from the Master Problem

cutHandler

protected CutHandler<T extends ModelInterface,W extends MasterData<T,U,V,?>> cutHandler

Handle to a cutHandler which performs separation

optimizationSenseMaster

protected final OptimizationSense optimizationSenseMaster

Defines whether the master problem is a minimization or a maximization problem

Constructor Detail

AbstractMaster

public AbstractMaster(T dataModel,
                      List<V> pricingProblems,
                      OptimizationSense optimizationSenseMaster)

Creates a new Master Problem. This implementation will invoke the buildModel() buildModel} method. Any data members required during the execution of buildModel() buildModel} should be instantiated prior to the invocation of this constructor, or within the buildModel() buildModel} method.

Parameters:

dataModel - data model

pricingProblems - pricing problems

optimizationSenseMaster - indicates whether the Master Problem is a Minimiation or a Maximization problem

AbstractMaster

public AbstractMaster(T dataModel,
                      V pricingProblem,
                      OptimizationSense optimizationSenseMaster)

Creates a new Master Problem This implementation will invoke the buildModel() buildModel} method. Any data members required during the execution of buildModel() buildModel} should be instantiated prior to the invocation of this constructor, or within the buildModel() buildModel} method.

Parameters:

dataModel - data model

pricingProblem - pricing problem

optimizationSenseMaster - indicates whether the Master Problem is a Minimiation or a Maximization problem

AbstractMaster

public AbstractMaster(T dataModel,
                      List<V> pricingProblems,
                      CutHandler<T,W> cutHandler,
                      OptimizationSense optimizationSenseMaster)

Creates a new Master Problem This implementation will invoke the buildModel() buildModel} method. Any data members required during the execution of buildModel() buildModel} should be instantiated prior to the invocation of this constructor, or within the buildModel() buildModel} method.

Parameters:

dataModel - data model

pricingProblems - pricing problems

cutHandler - Reference to a cut handler

optimizationSenseMaster - indicates whether the Master Problem is a Minimiation or a Maximization problem

AbstractMaster

public AbstractMaster(T dataModel,
                      V pricingProblem,
                      CutHandler<T,W> cutHandler,
                      OptimizationSense optimizationSenseMaster)

Creates a new Master Problem This implementation will invoke the buildModel() buildModel} method. Any data members required during the execution of buildModel() buildModel} should be instantiated prior to the invocation of this constructor, or within the buildModel() buildModel} method.

Parameters:

dataModel - data model

pricingProblem - pricing problem

cutHandler - Reference to a cut handler

optimizationSenseMaster - indicates whether the Master Problem is a Minimiation or a Maximization problem

Method Detail

buildModel

protected abstract W buildModel()

Build the master problem

Returns:

a MasterData object

solve

public void solve(long timeLimit)
           throws TimeLimitExceededException

Solve the master problem

Parameters:

timeLimit - Future point in time by which this method must be finished

Throws:

TimeLimitExceededException - if time limit is exceeded

solveMasterProblem

protected abstract boolean solveMasterProblem(long timeLimit)
                                       throws TimeLimitExceededException

Method implementing the solve procedure for the master problem

Parameters:

timeLimit - Future point in time by which this method must be finished

Returns:

Returns true if successfull (and optimal)

Throws:

TimeLimitExceededException - if time limit is exceeded

initializePricingProblem

public abstract void initializePricingProblem(V pricingProblem)

Get the reduced cost information required for a particular pricingProblem. The pricing problem often looks like: a_1x_1+a_2x_2+...+a_nx_n <= b, where a_i are dual variables, and b some constant. The dual information is stored in the PricingProblem object.

Parameters:

pricingProblem - Object in which the dual information required to solve the pricing problems is stored.

getOptimizationSense

public OptimizationSense getOptimizationSense()

Returns the optimization sense of the Master Problem (minimization or maximization).

Returns:

the optimization sense of the Master Problem (minimization or maximization).

getObjective

public double getObjective()

Returns the objective value of the current master problem.

Returns:

objective value of master problem

getIterationCount

public int getIterationCount()

Returns the number of times the master problem has been solved

Returns:

Returns the number of times the master problem has been solved

isOptimal

public boolean isOptimal()

Returns true if the master problem has been solved to optimality

Returns:

Returns true if the master problem has been solved to optimality

hasNewCuts

public boolean hasNewCuts()

Method which can be invoked externally to check whether the current master problem solution violates any inequalities. A handle to a cutHandler must have been provided when constructing the master problem

Returns:

true if inequalities were added to the master problem, false otherwise

addCuts

public void addCuts(Collection<AbstractInequality> cuts)

Adds inequalities to this master. A handle to a cutHandler must have been provided in the constructor of this class

Parameters:

cuts - inequalities to be added

getCuts

public List<AbstractInequality> getCuts()

Returns all the inequalities in the master model. A handle to a cutHandler must have been provided in the constructor of this class

Returns:

a list of inequalities

addColumn

public abstract void addColumn(U column)

Add a column to the model

Parameters:

column - column to add

addColumns

public void addColumns(List<U> columns)

Add an initial solution (list of columns)

Parameters:

columns - initial set of columns

getColumns

public Set<U> getColumns(V pricingProblem)

Returns all columns generated for the given pricing problem.

Parameters:

pricingProblem - Pricing problem

Returns:

Set ofcolumns

getSolution

public abstract List<U> getSolution()

After the master problem has been solved, a solution has to be returned, consisting of a set of columns selected by the master problem, i.e the columns with a non-zero value.

Returns:

solution consisting of non-zero columns

getBoundComponent

public double getBoundComponent()

To compute a bound on the optimal solution of the relaxed master problem, multiple components are required, including information from the master problem. This function returns that information.

Returns:

value originating from the master problem which is required to calculate a bound on the optimal objective of the master problem

exportModel

public void exportModel(String name)

Export the master problem to a file e.g. an .lp file

Parameters:

name - Name of the exported file

printSolution

public abstract void printSolution()

Give a textual representation of the solution

close

public abstract void close()

Close the master problem

branchingDecisionPerformed

public void branchingDecisionPerformed(BranchingDecision bd)

Method invoked when a branching decision is executed.

Specified by:

branchingDecisionPerformed in interface BranchingDecisionListener

Parameters:

bd - branching decision

branchingDecisionReversed

public void branchingDecisionReversed(BranchingDecision bd)

Method invoked when a branching decision is reversed due to backtracking in the Branch-and-Price tree.

Specified by:

branchingDecisionReversed in interface BranchingDecisionListener

Parameters:

bd - branching decision