net.sf.cpsolver.ifs.perturbations
Class DefaultPerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>

java.lang.Object
  extended by net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter<V,T>
All Implemented Interfaces:
PerturbationsCounter<V,T>
Direct Known Subclasses:
UniversalPerturbationsCounter

public class DefaultPerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>
extends Object
implements PerturbationsCounter<V,T>

Default computation of perturbation penalty (minimal perturbation problem).

A distance function can be defined with the help of perturbations. A perturbation is a variable that has a different value in the solutions of the initial and the new problem. Some perturbations must be present in each new solution. So called input perturbation means that a variable must have different values in the initial and changed problem because of some input changes (e.g., a course must be scheduled at a different time in the changed problem). The distance function can be defined as the number of additional perturbations. They are given by subtraction of the final number of perturbations and the number of input perturbations (variables without initial assignments).

This implementation is easily extendable. It disassemble all the available cases into a comparison of the initial and the assigned value different each other. So, the only method which is needed to be changed is getPenalty(Value, Value). Its current implementation is:

It is called only when assignedValue is different to initialValue.

Version:
IFS 1.2 (Iterative Forward Search)
Copyright (C) 2006 - 2010 Tomáš Müller
muller@unitime.org
http://muller.unitime.org

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.
See Also:
Solver, Solution, Variable

Field Summary
protected static DecimalFormat sDoubleFormat
           
 
Constructor Summary
DefaultPerturbationsCounter(DataProperties properties)
          Constructor
 
Method Summary
 void getInfo(Map<String,String> info, Model<V,T> model)
          Some (perturbation) information about the solution might be returned here.
 void getInfo(Map<String,String> info, Model<V,T> model, Collection<V> variables)
          Some (perturbation) information about the solution might be returned here (only include variables from the given set).
protected  double getPenalty(T assignedValue, T initialValue)
          Computes perturbation penalty between assigned and initial value of the same lecture.
protected  double getPenaltyA(T selectedValue, T initialValue)
          Case A: initial value of a different unassigned variable cannot be assigned (computed by ViolatedInitials)
protected  double getPenaltyB(T selectedValue, T assignedValue, T initialValue)
          Case B: initial value is unassigned from a conflicting variable.
protected  double getPenaltyC(T selectedValue, T assignedValue, T initialValue)
          Case C: non-initial value is unassigned from a conflicting variable.
protected  double getPenaltyD(T selectedValue, T initialValue)
          Case D: different than initial value is assigned to the varaible
 double getPerturbationPenalty(Model<V,T> model)
          Returns perturbation penalty, i.e., the distance between current solution and the solution of the initial problem (see Variable.getInitialAssignment()).
 double getPerturbationPenalty(Model<V,T> model, Collection<V> variables)
          Returns perturbation penalty, i.e., the distance between current solution and the solution of the initial (only include variables from the given set) problem (see Variable.getInitialAssignment()).
 double getPerturbationPenalty(Model<V,T> model, T selectedValue, Collection<T> conflicts)
          Returns perturbation penalty of the solution which become from the current solution when given conflicting values are unassigned and the selected value is assigned.
protected  ViolatedInitials<V,T> getViolatedInitials()
           
 void init(Solver<V,T> solver)
          Initialization
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

sDoubleFormat

protected static DecimalFormat sDoubleFormat
Constructor Detail

DefaultPerturbationsCounter

public DefaultPerturbationsCounter(DataProperties properties)
Constructor

Parameters:
properties - input configuration
Method Detail

init

public void init(Solver<V,T> solver)
Initialization

Specified by:
init in interface PerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>

getPerturbationPenalty

public double getPerturbationPenalty(Model<V,T> model)
Description copied from interface: PerturbationsCounter
Returns perturbation penalty, i.e., the distance between current solution and the solution of the initial problem (see Variable.getInitialAssignment()).

Specified by:
getPerturbationPenalty in interface PerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
model - current model

getPerturbationPenalty

public double getPerturbationPenalty(Model<V,T> model,
                                     Collection<V> variables)
Description copied from interface: PerturbationsCounter
Returns perturbation penalty, i.e., the distance between current solution and the solution of the initial (only include variables from the given set) problem (see Variable.getInitialAssignment()).

Specified by:
getPerturbationPenalty in interface PerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
model - current model

getViolatedInitials

protected ViolatedInitials<V,T> getViolatedInitials()

getPenalty

protected double getPenalty(T assignedValue,
                            T initialValue)
Computes perturbation penalty between assigned and initial value of the same lecture. It is called only when assignedValue is different to initialValue.

Parameters:
assignedValue - value assigned to a varuable (null when variable is unassigned)
initialValue - initial value of the same varaible (always not null)

getPenaltyA

protected double getPenaltyA(T selectedValue,
                             T initialValue)
Case A: initial value of a different unassigned variable cannot be assigned (computed by ViolatedInitials)

Parameters:
selectedValue - value which is going to be assigned to its variable
initialValue - value of a different variable, which is currently assigned but which need to be unassifned Different variable, which is unassigned and whose initial value is in conflict with the selected value.

getPenaltyB

protected double getPenaltyB(T selectedValue,
                             T assignedValue,
                             T initialValue)
Case B: initial value is unassigned from a conflicting variable.

Parameters:
selectedValue - value which is going to be unassigned to its variable
assignedValue - value currently assigned to a conflicting variable (different from the one of selectedVariable)
initialValue - initial value of the conflicting variable of assignedValue

getPenaltyC

protected double getPenaltyC(T selectedValue,
                             T assignedValue,
                             T initialValue)
Case C: non-initial value is unassigned from a conflicting variable.

Parameters:
selectedValue - value which is going to be unassigned to its variable
assignedValue - value currently assigned to a conflicting variable (different from the one of selectedVariable)
initialValue - initial value of the conflicting variable of assignedValue

getPenaltyD

protected double getPenaltyD(T selectedValue,
                             T initialValue)
Case D: different than initial value is assigned to the varaible

Parameters:
selectedValue - value which is going to be unassigned to its variable
initialValue - initial value of the same variable

getPerturbationPenalty

public double getPerturbationPenalty(Model<V,T> model,
                                     T selectedValue,
                                     Collection<T> conflicts)
Description copied from interface: PerturbationsCounter
Returns perturbation penalty of the solution which become from the current solution when given conflicting values are unassigned and the selected value is assigned. Since this penalty is used for comparison of different candidate values in the value selection criterion, it is fully acceptable to just return a difference between current and the altered solution (which might be easied for computation that the whole perturbation penalty).

Specified by:
getPerturbationPenalty in interface PerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
model - current model
selectedValue - value to be selected in the next iteration
conflicts - conflicting values to be unassigned in the next iteration

getInfo

public void getInfo(Map<String,String> info,
                    Model<V,T> model)
Description copied from interface: PerturbationsCounter
Some (perturbation) information about the solution might be returned here.

Specified by:
getInfo in interface PerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
info - resultant info table
model - current model

getInfo

public void getInfo(Map<String,String> info,
                    Model<V,T> model,
                    Collection<V> variables)
Description copied from interface: PerturbationsCounter
Some (perturbation) information about the solution might be returned here (only include variables from the given set).

Specified by:
getInfo in interface PerturbationsCounter<V extends Variable<V,T>,T extends Value<V,T>>
Parameters:
info - resultant info table
model - current model