solve.java

著名IT公司ILog的APS高级排产优化引擎

package com.power.lpsolver.LPSolve;

import java.util.*;
import java.io.*;
import java.awt.geom.*;
import com.power.util.Message.*;
import com.power.pipeengine.*;
/**
 *
 * <p>Title: PIPE Engine</p>
 * <p>Description: Global Planning Optimization Engine</p>
 * <p>Copyright: Copyright (c) 2002</p>
 * <p>Company: Paraster, Inc.</p>
 * @author Wei Tan
 * @version 1.0
 */

/**
 * Solve implements the Simplex algorithm. It provides methods that handles the
 * iteration process of the Simplex algorithm. It is a singular class.
 */
public class Solve
{
    static ResourceBundle res = ResourceBundle.getBundle("com.power.lpsolver.LPSolve.Res",
                                                          EngineConfig.getInstance().getLocale() );
    private static final Solve INSTANCE =
                              new Solve();

    /**
     * Default constructor.
     */
    private Solve( ) {
    }

    public static Solve getInstance( ) {
        return INSTANCE;
    }

    /**
     * a Hashtable that stores all basic variable indice.
     */
    private Hashtable _basicVariables = new Hashtable();

    /**
     * current pivotal row number.
     */
    private int _pivotRow;

    /**
     * current pivotal column number.
     */
    private int _pivotCol;

    /**
     * current iteration number. Used for both Phase I and Phase II. Reset for
     * Phase II.
     */
    private int _iterNum = 1;

    /**
     * stores the optimal solution. The key is a variable's symbolic name, the
     * value is the variable's value in the solution.
     */
     private Hashtable _solution = new Hashtable();

     /**
      * stores the current optimization phase, may only be
      *   0 - one phase algorithm
      *   1 - phase I of two-phase algortihm
      *   2 - phase II of two-phase algorithm
      */
     private int _currentPhase = 0;


     /**
      * Report the size of the model. Number of rows and number of columns
      */
    private void reportModelSize() {
        Model mdl = Model.getInstance();
        String numOfCols = res.getString( "Number of Columns" );
        MessageArea.getInstance().addMessage( numOfCols + ": " + mdl.getNumberOfColumns() );
        String numOfRows = res.getString( "Number of Rows" );
        MessageArea.getInstance().addMessage( numOfRows + ": " + mdl.getNumberOfRows() );
    }


     /**
      * Solves the model in memory.
      */
     public void solve() {

        Model mdl = Model.getInstance();

        reportModelSize();

        //initialization - introduce slack/surplus/artificial variables
        mdl.initialize();

        if( mdl.needTwoPhaseSimplex() ) {
            String msg = res.getString("LPSolve2010");
            MessageArea.getInstance().addMessage( msg );
            mdl.setModelForPhaseOne();
            msg = res.getString("LPSolve2020");
            MessageArea.getInstance().addMessage( msg );
            _currentPhase = 1;
       }

        //optimality test
        _iterNum = 0;
        int status;
        /*while( ! mdl.getObjectiveFunction().isOptimal() ) {
            System.out.print( "Iteration " + _iterNum + ":" );
            //Model.getInstance().getObjectiveFunction().print();
            this.startIteration();
            _iterNum++;
        }*/

        //System.out.print( "Iteration " + _iterNum + ":" );
        while( ( status = this.startIteration( _iterNum ) ) != 1000 ) {
            _iterNum++;
        }


        if( isProblemInfeasible() ) {
            String msg = res.getString("LPSolve2050");
            MessageArea.getInstance().addMessage( msg );
            System.exit( 0 );
        }

        if( mdl.needTwoPhaseSimplex() ) {
            removeArtificialBasicVariables();
            String msg = res.getString("LPSolve2030");
            ObjectiveValuePlot.getInstance().clear();
            MessageArea.getInstance().addMessage( msg );

            mdl.setModelForPhaseTwo();
            _currentPhase = 2;

            _iterNum = 1;
            while( ( status = this.startIteration( _iterNum ) ) != 1000 ) {
                _iterNum++;
            }
        }

		//mdl.print();

        createSolution();
		//System.out.println( _basicVariables );
		//mdl.getObjectiveFunction().print();
    }

    /**
     * Gets basic variables Hashtable.
     * @return the basic variables Hashtable.
     */
    public Hashtable getBasicVariables() {
        return _basicVariables;
    }

    /**
     * Updates the basic variables Hashtable by removing an existing entry and
     * adding an incoming entry.
     * @param enteringVarIdx
     * @param leavingVarIdx
     */
    public void updateBasicVariables( int enteringVarIdx, int leavingVarIdx ) {
        MemoryManager memMgr = MemoryManager.getInstance();
        String key = memMgr.getIntegerString( leavingVarIdx );
        _basicVariables.remove( key );
        //Integer newBasic = new Integer( enteringVarIdx );
        _basicVariables.put( memMgr.getIntegerString( enteringVarIdx ),
                                                 memMgr.getInteger( enteringVarIdx ) );
    }

    /**
     * Tests to see if the problem is feasible.
     * @return <code>true</code> if it is;
     *         <code>false></code> otherwise.
     */
    public boolean isProblemInfeasible() {
        Vector cons = Model.getInstance().getModelConstraints().getConstraints();
        for( int i=0; i<cons.size(); i++ ) {
                Constraint con = (Constraint) cons.elementAt( i );
                if( con.getRHS() == 0.0 ) continue;
                int basicVarIdx = con.getBasicVariableIndex();
                Variable var = Model.getInstance().getModelVariables().getVariable( basicVarIdx );
                if( var.getVarName().indexOf( "ART" ) == 0 ) return true;
        }

        return false;
    }

    /**
     * Starts an iteration.
     * @param iterNum the current iteration number.
     * @return the status of the iteration:
     *         1000 - when optimal reached;
     *         0    - normal return.
     */
    public int startIteration( int iterNum ) {
        Model mdl = Model.getInstance();
        _pivotCol = mdl.getObjectiveFunction().getPivotColumn();

        //return when optimal solution found
        if( _pivotCol < 0 ) {
            String msg = res.getString("Engine2500");
            if( _currentPhase != 0 ) {
                if( _currentPhase == 1 ) {
                    msg += res.getString("Phase_I");
                } else {
                    msg += res.getString("Phase_II");
                }
            }

            double objValue = mdl.getObjectiveFunction().getRHS();

            ObjectiveValuePlot.getInstance().addPoint(
                  new Point2D.Double( (double) iterNum, objValue ) );

            MessageArea.getInstance().addMessage( res.getString("Iteration_") + iterNum + "\t\t" +
                  mdl.getObjectiveFunction().getRHS() + "\n" );

            msg += res.getString("completed_Optimal");
            MessageArea.getInstance().addMessage( msg );
            return 1000;
        }

        _pivotRow = mdl.getModelConstraints().getPivotRowNumber( _pivotCol );

        Constraint pivotCon = mdl.getModelConstraints().getConsrtaint( _pivotRow );
        double pivotNumber = pivotCon.getElementAt( _pivotCol ).getCoefficient();
        pivotCon.applyMultiplier( 1.0 / pivotNumber );

        int leavingBasicVar = pivotCon.getBasicVariableIndex();

        mdl.getModelConstraints().gaussianEliminationByRow( _pivotRow, _pivotCol );
        Solve.getInstance().updateBasicVariables( _pivotCol, leavingBasicVar );
        pivotCon.setBasicVariableIndex( _pivotCol );

        //double objValue = Math.abs( mdl.getObjectiveFunction().getRHS() );
        double objValue = mdl.getObjectiveFunction().getRHS();

        if( (iterNum % EngineConfig.getInstance().getUpdateInterval() ) == 0 ) {
            ObjectiveValuePlot.getInstance().addPoint(
                  new Point2D.Double( (double) iterNum, objValue ) );

            MessageArea.getInstance().addMessage( res.getString("Iteration_") + iterNum + "\t\t" +
                  mdl.getObjectiveFunction().getRHS() + "\n" );
        }
        return 0;
    }

    /**
     * Adds a basic variable.
     * @param idx the index of the variable to be added.
     */
    public void addBasicVariable( Integer idx ) {
        _basicVariables.put( idx.toString(), idx );
    }

    /**
     * Prints the current solution.
     */
    public void printSolution() {
        Model mdl = Model.getInstance();
        ModelConstraints constraints = mdl.getModelConstraints();


        Vector allCons = constraints.getConstraints();
        for( int i=0; i<allCons.size(); i++ ) {
                Constraint con = (Constraint) allCons.elementAt( i );
                con.printSolution();
        }

    }

    /**
     * Creates a solution and stores it in a solution class.
     */
    public void createSolution() {
        String msg = res.getString("Engine2600");
        MessageArea.getInstance().addMessage( msg );
        Vector cons = Model.getInstance().getModelConstraints().getConstraints();
        int totOriginalVars = Model.getInstance().getTotOriginalVariables();

        /*for( int i=0; i<cons.size(); i++ ) {
                Constraint con = (Constraint) cons.elementAt( i );
                if( con.getRHS() == 0.0 ) continue;
                int basicVarIdx = con.getBasicVariableIndex();
                if( basicVarIdx >= totOriginalVars ) continue;

                Variable var = Model.getInstance().getModelVariables().getVariable( basicVarIdx );
                _solution.put( var.getVarName(), new Double( con.getRHS() ) );
                //System.out.println( var.getVarName() + "\t" + con.getRHS() );
        }*/
        BufferedReader d = null;
        try{
            FileInputStream r = new FileInputStream( "C:\\paraster\\lpsolver\\model.out" );
            d = new BufferedReader( new InputStreamReader( r ) );
        } catch (Exception e ) {
            MessageArea.getInstance().addMessage( "Error: " + e.getMessage() + "\n" );
        }

        if( null == d ) {
          return;
        }

        try{
            //read and discard
            String aLine = d.readLine();
            String token = " ";

            aLine = d.readLine();

            while( aLine != null ) {
                if( aLine.length() <= 1 ) {
                    break;
                }
                StringTokenizer st = new StringTokenizer( aLine, token );
                String varMPSName = new String( st.nextToken() );
                Double varValue = new Double( st.nextToken() );

                if( varValue.doubleValue() != 0 ) {
                    _solution.put( Model.getInstance().getRegularVarName( varMPSName ),
                                   varValue );
                }

                aLine = d.readLine();
            }

            d.close();
        } catch (Exception e) {
            MessageArea.getInstance().addMessage( "Error: " + e.getMessage() + "\n" );
        }


    }

    /**
     * Gets the current incubent solution.
     * @return
     */
    public Hashtable getSolution() {
        return _solution;
    }

    /**
     * Removes the artificial variables after Phase I and before starting Phase II.
     */
    public void removeArtificialBasicVariables( ) {
        Model mdl = Model.getInstance();
        _pivotCol = mdl.getObjectiveFunction().getPivotColumn();

        Vector allCons = mdl.getModelConstraints().getConstraints();

        for( int i=0; i<allCons.size(); i++ ) {
              Constraint con = (Constraint) allCons.elementAt( i );

              int leavingVarIdx = con.getBasicVariableIndex();
              //if( null == _basicVariables.get( MemoryManager.getInstance().getIntegerString( leavingVarIdx ) ) ) {
                      //continue;
              //}

              if( false == mdl.isArtVarIndex( leavingVarIdx ) ) continue;

              //con.print();
              _pivotRow = i;
              _pivotCol = con.getColIdxOfFirstPositiveCoefficient();


              //return when optimal solution found
              if( _pivotCol < 0 ) {
                      MessageArea.getInstance().addMessage( res.getString("LPSolver2000_Remove") );
                      mdl.getModelConstraints().removeConstraint( con );
                      i--;
                      continue;
              }

              double pivotNumber = con.getElementAt( _pivotCol ).getCoefficient();
              con.applyMultiplier( 1.0 / pivotNumber );

              mdl.getModelConstraints().gaussianEliminationByRow( _pivotRow, _pivotCol );
              this.updateBasicVariables( _pivotCol, leavingVarIdx );
              con.setBasicVariableIndex( _pivotCol );

              mdl.normalize();

        }

    }

    /**
     * Tests to see if a variable index is a basic variable index.
     * @param idx the index to be tested.
     * @return <code>true</code> if it is a basic variable index.
     *         <code>false</code> otherwise.
     */
    public boolean isBasicVariable( int idx ) {
        Integer anInt = (Integer) _basicVariables.get( MemoryManager.getInstance().getIntegerString( idx ) );
        if( null != anInt ) {
                return true;
        }

        return false;
    }
}