Class LP


  • public final class LP
    extends Object
    This class allows executing and solving formulations of linear programming problems. The method used for solving such optimization problems is the simplex method.
    Version:
    4.0
    Author:
    Stefano Scarioli
    See Also:
    SSC Software www.sscLab.org
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static double NaN  
    • Constructor Summary

      Constructors 
      Constructor Description
      LP​(String pl_text)
      Constructor for use with the problem statement in text format stored in an String.
      LP​(Path path)
      Constructor for use with the problem statement in text format stored in an external file.
      LP​(ArrayList<String> text)
      Constructor for use with the problem statement in text format stored in an ArrayList.
      LP​(JsonProblem pl_json)  
      LP​(LinearObjectiveFunction fo, ArrayList<Constraint> constraints)
      Constructor Creates an LP object for solving problems expressed in matrix format.
      LP​(LinearObjectiveFunction fo, ListConstraints constraints)
      Constructor of an LP object for solving problems expressed in matrix format.
      LP​(org.ssclab.ref.Input input)
      Constructor of an LP object for solving problems expressed in coefficient format.
      LP​(org.ssclab.ref.Input input, org.ssclab.context.Session session)
      Constructor of an LP object for solving problems expressed in coefficient format.
      LP​(org.ssclab.ref.Input input, org.ssclab.context.Session session, FormatTypeInput.FormatType format)
      Constructor of an LP object for solving problems expressed in sparse format or coefficient format.
      LP​(org.ssclab.ref.Input input, FormatTypeInput.FormatType format)
      Constructor of an LP object for solving problems expressed in either sparse or coefficient format.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      EPSILON getCEpsilon()  
      EPSILON getEpsilon()  
      int getNumMaxIteration()
      This method returns the maximum number of simplex iterations
      Solution getSolution()
      If the problem has an optimal solution, this method returns that optimal solution in the form of an object of the Solution class.
      double[][] getStandartMatrixA()
      This method returns the matrix A obtained after the process of reduction to standard form (max z , Ax + s=b, x ≥ 0, b ≥ 0) of the original linear programming problem.
      double[] getStandartVectorB()
      This method returns the vector b of the rhs values obtained after the process of reduction to standard form(max z , Ax+s=b, x ≥ 0, b ≥ 0) of the original linear programming problem.
      double[] getStandartVectorC()
      This method returns the vector c of the coefficients of the objective function after the process of reduction to standard form (max z , Ax+s=b, x ≥ 0, b ≥ 0) of the original linear programming problem.
      LPThreadsNumber getThreadsNumber()  
      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()
      Returns true if only phase 1 execution is set to obtain a feasible solution.
      boolean isParallelSimplex()  
      SolutionType resolve()
      Executes the simplex (phase 1 + phase 2).
      LP setCEpsilon​(EPSILON epsilon)
      This method allows setting the epsilon value relative to the tolerance in determining if an optimal solution expressed by phase 1 is close to or equal to zero and thus gives rise to feasible solutions for the initial problem.
      LP setEpsilon​(EPSILON epsilon)
      This method allows setting the epsilon value relative to the tolerance that intervenes in various contexts.
      LP setJustTakeFeasibleSolution​(boolean isStopPhase2)
      Setting to true allows interrupting the simplex at the end of phase 1, in order to determine not an optimal solution but only a feasible solution of the problem.
      LP setNumMaxIteration​(int num_max_iteration)
      This method allows limiting the maximum number of simplex iterations (phase 1 iterations + phase 2 iterations)
      LP setParallelSimplex​(boolean isParallelSimplex)
      If the number of physical cores of the host on which SSc is running is greater than 4 and and if the number of variables constraints and hundreds, the performance of the simplex can be improved by executing the optimization processes in parallel on multiple threads.
      LP setThreadsNumber​(LPThreadsNumber threadsNumber)
      If the set value is AUTO, the system decides the number of threads to use.
    • Field Detail

      • NaN

        public static double NaN
    • Constructor Detail

      • LP

        public LP​(String pl_text)
           throws Exception
        Constructor for use with the problem statement in text format stored in an String.
        Parameters:
        pl_text - The text where the file containing the LP problem formulated with the text format is located
        Throws:
        Exception - An exception is thrown if the problem is not correctly formulated or if the file does not exist
      • LP

        public LP​(ArrayList<String> text)
           throws Exception
        Constructor for use with the problem statement in text format stored in an ArrayList.
        Parameters:
        text - An ArrayList (of String objects) containing the problem formulation in the form of text
        Throws:
        Exception - An exception is thrown if the problem is not correctly formulated
      • LP

        public LP​(Path path)
           throws Exception
        Constructor for use with the problem statement in text format stored in an external file.
        Parameters:
        path - The path where the file containing the LP problem formulated with the text format is located
        Throws:
        Exception - An exception is thrown if the problem is not correctly formulated or if the file does not exist
      • LP

        public LP​(LinearObjectiveFunction fo,
                  ArrayList<Constraint> constraints)
           throws Exception
        Constructor Creates an LP object for solving problems expressed in matrix format.
        Parameters:
        fo - A LinearObjectiveFunction object representing the objective function
        constraints - The list of constraints expressed as an ArrayList of Constraint objects
        Throws:
        Exception - An exception is thrown if the problem is not correctly formulated
      • LP

        public LP​(LinearObjectiveFunction fo,
                  ListConstraints constraints)
           throws Exception
        Constructor of an LP object for solving problems expressed in matrix format.
        Parameters:
        fo - A LinearObjectiveFunction object representing the objective function
        constraints - The list of constraints as a ListConstraints object
        Throws:
        Exception - An exception is thrown if the problem is not correctly formulated
      • LP

        public LP​(org.ssclab.ref.Input input,
                  org.ssclab.context.Session session,
                  FormatTypeInput.FormatType format)
           throws Exception
        Constructor of an LP object for solving problems expressed in sparse format or coefficient format.
        Parameters:
        input - The problem formulated in sparse format or coefficient format
        session - An SSC working session
        format - Constant to express in which format the problem is formulated (FormatType.SPARSE or FormatType.COEFF)
        Throws:
        Exception - An exception is thrown if the problem is not formulated correctly
      • LP

        public LP​(org.ssclab.ref.Input input,
                  FormatTypeInput.FormatType format)
           throws Exception
        Constructor of an LP object for solving problems expressed in either sparse or coefficient format.
        Parameters:
        input - The problem formulated in sparse format
        format - Constant to express in which format the problem is formulated (FormatType.SPARSE or FormatType.COEFF)
        Throws:
        Exception - An exception is thrown if the problem is not formulated correctly
      • LP

        public LP​(org.ssclab.ref.Input input)
           throws Exception
        Constructor of an LP object for solving problems expressed in coefficient format.
        Parameters:
        input - The problem formulated in coefficient format
        Throws:
        Exception - An exception is thrown if the problem is not formulated correctly
      • LP

        public LP​(org.ssclab.ref.Input input,
                  org.ssclab.context.Session session)
           throws Exception
        Constructor of an LP object for solving problems expressed in coefficient format.
        Parameters:
        input - The problem formulated in coefficient format
        session - An SSC working session
        Throws:
        Exception - An exception is thrown if the problem is not formulated correctly
    • Method Detail

      • setEpsilon

        public LP setEpsilon​(EPSILON epsilon)
        This method allows setting the epsilon value relative to the tolerance that intervenes in various contexts. It is used in the following cases:
        During phase one, both in determining the entering variable and in determining the exiting variable with or without the Bland rule; it is also used 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.
        During phase two, both in determining the entering variable and in determining the exiting variable with or without the Bland rule; it is also used to determine if the base is degenerate.
        Parameters:
        epsilon - Tolerance used in various phases of the simplex. Default value 1E-10
        Returns:
        the LP instance (this) on which the method call is being made
      • setCEpsilon

        public LP setCEpsilon​(EPSILON epsilon)
        This method allows setting the epsilon value relative to the tolerance in determining if an optimal solution expressed by phase 1 is close to or equal to zero and thus gives rise to feasible solutions for the initial problem.
        Parameters:
        epsilon - Tolerance of phase 1 solution with respect to zero. Default value 1E-8
        Returns:
        the LP instance (this) on which the method call is being made
      • getEpsilon

        public EPSILON getEpsilon()
      • getCEpsilon

        public EPSILON getCEpsilon()
      • setNumMaxIteration

        public LP setNumMaxIteration​(int num_max_iteration)
                              throws LPException
        This method allows limiting the maximum number of simplex iterations (phase 1 iterations + phase 2 iterations)
        Parameters:
        num_max_iteration - The maximum number of iterations to be executed. Default value 100,000,000.
        Returns:
        the LP instance (this) on which the method call is being made
        Throws:
        LPException - If an incorrect number (zero or negative) is set
      • getNumMaxIteration

        public int getNumMaxIteration()
        This method returns the maximum number of simplex iterations
        Returns:
        The maximum number of iterations
      • resolve

        public SolutionType resolve()
                             throws Exception
        Executes the simplex (phase 1 + phase 2).
        Returns:
        The type of solution found
        Throws:
        Exception - If the execution process generates an error
      • getStandartMatrixA

        public double[][] getStandartMatrixA()
                                      throws org.ssclab.pl.milp.simplex.SimplexException,
                                             IOException
        This method returns the matrix A obtained after the process of reduction to standard form (max z , Ax + s=b, x ≥ 0, b ≥ 0) of the original linear programming problem.
        Returns:
        The coefficient matrix A
        Throws:
        org.ssclab.pl.milp.simplex.SimplexException - If null matrix
        IOException - if the problem has not been reduced to standard form
      • getStandartVectorB

        public double[] getStandartVectorB()
        This method returns the vector b of the rhs values obtained after the process of reduction to standard form(max z , Ax+s=b, x ≥ 0, b ≥ 0) of the original linear programming problem.
        Returns:
        The vector of RHS coefficients
      • getStandartVectorC

        public double[] getStandartVectorC()
        This method returns the vector c of the coefficients of the objective function after the process of reduction to standard form (max z , Ax+s=b, x ≥ 0, b ≥ 0) of the original linear programming problem.
        Returns:
        The vector c of the coefficients of the objective function.
      • getSolution

        public Solution getSolution()
                             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 object of the Solution class.
        Returns:
        The optimal solution of the problem
        Throws:
        org.ssclab.pl.milp.simplex.SimplexException - If the optimal solution is not present
      • 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 double values
        Throws:
        org.ssclab.pl.milp.simplex.SimplexException - If the optimal solution is not present
      • isParallelSimplex

        public boolean isParallelSimplex()
        Returns:
        true if the parallelization with multiple threads of the simplex is active.
      • setParallelSimplex

        public LP setParallelSimplex​(boolean isParallelSimplex)
        If the number of physical cores of the host on which SSc is running is greater than 4 and and if the number of variables constraints and hundreds, the performance of the simplex can be improved by executing the optimization processes in parallel on multiple threads. The number of threads is set to set value is AUTO, the system decides the number of threads to use.
        Parameters:
        isParallelSimplex - True to activate parallelization
        Returns:
        the LP instance on which the method call is being made
      • getThreadsNumber

        public LPThreadsNumber getThreadsNumber()
        Returns:
        the number of threads used in the execution. If the value is AUTO, the system decides the number of threads to use.
      • setThreadsNumber

        public LP setThreadsNumber​(LPThreadsNumber threadsNumber)
        If the set value is AUTO, the system decides the number of threads to use.
        Parameters:
        threadsNumber - Sets the number of threads to use in the execution.
        Returns:
        the LP instance (this) on which the method call is being made
      • isJustTakeFeasibleSolution

        public boolean isJustTakeFeasibleSolution()
        Returns true if only phase 1 execution is set to obtain a feasible solution.
        Returns:
        true if active
      • setJustTakeFeasibleSolution

        public LP setJustTakeFeasibleSolution​(boolean isStopPhase2)
        Setting to true allows interrupting the simplex at the end of phase 1, in order to determine not an optimal solution but only a feasible solution of the problem.
        Parameters:
        isStopPhase2 - true to interrupt the simplex before phase 2.
        Returns:
        the LP instance (this) on which the method call is being made