Coverage Report - net.sourceforge.combean.samples.mathprog.lp.matrixrounding.MatrixToRoundAsLP
 
Classes in this File Line Coverage Branch Coverage Complexity
MatrixToRoundAsLP
100%
38/38
100%
16/16
2
 
 1  
 /*
 2  
     This file is part of Combean.
 3  
 
 4  
     Combean is free software; you can redistribute it and/or modify
 5  
     it under the terms of the GNU General Public License as published by
 6  
     the Free Software Foundation; either version 2 of the License, or
 7  
     (at your option) any later version.
 8  
 
 9  
     Combean is distributed in the hope that it will be useful,
 10  
     but WITHOUT ANY WARRANTY; without even the implied warranty of
 11  
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 12  
     GNU General Public License for more details.
 13  
 
 14  
     You should have received a copy of the GNU General Public License
 15  
     along with Combean; if not, write to the Free Software
 16  
     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 17  
 */
 18  
 /*
 19  
  * Created on 04.08.2006
 20  
  *
 21  
  */
 22  
 package net.sourceforge.combean.samples.mathprog.lp.matrixrounding;
 23  
 
 24  
 
 25  
 
 26  
 import net.sourceforge.combean.interfaces.mathprog.linalg.Matrix;
 27  
 import net.sourceforge.combean.interfaces.mathprog.linalg.SparseVector;
 28  
 import net.sourceforge.combean.interfaces.mathprog.linalg.VectorOrientation;
 29  
 import net.sourceforge.combean.interfaces.mathprog.lp.LPConstraint;
 30  
 import net.sourceforge.combean.interfaces.mathprog.lp.LPVariable;
 31  
 import net.sourceforge.combean.interfaces.mathprog.lp.model.LPConstraintSequence;
 32  
 import net.sourceforge.combean.interfaces.mathprog.lp.model.LPModelRows;
 33  
 import net.sourceforge.combean.interfaces.mathprog.lp.model.LPModelSolver;
 34  
 import net.sourceforge.combean.interfaces.mathprog.lp.model.LPSparseVector;
 35  
 import net.sourceforge.combean.interfaces.mathprog.lp.model.LPVariableSequence;
 36  
 import net.sourceforge.combean.mathprog.linalg.SparseVectorWithConstantPattern;
 37  
 import net.sourceforge.combean.mathprog.linalg.statics.SparseVectorUtil;
 38  
 import net.sourceforge.combean.mathprog.lp.DoubleLPConstraint;
 39  
 import net.sourceforge.combean.mathprog.lp.DoubleLPVariable;
 40  
 import net.sourceforge.combean.mathprog.lp.model.AbstractSimpleIndexLPConstrainedRowsWithVars;
 41  
 import net.sourceforge.combean.mathprog.lp.model.SparseVectorAsLPVector;
 42  
 
 43  
 /**
 44  
  * A matrix rounding problem as linear program.
 45  
  * 
 46  
  * @author schickin
 47  
  *
 48  
  */
 49  
 public class MatrixToRoundAsLP
 50  
 extends AbstractSimpleIndexLPConstrainedRowsWithVars
 51  
 implements LPModelRows, LPConstraintSequence, LPVariableSequence {
 52  
     
 53  6
     private Matrix m = null;
 54  
     
 55  6
     private double[] rowsums = null;
 56  6
     private double[] colsums = null;
 57  
 
 58  
     /**
 59  
      * Constructor
 60  
      * 
 61  
      * @param matrixToRound the matrix to be rounded
 62  
      */
 63  
     public MatrixToRoundAsLP(Matrix matrixToRound) {
 64  6
         super("", "");
 65  
         
 66  6
         this.m = matrixToRound;
 67  
         
 68  6
         this.rowsums = new double[this.m.getNumRows()];
 69  24
         for (int row = 0; row < this.rowsums.length; row++) {
 70  18
             this.rowsums[row] =
 71  
                 SparseVectorUtil.sum(this.m.getRowVector(row));
 72  
         }
 73  
 
 74  6
         this.colsums = new double[this.m.getNumColumns()];
 75  24
         for (int col = 0; col < this.colsums.length; col++) {
 76  18
             this.colsums[col] =
 77  
                 SparseVectorUtil.sum(this.m.getColumnVector(col));
 78  
         }
 79  6
     }
 80  
 
 81  
     /* (non-Javadoc)
 82  
      * @see net.sourceforge.combean.interfaces.mathprog.linalg.AbstractMatrix#getNumColumns()
 83  
      */
 84  
     public int getNumColumns() {
 85  
         // one variable/column for each element of the matrix
 86  300
         return this.m.getNumColumns() * this.m.getNumRows();
 87  
     }
 88  
 
 89  
     /* (non-Javadoc)
 90  
      * @see net.sourceforge.combean.interfaces.mathprog.linalg.AbstractMatrix#getNumRows()
 91  
      */
 92  
     public int getNumRows() {
 93  
         // two constraints (<= and >= for each column and row of the matrix
 94  84
         return 2 * (this.m.getNumColumns() + this.m.getNumRows());
 95  
     }
 96  
 
 97  
 
 98  
     /* (non-Javadoc)
 99  
      * @see net.sourceforge.combean.interfaces.mathprog.lp.model.LPVariableSequence#getLPVariable(int)
 100  
      */
 101  
     public LPVariable getLPVariable(int localColumn) {
 102  54
         double val = this.m.getDoubleAt(
 103  
                 localColumn / this.m.getNumColumns(),
 104  
                 localColumn % this.m.getNumColumns());
 105  
         // this funny objective functions assigns high values to the variables
 106  
         // with low column numbers and thus forces a solution where these
 107  
         // variables are as small or big as possible (depending on the
 108  
         // objective function, i.e., whether we are maximizing or minimizing).
 109  
         // In any case the resulting solution is unique (which is important for
 110  
         // automated unit testing)..
 111  54
         return new DoubleLPVariable((localColumn + 1.0)*(localColumn + 1.0)
 112  
                 + getNumVars()*getNumVars()*getNumVars(),
 113  
                 Math.floor(val), Math.ceil(val));
 114  
         // for a non-unique solution it would suffixe to set:
 115  
         // return new DoubleLPVariable(1.0, Math.floor(val), Math.ceil(val));
 116  
     }
 117  
     
 118  
     /* (non-Javadoc)
 119  
      * @see net.sourceforge.combean.interfaces.mathprog.linalg.RowMatrix#getRowVector(int)
 120  
      */
 121  
     public LPSparseVector getRowVector(int localRow) {
 122  72
         SparseVector result = null;
 123  
         
 124  72
         if (localRow >= 2*this.m.getNumRows()) {
 125  
             // constraints for columns
 126  36
             int colInOrigM = localRow/2 - this.m.getNumRows();
 127  36
             result = new SparseVectorWithConstantPattern(
 128  
                     getNumColumns(),
 129  
                     1.0,
 130  
                     colInOrigM,
 131  
                     colInOrigM + this.m.getNumColumns()*(this.m.getNumRows()-1),
 132  
                     this.m.getNumColumns());
 133  36
         }
 134  
         else {
 135  
             // constraints for rows
 136  36
             int rowInOrigM = localRow / 2;
 137  36
             result = new SparseVectorWithConstantPattern (
 138  
                     getNumColumns(),
 139  
                     1.0,
 140  
                     rowInOrigM * this.m.getNumColumns(),
 141  
                     (rowInOrigM+1) * this.m.getNumColumns() - 1,
 142  
                     1);
 143  
         }
 144  
         
 145  72
         return new SparseVectorAsLPVector(result, "",
 146  
                 VectorOrientation.ROWWISE);
 147  
     }
 148  
 
 149  
     /* (non-Javadoc)
 150  
      * @see net.sourceforge.combean.interfaces.mathprog.lp.model.LPConstraintSequence#getLPConstraint(int)
 151  
      */
 152  
     public LPConstraint getLPConstraint(int localRow) {
 153  72
         byte rel = (localRow % 2 == 0) ? LPConstraint.REL_GREATER : LPConstraint.REL_LESS;
 154  
         
 155  72
         double val = 0.0;
 156  72
         if (localRow >= 2*this.m.getNumRows()) {
 157  
             // constraints for columns
 158  36
             val = this.colsums[localRow/2 - this.m.getNumRows()];
 159  
         }
 160  
         else {
 161  
             // constraints for rows
 162  36
             val = this.rowsums[localRow/2];
 163  
         }
 164  72
         if (rel == LPConstraint.REL_GREATER) {
 165  36
             val = Math.floor(val);
 166  
         }
 167  
         else {
 168  36
             val = Math.ceil(val);
 169  
         }
 170  
         
 171  72
         return new DoubleLPConstraint("row", rel, val);
 172  
     }
 173  
     
 174  
     /**
 175  
      * Translate the result of the solver back into a matrix of doubles
 176  
      * 
 177  
      * @param solver the solver which has solved the model "this".
 178  
      * @return the result given by the solver converted to a matrix of doubles.
 179  
      */
 180  
     public double[][] getRoundedMatrix(LPModelSolver solver) {
 181  6
         double[][] result =
 182  
             new double[this.m.getNumRows()][this.m.getNumColumns()];
 183  
         
 184  24
         for (int row = 0; row < this.m.getNumRows(); row++) {
 185  72
             for (int col = 0; col < this.m.getNumColumns(); col++) {
 186  54
                 result[row][col] =
 187  
                     solver.getSolution(getColumnModelIndex(
 188  
                             row * this.m.getNumColumns() + col));
 189  
             }
 190  
         }
 191  
         
 192  6
         return result;
 193  
     }
 194  
 }