|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||
See:
Description
| Interface Summary | |
|---|---|
| LPConstraintSequence | A contiguous sequence of LP constraints. |
| LPModel | A linear programming model consisting of variables, constraints and components of the constraint matrix. |
| LPModelColumns | An LP component which can be accessed column-wise. |
| LPModelComponent | The base class for a (matrix-like) component of a linear programming model. |
| LPModelIndex | An index of a variable or a constraint in an LP model, consisting of an offset identifier and a numerical local index. |
| LPModelIndexMapping | A mapping of a pair (local index, vector label) -> global index within an LP. |
| LPModelMatrix | A matrix component of an LP model. |
| LPModelRows | An LP component which can be accessed row-wise. |
| LPModelSolver | A class which connects an LP model to a solver. |
| LPSparseVector | |
| LPVariableSequence | A contiguous sequence of variables in an LP model. |
| LPVectorLabel | A label for entries of a sparse vector in a linear program. |
| LPVectorValue | |
| MIPModelSolver | |
| Class Summary | |
|---|---|
| NoLabel | This class is used as a marker for the fact that a sparse vector does not support a label. |
Interfaces for convenient and flexible definition and composition of LP models.
Linear programs for real-world problems often share common substructures, like flow balance constraints in problems with a network flow like structure or cover constraints in problems with a set cover like flavor. The interfaces in this package try to exploit that fact by providing a convenient way to construct a linear program from individual parts. A part that has been defined for one type of LP can then easily be reused for other LPs.
There is also a corresponding package with classes that implement these interfaces and utility classes that make it easier to work with them.
LPModel is the container for a model of a problem as a linear program. It consists of constraints, variables and components (which means parts of the constraint matrix.
LPConstraintSequence represents an (ordered) sequence of constraints that shall occur in consecutive rows of the LP. The individual constraints are modelled by LPConstraint and consist ofThe location of the sequence within the overall LP is defined by a symbolic offset id. When a LP is constructed from the individual parts, an offset for the row in the overall LP will be assigned to the first constraint in the sequence. A component, i.e., a part of the constraint matrix, that refers to this constraint sequence must then have the same offset id. When the model is loaded into an LP solver, the model loader algorithm will align the components with the first row of the constraint sequence.
LPVariableSequence represents an (ordered) sequence of variables that shall occur in consecutive columns of the LP. The individual variables are modelled by LPVariable and consist of
As for the constraints, an offset id is used to identify the column where the first column in the sequence is place in the overall LP. Components with the same offset id will be aligned with this column.
LPModelComponent represents a part of the constraint matrix of the LP. It consists of
A model component support the transformation of local row resp. column indices for the component (running from 0 to the number of rows resp. columns in the component) into model indices, represented by LPModelIndex. A model index consists of a symbolic offset id and a numeric offset (starting with 0). For instance, a row model index of ('nodes', 2) corresponds to the second row in the global LP below the row that was assigned to the first constraint in constraint sequence with the offset id 'nodes'. The row model index ('nodes', 0) would correspond to exactly that row where the constraint sequence starts.
Please note that a single model component supports more than one offset id. This means that not all rows resp. columns in the component have to occur consecutively in the final LP. This will only be true for those rows resp. columns with identical offset ids.
LPModelSolver is the interface for an algorithm to load an LP model into an LP solver. After a model has been loaded, the model loader will provide the necessary transformation between model indices and the global row and column numbers in the resulting overall LP.
This sample problem is taken from Ahuja, Magnanti, Orlin. Network Flows. Prentice-Hall, Inc. 1993., p. 171-172. It shows how to convert an existing problem from its original problem domain into an LP representation within Combean.
A given matrix shall be rounded in such a way that all components and the column and rowsums are rounded either up or down to the nearest integer.
E.g. the matrix
| 3.1 | 6.8 | 7.3 |
| 9.6 | 2.4 | 0.7 |
| 3.6 | 1.2 | 6.5 |
with row sums (17.2, 12.7, 11.3) and column sums (16.3, 10.4, 14.5) can be rounded to
| 3 | 6 | 8 |
| 9 | 3 | 0 |
| 4 | 1 | 6 |
with row sums (17, 12, 11) and column sums (16, 10, 14). Of course, there are also other possible solutions.
This problem can be solved by modelling it as LP:
| max | x11 + | x12 + | x13 + | x21 + | x22 + | x23 + | x31 + | x32 + | x33 | |
| such that | ||||||||||
| 17 ≤ | x11 + | x12 + | x13 | ≤ 18 | ||||||
| 12 ≤ | x21 + | x22 + | x23 | ≤ 13 | ||||||
| 11 ≤ | x31 + | x32 + | x33 | ≤ 12 | ||||||
| 16 ≤ | x11 + | x21 + | x31 | ≤ 17 | ||||||
| 10 ≤ | x12 + | x22 + | x32 | ≤ 11 | ||||||
| 14 ≤ | x13 + | x23 + | x33 | ≤ 15 | ||||||
| 3 ≤ | x11 | ≤ 4 | ||||||||
| 6 ≤ | x12 | ≤ 7 | ||||||||
| 7 ≤ | x13 | ≤ 8 | ||||||||
| 9 ≤ | x21 | ≤ 10 | ||||||||
| 2 ≤ | x22 | ≤ 3 | ||||||||
| 0 ≤ | x23 | ≤ 1 | ||||||||
| 3 ≤ | x31 | ≤ 4 | ||||||||
| 1 ≤ | x32 | ≤ 2 | ||||||||
| 6 ≤ | x33 | ≤ 7 |
In the sequel we show how this model can be constructed and solved in Combean. You find the corresponding code in the package net.sourceforge.combean.samples.mathprog.lp.
In typical real-world application scenarios one would compose the LP from several independent components. For this simple problem, however, it suffices to construct the LP in one step. We do so by defining a single class that represents the variables, constraints and the constraint matrix of the LP:
import net.sourceforge.combean.interfaces.mathprog.lp.model.LPConstraintSequence;
import net.sourceforge.combean.interfaces.mathprog.lp.model.LPVariableSequence;
import net.sourceforge.combean.interfaces.mathprog.lp.model.LPModelRows;
import net.sourceforge.combean.mathprog.lp.model.AbstractSimpleIndexLPConstrainedRowsWithVars;
public class MatrixToRoundAsLP
extends AbstractSimpleIndexLPConstrainedRowsWithVars
implements LPModelRows, LPConstraintSequence, LPVariableSequence {
...
}
The base class AbstractSimpleIndexLPConstrainedRowsWithVars is a utility class that already takes over the handling of a single row and column index and which safes us from implementing a couple of simple but uninteresting methods. In fact we only have to implement the following methods to satisfy the given interfaces:
public int getNumColumns() {
...
}
public int getNumRows() {
...
}
public LPVariable getLPVariable(int localColumn) {
...
}
public SparseVector getRowVector(int localRow) {
...
}
public LPConstraint getLPConstraint(int localRow) {
...
}
For an m x n-matrix the resulting LP has m*n variables or columns and 2*(m+n) rows. The factor 2 stems from the fact that one LPConstraint can have only one relation symbol and our model above has a lower bound and an upper bound for each column or row sum in the original matrix. Hence, we get
public int getNumColumns() {
// one variable/column for each element of the matrix
return this.m.getNumColumns() * this.m.getNumRows();
}
public int getNumRows() {
// two constraints (<= and >= for each column and row of the matrix
return 2 * (this.m.getNumColumns() + this.m.getNumRows());
}
For the implementation of getLPVariable we simply have to map the column index in the LP to a row and column index in the original matrix M and determine the two nearest integers to the corresponding element of M. In Java, we express this as follows:
public LPVariable getLPVariable(int localColumn) {
double val = this.m.getDoubleAt(
localColumn / this.m.getNumColumns(),
localColumn % this.m.getNumColumns());
return new DoubleLPVariable(1.0, Math.floor(val), Math.ceil(val));
}
Here we use the utility class DoubleLPVariable that provides a simple implementation of the LPVariable interface by directly storing the variable coefficient in the objective function (1.0 in the example) and the lower and upper bound of the variable domain as double values.
In a similar way, we define the constraints of the LP. We just have to do some calculations to derive from the row index in the LP whether we are dealing with a ≥ or with a ≤ constraint (for odd resp. even numbers) and whether the constraint refers to a row or column sum in the original matrix. In detail, the Java code is as follows:
public LPConstraint getLPConstraint(int localRow) {
byte rel = (localRow % 2 == 0) ? LPConstraint.REL_GREATER : LPConstraint.REL_LESS;
double val = 0.0;
if (localRow >= 2*this.m.getNumRows()) {
// constraints for columns
val = this.colsums[localRow/2 - this.m.getNumRows()];
}
else {
// constraints for rows
val = this.rowsums[localRow/2];
}
if (rel == LPConstraint.REL_GREATER) {
val = Math.floor(val);
}
else {
val = Math.ceil(val);
}
return new DoubleLPConstraint(rel, val);
}
For the construction of the row vectors of the constraint matrix we make use of the fact that all coefficients in the LP are equal to one and follow a simple pattern. Either all ones in one row are directly adjacent to each other or at least the are located at equal distances from each other. Such simple rows can be represented by the utility class SparseVectorWithConstantPattern. The constructor of this utility class is defined by
/**
* Construct a vector with a constant value in a arithmetic progression.
*
* @param dim dimension of the vector
* @param val the constant value of all non-zero elements of the vector.
* @param from the start index of the non-zero block
* @param to the end index of the non-zero block
* @param incr the increment of the arithmetic progression
*/
public SparseVectorWithConstantPattern(int dim, double val,
int from, int to, int incr){
...
}
With this utility class it is easy to define the rows of the constraint matrix:
public SparseVector getRowVector(int localRow) {
SparseVector result = null;
if (localRow >= 2*this.m.getNumRows()) {
// constraints for columns
int colInOrigM = localRow/2 - this.m.getNumRows();
result = new SparseVectorWithConstantPattern(
getNumColumns(),
1.0,
colInOrigM,
colInOrigM + this.m.getNumColumns()*(this.m.getNumRows()-1),
this.m.getNumColumns());
}
else {
// constraints for rows
int rowInOrigM = localRow / 2;
result = new :(
getNumColumns(),
1.0,
rowInOrigM * this.m.getNumColumns(),
(rowInOrigM+1) * this.m.getNumColumns() - 1,
1);
}
return result;
}
This basically completes the definition of our LP and we just have to solve it. This is achieved with the following lines of code taken from the main program:
/**
* Round a given matrix such that the row sums and column sums are also
* rounded to one of the two nearest integers, i.e., row sum 12.6 may
* only become 12 or 13 but not 14.
*
* @param m the matrix to be rounded
*/
public void roundMatrix(double[][] doubleArr) {
Matrix m = new DoubleMatrix(doubleArr);
this.problemAsLP = new MatrixToRoundAsLP(m);
this.lpModel = new ConstructableLPModel();
this.lpModel.addVariableSequence(this.problemAsLP);
this.lpModel.addConstraintSequence(this.problemAsLP);
this.lpModel.appendModelComponent(this.problemAsLP);
this.modelSolver = new LPModelSolverWithSequentialLoading();
this.modelSolver.getLPSolver().setObjective(LPSolver.LPOBJ_MAX);
this.modelSolver.loadModel(this.lpModel);
this.modelSolver.solve();
}
We finally retrieve the calculated solution with the following method of MatrixToRoundAsLP:
public double[][] getRoundedMatrix(LPModelSolver solver) {
double[][] result =
new double[this.m.getNumRows()][this.m.getNumColumns()];
for (int row = 0; row < this.m.getNumRows(); row++) {
for (int col = 0; col < this.m.getNumColumns(); col++) {
result[row][col] =
solver.getSolution(getColumnModelIndex(
row * this.m.getNumColumns() + col));
}
}
return result;
}
|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||