net.sf.cpsolver.ifs.perturbations
Class DefaultPerturbationsCounter

java.lang.Object
  net.sf.cpsolver.ifs.perturbations.DefaultPerturbationsCounter

All Implemented Interfaces:

PerturbationsCounter

Direct Known Subclasses:

UniversalPerturbationsCounter

public class DefaultPerturbationsCounter
extends Object
implements PerturbationsCounter

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:

protected double getPenalty(Value assignedValue, Value initialValue) {
return 1.0;
}


It is called only when assignedValue is different to initialValue.

Version:

IFS 1.1 (Iterative Forward Search)
Copyright (C) 2006 Tomáš Müller
muller@unitime.org
Lazenska 391, 76314 Zlin, Czech Republic

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 2.1 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, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA

See Also:

Solver, Solution, Variable

Field Summary

protected static DecimalFormat

sDoubleFormat

Constructor Summary

DefaultPerturbationsCounter(DataProperties properties)
Constructor

Method Summary

void	getInfo(Dictionary info, Model model) Some (perturbation) information about the solution might be returned here.
void	getInfo(Dictionary info, Model model, Vector variables) Some (perturbation) information about the solution might be returned here (only include variables from the given set).
protected double	getPenalty(Value assignedValue, Value initialValue) Computes perturbation penalty between assigned and initial value of the same lecture.
protected double	getPenaltyA(Value selectedValue, Value initialValue) Case A: initial value of a different unassigned variable cannot be assigned (computed by ViolatedInitials)
protected double	getPenaltyB(Value selectedValue, Value assignedValue, Value initialValue) Case B: initial value is unassigned from a conflicting variable.
protected double	getPenaltyC(Value selectedValue, Value assignedValue, Value initialValue) Case C: non-initial value is unassigned from a conflicting variable.
protected double	getPenaltyD(Value selectedValue, Value initialValue) Case D: different than initial value is assigned to the varaible
double	getPerturbationPenalty(Model model) Returns perturbation penalty, i.e., the distance between current solution and the solution of the initial problem (see Variable.getInitialAssignment()).
double	getPerturbationPenalty(Model model, Value selectedValue, Collection 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.
double	getPerturbationPenalty(Model model, Vector 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()).
protected ViolatedInitials	getViolatedInitials()
void	init(Solver 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 solver)

Initialization

Specified by:

init in interface PerturbationsCounter

getPerturbationPenalty

public double getPerturbationPenalty(Model 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

Parameters:

model - current model

getPerturbationPenalty

public double getPerturbationPenalty(Model model,
                                     Vector 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

Parameters:

model - current model

getViolatedInitials

protected ViolatedInitials getViolatedInitials()

getPenalty

protected double getPenalty(Value assignedValue,
                            Value 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(Value selectedValue,
                             Value 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(Value selectedValue,
                             Value assignedValue,
                             Value 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(Value selectedValue,
                             Value assignedValue,
                             Value 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(Value selectedValue,
                             Value 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 model,
                                     Value selectedValue,
                                     Collection 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

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(Dictionary info,
                    Model model)

Description copied from interface: PerturbationsCounter

Some (perturbation) information about the solution might be returned here.

Specified by:

getInfo in interface PerturbationsCounter

Parameters:

info - resultant info table

model - current model

getInfo

public void getInfo(Dictionary info,
                    Model model,
                    Vector 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

Parameters:

info - resultant info table

model - current model