AbstractPricingProblemSolver (Java Operations Research Library)

java.lang.Object
- org.jorlib.frameworks.columnGeneration.pricing.AbstractPricingProblemSolver<T,U,V>

Type Parameters:

T - type of model data

U - type of column

V - type of pricing problem

All Implemented Interfaces:

Callable<Void>, BranchingDecisionListener
```
public abstract class AbstractPricingProblemSolver<T,U extends AbstractColumn<T,V>,V extends AbstractPricingProblem<T>>
extends Object
implements Callable<Void>, BranchingDecisionListener
```
Abstract class representing a solver for a particular pricing problem

Version:

13-4-2015

Author:

Joris Kinable

Field Summary

Fields
Modifier and Type	Field and Description
`protected List<U>`	`columns` Columns generated
`protected Configuration`	`config` Configuration file
`protected T`	`dataModel` Data model
`protected org.slf4j.Logger`	`logger` Logger for this class
`protected String`	`name` Name of the pricing problem solver
`protected double`	`objective` Objective of pricing problem (best column)
`protected V`	`pricingProblem` Pricing problem
`protected boolean`	`pricingProblemInfeasible` Boolean indicating whether the pricing problem could be solved.
`protected long`	`timeLimit` Time by which the algorithm needs to be finished.

Constructor Summary

Constructors
Constructor and Description
`AbstractPricingProblemSolver(T dataModel, V pricingProblem)` Creates a new solver instance for a particular pricing problem

Method Summary

All Methods Instance Methods Abstract Methods Concrete Methods
Modifier and Type	Method and Description
`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
`Void`	`call()` Method needed for parallelization.
`abstract void`	`close()` Close the pricing problem and perform cleanup
`protected abstract List<U>`	`generateNewColumns()` Generates one or more new columns with negative reduced cost.
`double`	`getBound()` Returns a bound on the objective of the pricing problem.
`List<U>`	`getColumns()` Returns the list of negative reduced cost columns generated by the solver
`String`	`getName()` Returns the name of the pricing problem
`double`	`getObjective()` Returns the cost of the most negative reduced cost column.
`boolean`	`pricingProblemIsFeasible()` Returns whether the pricing problem is feasible.
`protected abstract void`	`setObjective()` Method which sets the objective of the Pricing Problem.
`void`	`setTimeLimit(long timeLimit)` Set time limit (future point in time).
`protected void`	`solve()` Solves the pricing 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
  - name
```
protected String name
```
    Name of the pricing problem solver
  - dataModel
```
protected final T dataModel
```
    Data model
  - pricingProblem
```
protected final V extends AbstractPricingProblem<T> pricingProblem
```
    Pricing problem
  - timeLimit
```
protected long timeLimit
```
    Time by which the algorithm needs to be finished.
  - objective
```
protected double objective
```
    Objective of pricing problem (best column)
  - columns
```
protected List<U extends AbstractColumn<T,V>> columns
```
    Columns generated
  - pricingProblemInfeasible
```
protected boolean pricingProblemInfeasible
```
    Boolean indicating whether the pricing problem could be solved. Certain branching decisions may render the pricing problem infeasible
- Constructor Detail
  - AbstractPricingProblemSolver
```
public AbstractPricingProblemSolver(T dataModel,
                                    V pricingProblem)
```
    Creates a new solver instance for a particular pricing problem
    
    Parameters:
    
    dataModel - data model
    
    pricingProblem - pricing problem
- Method Detail
  - call
```
public Void call()
          throws Exception
```
    Method needed for parallelization. Solves the pricing problem in a separate thread
    
    Specified by:
    
    call in interface Callable<Void>
    
    Returns:
    
    Nothing
    
    Throws:
    
    Exception
  - solve
```
protected void solve()
              throws TimeLimitExceededException
```
    Solves the pricing problem. The method invokes generateNewColumns internally and stores the generated columns in an internal list.
    
    Throws:
    
    TimeLimitExceededException - TimeLimitExceededException
  - generateNewColumns
```
protected abstract List<U> generateNewColumns()
                                       throws TimeLimitExceededException
```
    Generates one or more new columns with negative reduced cost. Every solver must implement this method.
    
    Returns:
    
    List of columns with negative reduced cost
    
    Throws:
    
    TimeLimitExceededException - thrown when timelimit is exceeded
  - getName
```
public String getName()
```
    Returns the name of the pricing problem
    
    Returns:
    
    name of the solver
  - setTimeLimit
```
public void setTimeLimit(long timeLimit)
```
    Set time limit (future point in time). A TimeLimitExceededException is thrown when this time limit is exceeded.
    
    Parameters:
    
    timeLimit - future point in time (System.currentTimeMillis() + runtime)
  - getObjective
```
public double getObjective()
```
    Returns the cost of the most negative reduced cost column. If the pricing problem is an maximization problem, then any feasible solution is a lower bound.
    
    Returns:
    
    Objective value of the pricing problem.
  - setObjective
```
protected abstract void setObjective()
```
    Method which sets the objective of the Pricing Problem. This method is invoked directly *before* the generatenewColumns() method is solved. It allows the user to update the pricing solver with fresh dual information coming from the master problem. Typically this information is stored inside the PricingProblem objects.
  - getBound
```
public double getBound()
```
    Returns a bound on the objective of the pricing problem. If the pricing problem is solved to optimality, this function would typically return the objective value. Alternatively, the objective value of a relaxation of the Pricing Problem may be returned, e.g. the LP relaxation when the Pricing Problem is implemented as a MIP, or the value of a Lagrangian Relaxation.
    
    Returns:
    
    a bound on the objective of the pricing problem)
  - getColumns
```
public List<U> getColumns()
```
    Returns the list of negative reduced cost columns generated by the solver
    
    Returns:
    
    List of columns with negative reduced cost, or an empty list when no such column exists.
  - pricingProblemIsFeasible
```
public boolean pricingProblemIsFeasible()
```
    Returns whether the pricing problem is feasible. For example due to branching decisions, no feasible solution may exist for a particular pricing problem.
    
    Returns:
    
    true if a feasible solution exists to the pricing problem, or false if there is none, or none could be found in case of a heuristic pricing solver.
  - close
```
public abstract void close()
```
    Close the pricing problem and perform cleanup
  - 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

Class AbstractPricingProblemSolver<T,U extends AbstractColumn<T,V>,V extends AbstractPricingProblem<T>>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

logger

config

name

dataModel

pricingProblem

timeLimit

objective

columns

pricingProblemInfeasible

Constructor Detail

AbstractPricingProblemSolver

Method Detail

call

solve

generateNewColumns

getName

setTimeLimit

getObjective

setObjective

getBound

getColumns

pricingProblemIsFeasible

close

branchingDecisionPerformed

branchingDecisionReversed