LBJ2.jni
Class GLPKHook

java.lang.Object
  LBJ2.jni.GLPKHook

All Implemented Interfaces:

ILPSolver

public class GLPKHook
extends java.lang.Object
implements ILPSolver

Native interface to the GNU Linear Programming Kit (GLPK), designed for version 4.14. In order to use this class, GLPK 4.14 must be installed such that the following statement would work in a C source file:

#include <glpk.h>

and such that that C file could be compiled and linked with -lglpk on the command line. Furthermore, the GLPKHook library distributed with LBJ must be accessible in a location where the JVM will search for it.

An object of this class represents a single integer linear programming problem. All columns added are assumed to represent Boolean variables (i.e., integer variables that may take either the value 0 or the value 1).

Field Summary

private java.util.LinkedList	constraints If the appropriate methods are called below, this list will contain all the constraints that have been added to this solver.
private java.lang.String	debugFileName Diagnostic messages are written to this file when an optimal solution cannot be found.
private boolean	generateCuts Whether or not to generate Gomory cuts.
private boolean	maximize If the appropriate methods are called below, this variable will be set iff this solver is solving a maximization.
private int	objectiveCoefficients Represents the number of variables in the optimization problem.
private java.lang.String	objectiveFunction If the appropriate methods are called below, this string will represent the objective function.
private boolean	printProblem true if the ILP problem should be printed when invoking solve().
private int	problemPointer A C pointer to the C problem structure.
private boolean	solved Indicates whether this problem instance has been solved already.

Constructor Summary

GLPKHook()
Creates the problem object with a call to createProblem().

GLPKHook(boolean g)
Creates the problem object with a call to createProblem().

GLPKHook(boolean g, boolean p)
Creates the problem object with a call to createProblem().

GLPKHook(java.lang.String s)
Creates the problem object with a call to createProblem().

GLPKHook(java.lang.String s, boolean g)
Creates the problem object with a call to createProblem().

GLPKHook(java.lang.String s, boolean g, boolean p)
Creates the problem object with a call to createProblem().

Method Summary

int	addBooleanVariable(double c) Adds a new Boolean variable (an integer variable constrained to take either the value 0 or the value 1) with the specified coefficient in the objective function to the problem.
int[]	addDiscreteVariable(double[] c) Adds a general, multi-valued discrete variable, which is implemented as a set of Boolean variables, one per value of the discrete variable, with exactly one of those variables set true at any given time.
int[]	addDiscreteVariable(Score[] c) Adds a general, multi-valued discrete variable, which is implemented as a set of Boolean variables, one per value of the discrete variable, with exactly one of those variables set true at any given time.
void	addEqualityConstraint(int[] i, double[] a, double b) Adds a new fixed constraint to the problem.
protected void	addFixedConstraint(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.
void	addLessThanConstraint(int[] i, double[] a, double b) Adds a new upper bounded constraint to the problem.
protected void	addLowerBoundedConstraint(int[] i, double[] a, double b) Adds a new lower bounded constraint to the problem.
protected void	addObjectiveCoefficient(double c) Adds a new Boolean variable (an integer variable constrained to take either the value 0 or the value 1) with the specified coefficient in the objective function to the problem.
protected void	addUpperBoundedConstraint(int[] i, double[] a, double b) Adds a new upper bounded constraint to the problem.
double	columnPrimalValueOf(int i) Returns the value of the specified variable in the primal solution.
protected int	createProblem() Instantiates the problem object in the C world.
protected void	deleteProblem() Frees the problem object's memory in the C world.
protected void	finalize() Deletes the problem object with a call to deleteProblem().
boolean	getBooleanValue(int index) When the problem has been solved, use this method to retrieve the value of any Boolean inference variable.
boolean	isSolved() Tests whether the problem represented by this ILPSolver instance has been solved already.
protected boolean	nativeSolve() Invokes the lpx_intopt GLPK library function to solve the integer linear program.
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.
protected void	setMaximize() Sets the direction of the objective function to maximization.
void	setMaximize(boolean d) Sets the direction of the objective function.
protected void	setMinimize() Sets the direction of the objective function to minimization.
boolean	solve() Simply calls nativeSolve(), saving the result in solved.
void	write(java.lang.StringBuffer buffer) Writes the optimization problem that this solver represents into the specified buffer, assuming the appropriate member methods were called to remember this information.

Methods inherited from class java.lang.Object

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

Field Detail

solved

private boolean solved

Indicates whether this problem instance has been solved already.

problemPointer

private int problemPointer

A C pointer to the C problem structure.

generateCuts

private boolean generateCuts

Whether or not to generate Gomory cuts.

debugFileName

private java.lang.String debugFileName

Diagnostic messages are written to this file when an optimal solution cannot be found.

printProblem

private boolean printProblem

true if the ILP problem should be printed when invoking solve().

constraints

private java.util.LinkedList constraints

If the appropriate methods are called below, this list will contain all the constraints that have been added to this solver.

objectiveFunction

private java.lang.String objectiveFunction

If the appropriate methods are called below, this string will represent the objective function.

objectiveCoefficients

private int objectiveCoefficients

Represents the number of variables in the optimization problem.

maximize

private boolean maximize

If the appropriate methods are called below, this variable will be set iff this solver is solving a maximization.

Constructor Detail

GLPKHook

public GLPKHook()

Creates the problem object with a call to createProblem().

See Also:

createProblem()

GLPKHook

public GLPKHook(boolean g)

Creates the problem object with a call to createProblem().

Parameters:

g - Whether or not to generate cuts.

See Also:

createProblem()

GLPKHook

public GLPKHook(boolean g,
                boolean p)

Creates the problem object with a call to createProblem().

Parameters:

g - Whether or not to generate cuts.

p - Set true to cause a textual representation of the problem to be printed to STDOUT when invoking the solve() method before the solution is carried out.

See Also:

createProblem()

GLPKHook

public GLPKHook(java.lang.String s)

Creates the problem object with a call to createProblem().

Parameters:

s - A file name for the "debug" file, in which diagnostic messages are written when an optimal solution cannot be found.

See Also:

createProblem()

GLPKHook

public GLPKHook(java.lang.String s,
                boolean g)

Creates the problem object with a call to createProblem().

Parameters:

s - A file name for the "debug" file, in which diagnostic messages are written when an optimal solution cannot be found.

g - Whether or not to generate cuts.

See Also:

createProblem()

GLPKHook

public GLPKHook(java.lang.String s,
                boolean g,
                boolean p)

Creates the problem object with a call to createProblem().

Parameters:

s - A file name for the "debug" file, in which diagnostic messages are written when an optimal solution cannot be found.

g - Whether or not to generate cuts.

p - Set true to cause a textual representation of the problem to be printed to STDOUT when invoking the solve() method before the solution is carried out.

See Also:

createProblem()

Method Detail

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 ILPSolver

isSolved

public boolean isSolved()

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

Specified by:

isSolved in interface ILPSolver

finalize

protected void finalize()
                 throws java.lang.Throwable

Deletes the problem object with a call to deleteProblem().

Overrides:

finalize in class java.lang.Object

Throws:

java.lang.Throwable

See Also:

deleteProblem()

createProblem

protected int createProblem()

Instantiates the problem object in the C world.

Returns:

A pointer to the structure created.

deleteProblem

protected void deleteProblem()

Frees the problem object's memory in the C world.

setMaximize

public void setMaximize(boolean d)

Sets the direction of the objective function.

Specified by:

setMaximize in interface ILPSolver

Parameters:

d - true if the objective function is to be maximized.

setMaximize

protected void setMaximize()

Sets the direction of the objective function to maximization.

setMinimize

protected void setMinimize()

Sets the direction of the objective function to minimization.

addDiscreteVariable

public int[] addDiscreteVariable(double[] c)

Adds a general, multi-valued discrete variable, which is implemented as a set of Boolean variables, one per value of the discrete variable, with exactly one of those variables set true at any given time. Since GLPK does not handle these sets of Boolean variables specially, this method simply calls addBooleanVariable(double) repeatedly and then adds an equality constraint.

Specified by:

addDiscreteVariable in interface ILPSolver

Parameters:

c - The objective function coefficients for the new Boolean variables.

Returns:

The indexes of the newly created variables.

addDiscreteVariable

public int[] addDiscreteVariable(Score[] c)

Adds a general, multi-valued discrete variable, which is implemented as a set of Boolean variables, one per value of the discrete variable, with exactly one of those variables set true at any given time. Since GLPK does not handle these sets of Boolean variables specially, this method simply calls addBooleanVariable(double) repeatedly and then adds an equality constraint.

Specified by:

addDiscreteVariable in interface ILPSolver

Parameters:

c - An array of Scores containing the objective function coefficients for the new Boolean variables.

Returns:

The indexes of the newly created variables.

addBooleanVariable

public int addBooleanVariable(double c)

Adds a new Boolean variable (an integer variable constrained to take either the value 0 or the value 1) with the specified coefficient in the objective function to the problem.

Specified by:

addBooleanVariable in interface ILPSolver

Parameters:

c - The objective function coefficient for the new Boolean variable.

Returns:

The indexes of the created variable.

addObjectiveCoefficient

protected void addObjectiveCoefficient(double c)

Adds a new Boolean variable (an integer variable constrained to take either the value 0 or the value 1) with the specified coefficient in the objective function to the problem.

Parameters:

c - The objective function coefficient for the new Boolean variable.

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 addBooleanVariable(double) or 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 ILPSolver

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.

addFixedConstraint

protected void addFixedConstraint(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 addBooleanVariable(double) or 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.

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 addBooleanVariable(double) or 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 ILPSolver

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.

addLowerBoundedConstraint

protected void addLowerBoundedConstraint(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 addBooleanVariable(double) or 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.

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 addBooleanVariable(double) or 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 ILPSolver

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.

addUpperBoundedConstraint

protected void addUpperBoundedConstraint(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 addBooleanVariable(double) or 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.

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 java.lang.Exception

Simply calls nativeSolve(), saving the result in solved.

Specified by:

solve in interface ILPSolver

Throws:

java.lang.Exception

nativeSolve

protected boolean nativeSolve()

Invokes the lpx_intopt GLPK library function to solve the integer linear program. To produce diagnostic messages regarding a return value of false from this method, use the constructor of this class that takes a String argument.

Returns:

true iff an optimal integer solution was found and no problems were encountered while running the algorithms.

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 ILPSolver

Parameters:

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

Returns:

The value of the variable.

columnPrimalValueOf

public double columnPrimalValueOf(int i)

Returns the value of the specified variable in the primal solution.

Parameters:

i - The index of the variable whose value is to be returned.

Returns:

The value of the specified variable in the primal solution.

write

public void write(java.lang.StringBuffer buffer)

Writes the optimization problem that this solver represents into the specified buffer, assuming the appropriate member methods were called to remember this information.

Specified by:

write in interface ILPSolver

Parameters:

buffer - The buffer to write in.