Package org.ssclab.pl.milp

Class MILP

java.lang.Object

org.ssclab.pl.milp.MILP

All Implemented Interfaces:

FormatTypeInput

public final class MILP
extends java.lang.Object
implements FormatTypeInput

This class allows executing and solving formulations of mixed integer linear programming problems, binary or semicontinuous. The method used for solving such optimization problems is the simplex method combined with the Branch and Bound method.

Version:

4.0

Author:

Stefano Scarioli

See Also:

SSC Software www.sscLab.org

Nested Class Summary

Nested classes/interfaces inherited from interface org.ssclab.pl.milp.FormatTypeInput

FormatTypeInput.FormatType

Field Summary

Fields

Modifier and Type	Field	Description
static double	NaN

Constructor Summary

Constructors

Constructor	Description
MILP(java.lang.String path)	Constructor of a MILP object for solving problems formulated in inequality format contained in an external file.
MILP(java.util.ArrayList<java.lang.String> inequality)	Constructor of a MILP object for solving problems formulated in inequality format contained in an ArrayList of Strings.
MILP(LinearObjectiveFunction fo, java.util.ArrayList<Constraint> constraints)	Constructor of a MILP object for solving problems expressed in matrix format.
MILP(org.ssclab.ref.Input input)	Constructor of a MILP object for solving problems expressed in coefficient format.
MILP(org.ssclab.ref.Input input, org.ssclab.context.Session session)	Constructor of a MILP object for solving problems expressed in coefficient format.
MILP(org.ssclab.ref.Input input_sparse, org.ssclab.context.Session session, FormatTypeInput.FormatType format)	Constructor of a MILP object for solving problems expressed in either sparse or coefficient format.
MILP(org.ssclab.ref.Input input_sparse, FormatTypeInput.FormatType format)	Constructor of a MILP object for solving problems expressed in sparse or coefficient format.

Method Summary

Modifier and Type	Method	Description
int	getNumMaxIterationForSingleSimplex()
int	getNumMaxSimplexs()
Solution	getRelaxedSolution()	This method returns the solution of the problem by removing the integer constraints (relaxed solution).
Solution	getSolution()	This method returns, if it exists, the optimal integer, mixed-integer, or binary solution.
MILPThreadsNumber	getThreadNumber()
double[]	getValuesSolution()	If the problem has an optimal solution, this method returns that optimal solution in the form of an array with the values of the variables.
boolean	isJustTakeFeasibleSolution()
SolutionType	resolve()	Executes the Branch and Bound algorithm.
void	setCEpsilon(EPSILON cepsilon)	This method allows setting the epsilon value relative to the tolerance for determining if an optimal solution of phase 1 of the simplex is close to or equal to zero and thus gives rise to feasible solutions for the problem.
void	setEpsilon(EPSILON epsilon)	This method allows setting the epsilon value relative to the tolerance that intervenes in various aspects of the simplex.
void	setIEpsilon(EPSILON iepsilon)	This method allows setting the epsilon value relative to the tolerance for determining if a number should be considered integer or not.
void	setJustTakeFeasibleSolution(boolean isJustTakeFeasibleSolution)	Setting it to true allows interrupting the Branch and Bound in order to determine not an optimal solution but only a feasible solution to the problem.
void	setNumMaxIterationForSingleSimplex(int num_max_iteration)	Method to set the number of iterations for each individual simplex.
void	setNumMaxSimplexs(int num_max_simplex)	Method to set the maximum number of simplexes.
void	setThreadNumber(MILPThreadsNumber lthreadNumber)	This method allows setting the number of threads to use for executing the Branch and Bound.

Methods inherited from class java.lang.Object

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

Field Detail

NaN

public static double NaN

Constructor Detail

MILP

public MILP(java.util.ArrayList<java.lang.String> inequality)
     throws java.lang.Exception

Constructor of a MILP object for solving problems formulated in inequality format contained in an ArrayList of Strings.

Parameters:

inequality - The ArrayList with the problem

Throws:

java.lang.Exception - if the ArrayList is null or empty

MILP

public MILP(java.lang.String path)
     throws java.lang.Exception

Constructor of a MILP object for solving problems formulated in inequality format contained in an external file.

Parameters:

path - Path of the file containing the problem in inequality format

Throws:

java.lang.Exception - if the problem is not correctly formulated

MILP

public MILP(LinearObjectiveFunction fo,
            java.util.ArrayList<Constraint> constraints)
     throws java.lang.Exception

Constructor of a MILP object for solving problems expressed in matrix format.

Parameters:

fo - A LinearObjectiveFunction object representing the objective function

constraints - The list of constraints

Throws:

java.lang.Exception - An exception is thrown if the problem is not correctly formulated

MILP

public MILP(org.ssclab.ref.Input input)
     throws java.lang.Exception

Constructor of a MILP object for solving problems expressed in coefficient format.

Parameters:

input - The problem formulated in coefficient format

Throws:

java.lang.Exception - An exception is thrown if the problem is not formulated correctly

MILP

public MILP(org.ssclab.ref.Input input,
            org.ssclab.context.Session session)
     throws java.lang.Exception

Constructor of a MILP object for solving problems expressed in coefficient format.

Parameters:

input - The problem formulated in coefficient format

session - An SSC working session

Throws:

java.lang.Exception - An exception is thrown if the problem is not formulated correctly

MILP

public MILP(org.ssclab.ref.Input input_sparse,
            org.ssclab.context.Session session,
            FormatTypeInput.FormatType format)
     throws java.lang.Exception

Constructor of a MILP object for solving problems expressed in either sparse or coefficient format.

Parameters:

input_sparse - The problem formulated in sparse or coefficient format

session - An SSC working session

format - The type of format used (FormatType.SPARSE or FormatType.COEFF)

Throws:

java.lang.Exception - An exception is thrown if the problem is not formulated correctly

MILP

public MILP(org.ssclab.ref.Input input_sparse,
            FormatTypeInput.FormatType format)
     throws java.lang.Exception

Constructor of a MILP object for solving problems expressed in sparse or coefficient format.

Parameters:

input_sparse - The problem formulated in sparse format

format - The type of format used (FormatType.SPARSE or FormatType.COEFF)

Throws:

java.lang.Exception - An exception is thrown if the problem is not formulated correctly

Method Detail

getNumMaxIterationForSingleSimplex

public int getNumMaxIterationForSingleSimplex()

Returns:

the maximum number of iterations that each simplex can execute

setNumMaxIterationForSingleSimplex

public void setNumMaxIterationForSingleSimplex(int num_max_iteration)
                                        throws org.ssclab.pl.milp.simplex.SimplexException

Method to set the number of iterations for each individual simplex.

Parameters:

num_max_iteration - The maximum number of iterations that each simplex can execute

Throws:

org.ssclab.pl.milp.simplex.SimplexException - If an error occurs during the process

getNumMaxSimplexs

public int getNumMaxSimplexs()

Returns:

the maximum number of simplexes executable in the Branch and Bound procedure

setNumMaxSimplexs

public void setNumMaxSimplexs(int num_max_simplex)

Method to set the maximum number of simplexes.

Parameters:

num_max_simplex - the maximum number of simplexes executable in the Branch and Bound procedure

setEpsilon

public void setEpsilon(EPSILON epsilon)

This method allows setting the epsilon value relative to the tolerance that intervenes in various aspects of the simplex. It is used in the following cases:
1) During phase one, both in determining the entering variable and in determining the exiting variable with or without the Bland rule. Also to determine if the base is degenerate. It is also used at the end of phase one: if there is an auxiliary variable in the base, epsilon is used to determine if it is possible to eliminate the rows and columns of these on the extended table.
2) During phase two, both in determining the entering variable and in determining the exiting variable with or without the Bland rule. Also to determine if the base is degenerate.

Parameters:

epsilon - Tolerance used in various phases of the simplex. Default value 1E-10

setCEpsilon

public void setCEpsilon(EPSILON cepsilon)

This method allows setting the epsilon value relative to the tolerance for determining if an optimal solution of phase 1 of the simplex is close to or equal to zero and thus gives rise to feasible solutions for the problem.

Parameters:

cepsilon - Tolerance of phase 1 solution with respect to zero. Default value 1E-8

setIEpsilon

public void setIEpsilon(EPSILON iepsilon)

This method allows setting the epsilon value relative to the tolerance for determining if a number should be considered integer or not. This check occurs when at the end of the simplex the solution found is evaluated to satisfy the integer condition on the variables that must be integers. Let x be a number and Int(x) the nearest integer to x, if | Int(x) - x | < epsilon -> x ∈ ℤ

Parameters:

iepsilon - Tolerance to consider a number as integer. Default value 1E-10

resolve

public SolutionType resolve()
                     throws java.lang.Exception

Executes the Branch and Bound algorithm.

Returns:

The type of solution found

Throws:

java.lang.Exception - If the execution process generates an error

getRelaxedSolution

public Solution getRelaxedSolution()

This method returns the solution of the problem by removing the integer constraints (relaxed solution). If there are binary variables, only the constraint from assuming integer values is removed, but the binary variable still has the constraint of being between zero and one.

Returns:

returns the relaxed solution, i.e., the solution of the problem without integer constraints.

getSolution

public Solution getSolution()

This method returns, if it exists, the optimal integer, mixed-integer, or binary solution.

Returns:

the optimal integer, mixed-integer, or binary solution

getValuesSolution

public double[] getValuesSolution()
                           throws org.ssclab.pl.milp.simplex.SimplexException

If the problem has an optimal solution, this method returns that optimal solution in the form of an array with the values of the variables.

Returns:

The optimal solution of the problem as an array of values

Throws:

org.ssclab.pl.milp.simplex.SimplexException - If the optimal solution is not present

getThreadNumber

public MILPThreadsNumber getThreadNumber()

Returns:

the number of threads set for solving the problem

setThreadNumber

public void setThreadNumber(MILPThreadsNumber lthreadNumber)

This method allows setting the number of threads to use for executing the Branch and Bound.

Parameters:

lthreadNumber - Enumeration for setting the number of Threads

isJustTakeFeasibleSolution

public boolean isJustTakeFeasibleSolution()

Returns:

true if the mode of returning a feasible solution instead of an optimal one is set

setJustTakeFeasibleSolution

public void setJustTakeFeasibleSolution(boolean isJustTakeFeasibleSolution)

Setting it to true allows interrupting the Branch and Bound in order to determine not an optimal solution but only a feasible solution to the problem.

Parameters:

isJustTakeFeasibleSolution - true to interrupt the Branch and Bound and obtain only a feasible solution.