problem.java

Create a problem solver for linear programming

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package ro.simplex;

import java.util.ArrayList;
import ro.utils.Fraction;

/**
 *
 * @author Doan Chien Thang
 */
public class Problem {
    public static final int HAS_ONE_SOLUTION = 1;
    public static final int HAS_INFINITVE_SOLUTIONS = 2;
    public static final int IS_UNBOUND = 3;
    public static final int NO_SOLUTION = 4;

    protected ArrayList<Variable> vars;
    protected ArrayList<Constraint> constraints;
    protected Objective objective;
    protected int answer;

    public Problem(ArrayList<Variable> vars, ArrayList<Constraint> constraints,
            Objective objective) {
        this.vars = vars;
        this.constraints = constraints;
        this.objective = objective;
    }

    @Override
    public String toString() {
        String result = "<div style=\"background-color:#EDEDED;padding:10;" +
                "margin-right:15\">";
        result += objective.toString();
        for (int i = 0; i < constraints.size(); i++)
            result += constraints.get(i).toString();
        result += "<b>Conditions: ";
        for (int i = 0; i < vars.size(); i++) {
            if (i < vars.size() - 1)
                result += vars.get(i).getConstraintString() + ", ";
            else
                result += vars.get(i).getConstraintString() + "<br />";
        }
        return result + "</b></div>";
    }

    public ArrayList<Variable> getVars() {
        return this.vars;
    }

    public void refinePositiveConstraints(
            ArrayList<Constraint> newConstraints,
            Variable currentVar) {
        for (int i = 0; i < constraints.size(); i++) {
            for (int j = 0; j < constraints.get(i).getCoefs().size(); j++) {
                if (vars.get(j).equals(currentVar)) {
                    newConstraints.get(i).getCoefs().add(
                            constraints.get(i).getCoefs().get(j));
                }
            }
        }
    }

    public void refineNegativeConstraints (
            ArrayList<Constraint> newConstraints,
            Variable currentVar) {
        for (int i = 0; i < constraints.size(); i++) {
            for (int j = 0; j < constraints.get(i).getCoefs().size(); j++)
                if (vars.get(j).equals(currentVar))
                    newConstraints.get(i).getCoefs().add(
                            constraints.get(i).getCoefs().get(j).getOpposite());
        }
    }

    public void refineBelongsRConstraints (
            ArrayList<Constraint> newConstraints,
            Variable currentVar) {
        for (int i = 0; i < constraints.size(); i++) {
            for (int j = 0; j < constraints.get(i).getCoefs().size(); j++)
                if (vars.get(j).equals(currentVar)) {
                    newConstraints.get(i).getCoefs().add(
                            constraints.get(i).getCoefs().get(j));
                    newConstraints.get(i).getCoefs().add(
                            constraints.get(i).getCoefs().get(j).getOpposite());
                }
        }
    }

    public void refineObjective(Objective newObjective, 
            Variable currentVar) {
        for (int i = 0; i < objective.getCoefs().size(); i++)
            if (vars.get(i).equals(currentVar)) {
                if (currentVar.getConstraint() == ConstraintTypes.GREATER_THAN)
                    newObjective.getCoefs().add(objective.getCoefs().get(i));
                else if (currentVar.getConstraint() == ConstraintTypes.LESS_THAN)
                    newObjective.getCoefs().add(
                            objective.getCoefs().get(i).getOpposite());
                else
                    newObjective.getCoefs().add(objective.getCoefs().get(i));
                if (currentVar.getConstraint() == ConstraintTypes.BELONG_R)
                    newObjective.getCoefs().add(
                            objective.getCoefs().get(i).getOpposite());
            }
    }

    public void setObjective(Objective newObjective) {
        if (objective.getType() == Objective.MINIMIZE)
            for (int i = 0; i < newObjective.getCoefs().size(); i++)
                newObjective.getCoefs().set(i,
                        newObjective.getCoefs().get(i).getOpposite());
        newObjective.setType(Objective.MAXIMIZE);
    }

    public void addNewVariablesToGetEquations(
            ArrayList<Variable> newVars, ArrayList<Constraint> newConstraints) {
        String newPrefix = "u";
        int index = 0;
        for (int i = 0; i < newConstraints.size(); i++) {
            Variable var;
            newConstraints.get(i).setValue(constraints.get(i).getValue());
            switch (constraints.get(i).getType()) {
                case ConstraintTypes.GREATER_THAN:
                    var = new Variable(null, ++index, newPrefix,
                            ConstraintTypes.GREATER_THAN);
                    var.setValue(constraints.get(i).getValue().getOpposite());
                    newVars.add(var);
                    for (int j = 0; j < index - 1; j++)
                        newConstraints.get(i).getCoefs().add(new Fraction(0));
                    newConstraints.get(i).getCoefs().add(new Fraction(-1));
                    break;
                case ConstraintTypes.LESS_THAN:
                    var = new Variable(null, ++index, newPrefix,
                            ConstraintTypes.GREATER_THAN);
                    var.setValue(constraints.get(i).getValue());
                    newVars.add(var);
                    for (int j = 0; j < index - 1; j++)
                        newConstraints.get(i).getCoefs().add(new Fraction(0));
                    newConstraints.get(i).getCoefs().add(new Fraction(1));
                    break;
                case ConstraintTypes.EQUAL_TO:
                    for (int j = 0; j < index; j++)
                        newConstraints.get(i).getCoefs().add(new Fraction(0));
                    break;
                default:
                    break;
            }
        }
        for (int i = 0; i < newConstraints.size(); i++) {
            for (int j = newConstraints.get(i).getCoefs().size();
                j < newVars.size(); j++)
                newConstraints.get(i).getCoefs().add(new Fraction(0));
        }
    }

    public Problem refinedProblem() {
        ArrayList<Variable> newVars = this.vars;
        ArrayList<Constraint> newConstraints = new ArrayList<Constraint>();
        Objective newObjective = this.objective;
        for (int i = 0; i < this.constraints.size(); i++) {
            Constraint constraint1, constraint2;
            if (this.constraints.get(i).getType() == ConstraintTypes.EQUAL_TO) {
                constraint1 = new Constraint(ConstraintTypes.GREATER_THAN,
                        this.constraints.get(i).getCoefs(),
                        this.constraints.get(i).getVars(),
                        this.constraints.get(i).getValue());
                constraint2 = new Constraint(ConstraintTypes.LESS_THAN,
                        this.constraints.get(i).getCoefs(),
                        this.constraints.get(i).getVars(),
                        this.constraints.get(i).getValue());
                newConstraints.add(constraint1);
                newConstraints.add(constraint2);
            } else
                newConstraints.add(this.constraints.get(i));
        }
        return new Problem(newVars, newConstraints, newObjective);
    }

    public ProblemInStandardForm getStandardForm() {
        ArrayList<Variable> newVars = new ArrayList<Variable>();
        ArrayList<Constraint> newConstraints = new ArrayList<Constraint>();
        ArrayList<String> transitions = new ArrayList<String>();
        ArrayList<Fraction> newObjCoeffs = new ArrayList<Fraction>();
        ArrayList<Fraction> newConsCoeffs = new ArrayList<Fraction>();
        Objective newObjective = new Objective();
        String newPrefix = "y";
        int currentIdx = 0;

        for (int i = 0; i < constraints.size(); i++)
            newConstraints.add(new Constraint());
        for (int i = 0; i < vars.size(); i++) {
            Variable var, var1;
            switch(vars.get(i).getConstraint()) {
                case (ConstraintTypes.GREATER_THAN):
                    var = new Variable(vars.get(i).getValue(), ++currentIdx,
                            newPrefix, ConstraintTypes.GREATER_THAN);
                    newVars.add(var);
                    transitions.add("G " + vars.get(i).getIndex() + " "
                           + currentIdx);
                    refinePositiveConstraints(newConstraints, vars.get(i));
                    refineObjective(newObjective, vars.get(i));
                    break;
                case (ConstraintTypes.LESS_THAN):
                    var = new Variable(vars.get(i).getValue(), ++currentIdx,
                            newPrefix, ConstraintTypes.GREATER_THAN);
                    newVars.add(var);
                    transitions.add("L " + vars.get(i).getIndex() + " "
                           + currentIdx);
                    refineNegativeConstraints(newConstraints, vars.get(i));
                    refineObjective(newObjective, vars.get(i));
                    break;
                case (ConstraintTypes.BELONG_R):
                    var = new Variable(vars.get(i).getValue(), ++currentIdx,
                            newPrefix, ConstraintTypes.GREATER_THAN);
                    newVars.add(var);
                    var1 = new Variable(vars.get(i).getValue(), ++currentIdx,
                            newPrefix, ConstraintTypes.GREATER_THAN);
                    newVars.add(var1);
                    transitions.add("B " + vars.get(i).getIndex() + " " +
                            (currentIdx - 1) + " " + currentIdx);
                    refineBelongsRConstraints(newConstraints, vars.get(i));
                    refineObjective(newObjective, vars.get(i));
                    break;
                default:
                    break;
            }
        }
        for (int i = 0; i < newConstraints.size(); i++)
            newConstraints.get(i).setVars(newVars);
        newObjective.setVars(newVars);
        int numOfVarsBefore = newVars.size();
        setObjective(newObjective);
        newObjective.setValue(new Fraction(0));
        addNewVariablesToGetEquations(newVars, newConstraints);
        for (int i = numOfVarsBefore; i < newVars.size(); i++)
            newObjective.getCoefs().add(new Fraction(0));
        ProblemInStandardForm stdFormProblem =
                new ProblemInStandardForm(newVars, newConstraints,
                newObjective);
        stdFormProblem.setTransitions(transitions);
//        stdFormProblem.dict = stdFormProblem.getDictionary();
        return stdFormProblem;
    }

    public String getSolution() {
        String result = "(";
        for (int i = 0; i < vars.size(); i++) {
            if (i < vars.size() - 1)
                result += vars.get(i).toString() + ", ";
            else
                result += vars.get(i).toString() + ") = (";
        }
        for (int i = 0; i < vars.size(); i++) {
            if (i < vars.size() - 1)
                result += vars.get(i).getValue() + ", ";
            else
                result += vars.get(i).getValue() + ")";
        }
        return result;
    }

    public Objective getObjective() {
        return this.objective;
    }

    public String solution() {
        String text = "";
        Problem refinedProblem = this.refinedProblem();
        ProblemInStandardForm stdFormProblem = refinedProblem.getStandardForm();
        //System.out.println(constraint.toString());
        text = "<body style=\"padding:0px 0px 0px 10px;" +
                "font-family:cambria Math;font-size:16\"><h1>Problème en forme générale</h1>";
        text += "Voici le problème en forme générale: <br /><br />";
        text += this.toString();
        text += "<p>On peut changer les variables comme ça " +
                "pour gagner le problème sous forme standarde:</p><br />";
        text += stdFormProblem.toString();
        stdFormProblem.preprocess();
        stdFormProblem.setDict();
        text += stdFormProblem.getAuxiliaryMessage();
        if (!stdFormProblem.isSolutionAdmissible()) {
            stdFormProblem.getAuxiliaryProblem();
            ProblemInStandardForm auxiliaryProblem =
                    stdFormProblem.auxiliaryProb();
            text += auxiliaryProblem.toString();
            text += auxiliaryProblem.getSolution();
            text += auxiliaryProblem.simplexMethod();
//            text += stdFormProblem.getSolution();
//            text += auxiliaryProblem.getDict();
            text += "<h1>Retour au problème original: </h1>";
            stdFormProblem.updateDict(auxiliaryProblem);
            if (!auxiliaryProblem.objective.getObjectiveValue().equals(0)) {
                return text + "<p><b><font color=\"red\">Le problème ne possède " +
                            "pas une solution réalisable.</font></b></p></body>";
            }
/*            text += stdFormProblem.getSolution();
            text += "<p><b>Valeur de l'objective = " +
                    stdFormProblem.getObjective().getObjectiveValue() + "</b></p>";*/
        }
        //text += stdFormProblem.displayDict();
        Dictionary dict = stdFormProblem.getDict();
        text += dict.toString();
        Variable inVar = null;
        Variable outVar = null;
        text += stdFormProblem.getSolution();
        text += stdFormProblem.simplexMethod();
        text += "</body>";
        return text;
    }
}