// Catalano Math Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2018
// diego.catalano at live.com
//
//
//    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 St, Fifth Floor, Boston, MA  02110-1301  USA
//

package Catalano.Math.Optimization;

import Catalano.Math.Matrix;
import java.util.Arrays;
import java.util.List;

/**
 * Linear Programming.
 * Two Phase Method.
 * 
 * @author Diego Catalano
 */
public class LinearProgramming {
    
    /**
     * The solution is infeasible.
     */
    public static final int INFEASIBLE = 0;
    
    /**
     * The solution exists.
     */
    public static final int OPTIMAL = 1;
    
    /**
     * The solution is unbounded.
     */
    public static final int UNBOUNDED = 2;
    
    /**
     * Objective of the function.
     */
    public enum Objective{
        
        /**
         * Minimize the function.
         */
        Minimize,
        
        /**
         * Maximize the function.
         */
        Maximize
    };
    
    private final static int SECOND_PHASE = -2;
    
    private double[] function;
    private Objective objective;
    
    private double[] r;
    private double solution;
    private boolean isInfinite;
    
    private int iterations;
    
    private List constraints;

    /**
     * Number of iterations required to be converged.
     * @return Number of iterations.
     */
    public int getIterations() {
        return iterations;
    }
    
    /**
     * Get the final solution.
     * @return Optimal objective value.
     */
    public double getSolution() {
        return solution;
    }

    /**
     * Get coefficients.
     * @return Coefficients.
     */
    public double[] getCoefficients() {
        return r;
    }

    /**
     * Linear Programming.
     * @param objective Objective.
     */
    public LinearProgramming(Objective objective) {
        this.objective = objective;
    }
    
    /**
     * Check if the solution is infinite.
     * @return True if exists one more solution, otherwise return false.
     */
    public boolean isInfinite(){
        return isInfinite;
    }
    
    /**
     * Solve the simplex problem.
     * @param function Function.
     * @param constraints List of constraints.
     * @return Status of the solution.
     */
    public int Solve(double[] function, List constraints){
        
        this.function = function;
        this.constraints = constraints;
        iterations = 0;
        isInfinite = false;
        
        //Create Tableau
        Tableau tableau = CreateTableau(function, constraints);
        
        double[][] tab = tableau.getTableau();
        double[] vars = tableau.getCoefVars();
        int[] basis = tableau.getBasis();
        
        int status = -1;
        
        while(true){
            
            iterations++;
            
            //Find column
            int q = findColumn(tab, vars, basis); //var in
            
            //Create another tableau, 2-phase
            if(q == SECOND_PHASE){
                tableau = CreateSecondTableau(tab, vars, basis);
                tab = tableau.getTableau();
                vars = tableau.getCoefVars();
                basis = tableau.getBasis();
            }
            
            //Check if the solution is unbounded
            if(q >= 0){
                if(isUnbounded(tab, q))
                    return 2;
            }
            
            if(q == -1){
                
                //Check if the solution is infeasible
                if(isInfeasible(tab, vars, basis))
                    return 0;
                
                //Optimal solution
                status = 1;
                break;
            }
            
            if(q >= 0){
                int p = findRow(tab, q, vars, basis); //var out

                //Change basis
                basis[p] = q;

                //Pivot element
                double pivot = tab[p][q];

                //Calculate new line
                for (int i = 0; i < tab[0].length; i++) {
                    tab[p][i] /= pivot;
                }

                //Calculate the rest of the tableau
                for (int i = 0; i < tab.length; i++) {
                    if(i != p){
                        pivot = tab[i][q];
                        for (int j = 0; j < tab[0].length; j++) {
                            tab[i][j] = tab[i][j] - pivot * tab[p][j];
                        }
                    }
                }
            }
        }
        
        //Compute the coefficients
        r = new double[vars.length];
        for (int i = 0; i < basis.length; i++) {
            r[basis[i]] = tab[i][tab[0].length - 1];
        }
        
        //Compute Z (The final solution)
        solution = 0;
        for (int i = 0; i < function.length; i++) {
            solution += function[i] * r[i];
        }
        
        if(objective == Objective.Minimize){
            for (int i = 0; i < function.length; i++) {
                function[i] *= -1;
            }
        }
        
        if(objective == Objective.Minimize)
            solution = -solution;
        
        r = Arrays.copyOf(r, function.length);
        return status;
        
    }
    
    private Tableau CreateSecondTableau(double[][] tableau, double[] vars, int[] basis){
        
        //Count how many artificial variables exists
        int c = 0;
        for (int i = 0; i < vars.length; i++) {
            if(vars[i] == -1) c++;
        }
        
        //Eliminate columns from tableau, vars and others.
        int[] index = new int[c];
        int idx = 0;
        for (int i = 0; i < vars.length; i++) {
            if(vars[i] == -1){
                index[idx] = i;
                idx++;
            }
        }
        
        tableau = Matrix.RemoveColumns(tableau, index);
        
        vars = new double[tableau[0].length];
        
        for (int i = 0; i < function.length; i++) {
            vars[i] = function[i];
        }
        
        return new Tableau(tableau, vars, basis);
        
    }
    
    private boolean isUnbounded(double[][] tableau, int q){
        int c = 0;
        for (int i = 0; i < tableau.length; i++) {
            if(tableau[i][q] <= 0) c++;
        }

        if(c == tableau.length) return true;
        
        return false;
    }
    
    private boolean isInfeasible(double[][] tableau, double[] artVariables, int[] basis){
        for (int i = 0; i < tableau.length; i++) {
            if((tableau[i][tableau[0].length - 1] > 0) && (artVariables[basis[i]] == -1)){
                return true;
            }
        }
        return false;
    }
    
    private int findColumn(double[][] tableau, double[] coef, int[] basis){

        //Calculate Z
        double[] z = new double[tableau[0].length - 1];
        for (int i = 0; i < tableau.length; i++) {
            for (int j = 0; j < tableau[0].length - 1; j++) {
                z[j] += tableau[i][j] * coef[basis[i]];
            }
        }
        
        //Calculate C-Z
        for (int i = 0; i < coef.length - 1; i++) {
            z[i] = z[i] - coef[i];
        }
        
        //Check if the solution is optimal
        boolean isOptimal = true;
        for (int i = 0; i < z.length; i++) {
            if(z[i] < 0)
                isOptimal = false;
        }
        
        //Check if Z right values is 0 too
        if(isOptimal){
            double sum = 0;
            for (int i = 0; i < tableau.length; i++) {
                sum += tableau[i][tableau[0].length - 1] * coef[basis[i]];
            }
            
            //Need to create the other tableau
            if(sum == 0){
                return -2;
            }
            
            //Check if the solution is infinite
            for (int i = 0; i < basis.length; i++) {
                coef[basis[i]] = Double.NaN;
            }
            
            int c = 0;
            for (int i = 0; i < z.length; i++)
                if(!Double.isNaN(coef[i]) && z[i] == 0) c++;
            
            
            if(c > 0) isInfinite = true;
            
            return -1;
            
        }
        
        if(isOptimal) return -1;
        
        return Matrix.MinIndex(z);
        
    }
    
    private int findRow(double[][] tableau, int q, double[] artVar, int[] basis){
        
        double min = Double.MAX_VALUE;
        double[] div = new double[tableau.length];
        for (int i = 0; i < div.length; i++) {
            if(tableau[i][q] > 0){
                div[i] = tableau[i][tableau[0].length - 1] / tableau[i][q];
                min = Math.min(min, div[i]);
            }
            else{
                div[i] = Double.MAX_VALUE;
            }
        }
        
        //Output variable draw
        //In the case if exists more than one same value of min, we need to choose artificial variable
        int c = 0;
        for (int i = 0; i < div.length; i++) {
            if(div[i] == min) c++;
        }
        
        if(c == 1) return Matrix.MinIndex(div);
        
        for (int i = 0; i < div.length; i++)
            if(div[i] == min && artVar[basis[i]] == -1)
                return i;
        
        
        return Matrix.MinIndex(div);
        
    }
    
    private Tableau CreateTableau(double[] function, List constraint){
        
        //Transform minimization problem in maximization
        if(objective == Objective.Minimize){
            for (int i = 0; i < function.length; i++) {
                function[i] *= -1;
            }
        }
        
        boolean hasArtificialVariable = false;
        int nBasic = 0;
        int nArtificial = 0;
        
        //Discover how many variables is necessary
        int vars = 0;
        for (Constraint c : constraint) {
            switch(c.getSymbol()){
                case LESS_THAN:
                    nBasic++;
                break;
                case EQUAL_TO:
                    nArtificial++;
                break;
                case GREATER_THAN:
                    nBasic++;
                    nArtificial++;
                break;
            }
        }
        
        vars = nBasic + nArtificial;
        if(nArtificial > 0) hasArtificialVariable = true;
        
        //Build our tableau
        double[][] tableau = new double[constraint.size()][function.length + vars + 1];
        
        int[] basis = new int[constraint.size()];
        for (int i = 0; i < basis.length; i++) {
            basis[i] = i;
        }
        
        //Write left side values
        for (int i = 0; i < constraint.size(); i++) {
            Constraint c = constraint.get(i);
            for (int j = 0; j < function.length; j++) {
                if(c.getRightSide() >= 0)
                    tableau[i][j] = c.getLeftSide()[j];
                else
                    tableau[i][j] = -c.getLeftSide()[j];
            }
        }
        
        //Write right side values
        for (int i = 0; i < constraint.size(); i++){
            Constraint c = constraint.get(i);
            if(c.getRightSide() >= 0)
                tableau[i][tableau[0].length - 1] = c.getRightSide();
            else
                tableau[i][tableau[0].length - 1] = -c.getRightSide();
        }
        
        //Coefficients
        double[] t = new double[function.length + vars + 1];
        
        if(!hasArtificialVariable){
            for (int i = 0; i < function.length; i++) {
                t[i] = function[i];
            }
        }
        
        //Initialize slack variables
        int movesSx = function.length;
        int movesAx = function.length + nBasic;
        for (int i = 0; i < constraint.size(); i++) {
            
            Constraint c = constraint.get(i);
            
            if(c.getRightSide() >= 0){
                switch(c.getSymbol()){
                    case LESS_THAN:
                        tableau[i][movesSx] = 1;
                        basis[i] = movesSx;

                        movesSx++;
                    break;
                    case EQUAL_TO:
                        tableau[i][movesAx] = 1;
                        basis[i] = movesAx;
                        t[movesAx] = -1;

                        movesAx++;
                    break;
                    case GREATER_THAN:
                        tableau[i][movesSx] = -1;
                        tableau[i][movesAx] = 1;
                        t[movesSx] = 0;
                        t[movesAx] = -1;
                        basis[i] = movesAx;

                        movesSx++;
                        movesAx++;
                    break;
                }
            }
            else{
                switch(c.getSymbol()){
                    case LESS_THAN:
                        tableau[i][movesSx] = -1;
                        tableau[i][movesAx] = 1;
                        t[movesSx] = 0;
                        t[movesAx] = -1;
                        basis[i] = movesAx;

                        movesSx++;
                        movesAx++;
                    break;
                    case EQUAL_TO:
                        tableau[i][movesAx] = 1;
                        basis[i] = movesAx;
                        t[movesAx] = -1;

                        movesAx++;
                    break;
                    case GREATER_THAN:
                        tableau[i][movesSx] = 1;
                        basis[i] = movesSx;

                        movesSx++;
                    break;
                }
            }
            
        }
        
        return new Tableau(tableau, t, basis);
        
    }
    
}
 

Ads help maintain this website.