edu.illinois.cs.cogcomp.lbjava.infer

Class BalasHook

java.lang.Object

edu.illinois.cs.cogcomp.lbjava.infer.ZeroOneILPProblem

edu.illinois.cs.cogcomp.lbjava.infer.BalasHook

All Implemented Interfaces:

edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

public class BalasHook
extends ZeroOneILPProblem
implements edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

This ILPSolver implements Egon Balas' zero-one ILP solving algorithm. It is a branch and bound algorithm that can return the best solution found so far if stopped early. For more information on the original algorithm, see

E. Balas. 1965. An Additive Algorithm for Solving Linear Programs with Zero-One Variables. Operations Research, 13(4):517–546.

Author:

Nick Rizzolo

Field Summary

Fields

Modifier and Type	Field and Description
protected boolean	first Whether or not the algorithm will halt upon finding its first feasible solution.
protected int	verbosity Verbosity level.

Fields inherited from class edu.illinois.cs.cogcomp.lbjava.infer.ZeroOneILPProblem

Ac, Av, bounds, boundTypes, boundTypeSymbols, EQUALITY, GREATER_THAN, LESS_THAN, maximize, objectiveCoefficients, TOLERANCE

Fields inherited from interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

VERBOSITY_HIGH, VERBOSITY_LOW, VERBOSITY_NONE

Constructor Summary

Constructors

Constructor and Description
BalasHook() Default constructor.
BalasHook(boolean f) Creates a new ILP solver that halts at the first feasible solution found, if the parameter to this constructor is true.
BalasHook(boolean f, int v) Creates a new ILP solver that halts at the first feasible solution found, if the first parameter to this constructor is true.
BalasHook(int v) Creates a new ILP solver with the specified verbosity.
BalasHook(String name) Creates a new ILP solver with the problem represented in the named file loaded and ready to solve.
BalasHook(String name, boolean f) Creates a new ILP solver with the problem represented in the named file loaded and ready to solve.
BalasHook(String name, boolean f, int v) Creates a new ILP solver with the problem represented in the named file loaded and ready to solve.
BalasHook(String name, int v) Creates a new ILP solver with the problem represented in the named file loaded and ready to solve.

Method Summary

Modifier and Type	Method and Description
protected void	addConstraint(int[] i, double[] a, int t, double b) Simply overrides ZeroOneILPProblem.addConstraint(int[],double[],int,double) so that it calls ZeroOneILPProblem.addConstraint(int[],double[],double) thereby ignoring the constraint's type.
void	addEqualityConstraint(int[] i, double[] a, double b) Adds a new fixed constraint to the problem.
void	addGreaterThanConstraint(int[] I, double[] a, double b) Adds a new lower bounded constraint to the problem.
int	addIntegerVariable(double c)
void	addLessThanConstraint(int[] i, double[] a, double b) Adds a new upper bounded constraint to the problem.
int	addRealVariable(double c)
boolean	getBooleanValue(int index) When the problem has been solved, use this method to retrieve the value of any Boolean inference variable.
int	getIntegerValue(int index)
double	getRealValue(int index)
boolean	isSolved() Tests whether the problem represented by this ILPSolver instance has been solved already.
double	objectiveValue() When the problem has been solved, use this method to retrieve the value of the objective function at the solution.
void	reset() This method clears the all constraints and variables out of the ILP solver's problem representation, bringing the ILPSolver instance back to the state it was in when first constructed.
void	setFirst(boolean f) Sets the value of first.
boolean	solve() Solves the ILP problem, saving the solution internally.
boolean	solve(double z) Implements the meat of the Balas algorithm recursively.
void	write(StringBuffer buffer) Creates a textual representation of the ILP problem in an algebraic notation.

Methods inherited from class edu.illinois.cs.cogcomp.lbjava.infer.ZeroOneILPProblem

addBooleanVariable, addConstraint, addDiscreteVariable, addDiscreteVariable, columns, constraintsSatisfied, evaluate, getBoundType, getConstraintBound, getConstraintCoefficient, getMaximize, getObjectiveCoefficient, rows, setBoundType, setConstraintBound, setConstraintCoefficient, setMaximize, setObjectiveCoefficient, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

addBooleanVariable, addDiscreteVariable, setMaximize

Field Detail

first

protected boolean first

Whether or not the algorithm will halt upon finding its first feasible solution.

verbosity

protected int verbosity

Verbosity level. ILPInference.VERBOSITY_NONE produces no incidental output. If set to ILPInference.VERBOSITY_LOW, only variable and constraint counts are reported on STDOUT. If set to ILPInference.VERBOSITY_HIGH, a textual representation of the entire optimization problem is also generated on STDOUT.

Constructor Detail

BalasHook

public BalasHook()

Default constructor.

BalasHook

public BalasHook(int v)

Creates a new ILP solver with the specified verbosity.

Parameters:

v - Setting for the verbosity level.

BalasHook

public BalasHook(boolean f)

Creates a new ILP solver that halts at the first feasible solution found, if the parameter to this constructor is true.

Parameters:

f - Whether or not to stop at the first feasible solution.

BalasHook

public BalasHook(boolean f,
                 int v)

Creates a new ILP solver that halts at the first feasible solution found, if the first parameter to this constructor is true.

Parameters:

f - Whether or not to stop at the first feasible solution.

v - Setting for the verbosity level.

BalasHook

public BalasHook(String name)

Creates a new ILP solver with the problem represented in the named file loaded and ready to solve. The constraints in the problem are assumed to all be "less than or equal to" constraints, and the actual (in)equality symbol is ignored during parsing.

Parameters:

name - The name of the file containing the textual representation of a 0-1 ILP problem.

BalasHook

public BalasHook(String name,
                 boolean f)

Creates a new ILP solver with the problem represented in the named file loaded and ready to solve. The constraints in the problem are assumed to all be "less than or equal to" constraints, and the actual (in)equality symbol is ignored during parsing.

Parameters:

name - The name of the file containing the textual representation of a 0-1 ILP problem.

f - Whether or not to stop at the first feasible solution.

BalasHook

public BalasHook(String name,
                 int v)

Creates a new ILP solver with the problem represented in the named file loaded and ready to solve. The constraints in the problem are assumed to all be "less than or equal to" constraints, and the actual (in)equality symbol is ignored during parsing.

Parameters:

name - The name of the file containing the textual representation of a 0-1 ILP problem.

v - Setting for the verbosity level.

BalasHook

public BalasHook(String name,
                 boolean f,
                 int v)

Creates a new ILP solver with the problem represented in the named file loaded and ready to solve. The constraints in the problem are assumed to all be "less than or equal to" constraints, and the actual (in)equality symbol is ignored during parsing.

Parameters:

name - The name of the file containing the textual representation of a 0-1 ILP problem.

f - Whether or not to stop at the first feasible solution.

v - Setting for the verbosity level.

Method Detail

setFirst

public void setFirst(boolean f)

Sets the value of first.

reset

public void reset()

This method clears the all constraints and variables out of the ILP solver's problem representation, bringing the ILPSolver instance back to the state it was in when first constructed.

Specified by:

reset in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Overrides:

reset in class ZeroOneILPProblem

addConstraint

protected void addConstraint(int[] i,
                             double[] a,
                             int t,
                             double b)

Simply overrides ZeroOneILPProblem.addConstraint(int[],double[],int,double) so that it calls ZeroOneILPProblem.addConstraint(int[],double[],double) thereby ignoring the constraint's type. Overriding this method in this way ensures that types are not stored when reading in a textual problem representation, as happens when constructing an instance with BalasHook(String).

Overrides:

addConstraint in class ZeroOneILPProblem

Parameters:

i - The indexes of the variables with non-zero coefficients.

a - The coefficients of the variables with the given indexes.

t - The type of comparison in this constraint.

b - The new constraint will enforce equality with this constant.

addRealVariable

public int addRealVariable(double c)

Specified by:

addRealVariable in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

addIntegerVariable

public int addIntegerVariable(double c)

Specified by:

addIntegerVariable in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

addEqualityConstraint

public void addEqualityConstraint(int[] i,
                                  double[] a,
                                  double b)

Adds a new fixed constraint to the problem. The two array arguments must be the same length, as their elements correspond to each other. Variables whose coefficients are zero need not be mentioned. Variables that are mentioned must have previously been added via ZeroOneILPProblem.addBooleanVariable(double) or ZeroOneILPProblem.addDiscreteVariable(double[]). The resulting constraint has the form:

xi * a = b

where xi represents the inference variables whose indexes are contained in the array i and * represents dot product.

Specified by:

addEqualityConstraint in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Overrides:

addEqualityConstraint in class ZeroOneILPProblem

Parameters:

i - The indexes of the variables with non-zero coefficients.

a - The coefficients of the variables with the given indexes.

b - The new constraint will enforce equality with this constant.

addGreaterThanConstraint

public void addGreaterThanConstraint(int[] I,
                                     double[] a,
                                     double b)

Adds a new lower bounded constraint to the problem. The two array arguments must be the same length, as their elements correspond to each other. Variables whose coefficients are zero need not be mentioned. Variables that are mentioned must have previously been added via ZeroOneILPProblem.addBooleanVariable(double) or ZeroOneILPProblem.addDiscreteVariable(double[]). The resulting constraint has the form:

xi * a >= b

where xi represents the inference variables whose indexes are contained in the array i and * represents dot product.

Specified by:

addGreaterThanConstraint in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Overrides:

addGreaterThanConstraint in class ZeroOneILPProblem

Parameters:

I - The indexes of the variables with non-zero coefficients.

a - The coefficients of the variables with the given indexes.

b - The lower bound for the new constraint.

addLessThanConstraint

public void addLessThanConstraint(int[] i,
                                  double[] a,
                                  double b)

Adds a new upper bounded constraint to the problem. The two array arguments must be the same length, as their elements correspond to each other. Variables whose coefficients are zero need not be mentioned. Variables that are mentioned must have previously been added via ZeroOneILPProblem.addBooleanVariable(double) or ZeroOneILPProblem.addDiscreteVariable(double[]). The resulting constraint has the form:

xi * a <= b

where xi represents the inference variables whose indexes are contained in the array i and * represents dot product.

Specified by:

addLessThanConstraint in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Overrides:

addLessThanConstraint in class ZeroOneILPProblem

Parameters:

i - The indexes of the variables with non-zero coefficients.

a - The coefficients of the variables with the given indexes.

b - The upper bound for the new constraint.

solve

public boolean solve()
              throws Exception

Solves the ILP problem, saving the solution internally.

Specified by:

solve in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Returns:

true iff a solution was found successfully.

Throws:

Exception

solve

public boolean solve(double z)

Implements the meat of the Balas algorithm recursively.

Parameters:

z - The value of the objective function with the current variable settings.

Returns:

true iff a solution was found successfully.

isSolved

public boolean isSolved()

Tests whether the problem represented by this ILPSolver instance has been solved already.

Specified by:

isSolved in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

getBooleanValue

public boolean getBooleanValue(int index)

When the problem has been solved, use this method to retrieve the value of any Boolean inference variable. The result of this method is undefined when the problem has not yet been solved.

Specified by:

getBooleanValue in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Parameters:

index - The index of the variable whose value is requested.

Returns:

The value of the variable.

getIntegerValue

public int getIntegerValue(int index)

Specified by:

getIntegerValue in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

getRealValue

public double getRealValue(int index)

Specified by:

getRealValue in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

objectiveValue

public double objectiveValue()

When the problem has been solved, use this method to retrieve the value of the objective function at the solution. The result of this method is undefined when the problem has not yet been solved. If the problem had no feasible solutions, negative (positive, respectively) infinity will be returned if maximizing (minimizing).

Specified by:

objectiveValue in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Returns:

The value of the objective function at the solution.

write

public void write(StringBuffer buffer)

Creates a textual representation of the ILP problem in an algebraic notation.

Specified by:

write in interface edu.illinois.cs.cogcomp.infer.ilp.ILPSolver

Overrides:

write in class ZeroOneILPProblem

Parameters:

buffer - The created textual representation will be appended here.