1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
|
7 | |
|
8 | |
|
9 | |
|
10 | |
|
11 | |
|
12 | |
|
13 | |
|
14 | |
|
15 | |
|
16 | |
|
17 | |
|
18 | |
|
19 | |
|
20 | |
|
21 | |
|
22 | |
package net.sourceforge.combean.graph.alg.flow; |
23 | |
|
24 | |
import org.apache.commons.logging.Log; |
25 | |
import org.apache.commons.logging.LogFactory; |
26 | |
|
27 | |
import net.sourceforge.combean.graph.alg.AbstractGraphAlg; |
28 | |
import net.sourceforge.combean.graph.alg.lp.EdgesAsLPVariableSequence; |
29 | |
import net.sourceforge.combean.graph.alg.lp.GraphAsLPModelColumns; |
30 | |
import net.sourceforge.combean.graph.alg.lp.LPModelSolverAsFixedDoubleEdgeMap; |
31 | |
import net.sourceforge.combean.graph.alg.lp.NodesAsLPConstraintSequence; |
32 | |
import net.sourceforge.combean.graph.containers.doubleval.ScalingDoubleNodeMapDecorator; |
33 | |
import net.sourceforge.combean.interfaces.graph.alg.flow.MinCostFlowAlg; |
34 | |
import net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleEdgeMap; |
35 | |
import net.sourceforge.combean.interfaces.graph.containers.doubleval.FixedDoubleNodeMap; |
36 | |
import net.sourceforge.combean.interfaces.graph.prop.GlobalNumberedGraphProp; |
37 | |
import net.sourceforge.combean.interfaces.graph.prop.NeighborhoodGraphProp; |
38 | |
import net.sourceforge.combean.interfaces.mathprog.lp.LPConstraint; |
39 | |
import net.sourceforge.combean.interfaces.mathprog.lp.LPSolver; |
40 | |
import net.sourceforge.combean.interfaces.mathprog.lp.model.LPModelSolver; |
41 | |
import net.sourceforge.combean.mathprog.lp.model.ConstructableLPModel; |
42 | |
import net.sourceforge.combean.mathprog.lp.model.LPModelSolverWithSequentialLoading; |
43 | |
import net.sourceforge.combean.util.except.IllegalParameterException; |
44 | |
|
45 | |
|
46 | |
|
47 | |
|
48 | |
|
49 | |
|
50 | |
|
51 | |
public class MinCostFlowByLPAlg extends AbstractGraphAlg implements |
52 | |
MinCostFlowAlg { |
53 | |
|
54 | 3 | private static Log log = LogFactory.getLog(MinCostFlowByLPAlg.class); |
55 | |
|
56 | 9 | private NeighborhoodGraphProp neigh = null; |
57 | 9 | private GlobalNumberedGraphProp numberedGraph = null; |
58 | |
|
59 | 9 | private LPSolver lpSolver = null; |
60 | 9 | private LPModelSolver lpModelSolver = null; |
61 | |
|
62 | 9 | private FixedDoubleNodeMap inflow = null; |
63 | |
|
64 | 9 | private FixedDoubleEdgeMap edgeWeights = null; |
65 | 9 | private FixedDoubleEdgeMap edgeCapacities = null; |
66 | |
|
67 | |
|
68 | |
|
69 | |
|
70 | |
public MinCostFlowByLPAlg() { |
71 | 9 | super(); |
72 | 9 | } |
73 | |
|
74 | |
|
75 | |
|
76 | |
|
77 | |
public final void setLpModelLoader(LPModelSolver lpModelLoader) { |
78 | 0 | this.lpModelSolver = lpModelLoader; |
79 | 0 | } |
80 | |
|
81 | |
|
82 | |
|
83 | |
|
84 | |
public final void setLpSolver(LPSolver lpSolver) { |
85 | 9 | this.lpSolver = lpSolver; |
86 | 9 | } |
87 | |
|
88 | |
|
89 | |
|
90 | |
|
91 | |
public void setEdgeWeightsMap(FixedDoubleEdgeMap edgeWeights) { |
92 | 9 | this.edgeWeights = edgeWeights; |
93 | 9 | } |
94 | |
|
95 | |
|
96 | |
|
97 | |
|
98 | |
public void setInflowMap(FixedDoubleNodeMap inflowMap) { |
99 | 9 | this.inflow = inflowMap; |
100 | 9 | } |
101 | |
|
102 | |
|
103 | |
|
104 | |
|
105 | |
public void setEdgeCapacityMap(FixedDoubleEdgeMap edgeCapacities) { |
106 | 9 | this.edgeCapacities = edgeCapacities; |
107 | 9 | } |
108 | |
|
109 | |
|
110 | |
|
111 | |
|
112 | |
public void run() { |
113 | 9 | if (this.lpModelSolver == null) { |
114 | 9 | this.lpModelSolver = new LPModelSolverWithSequentialLoading(); |
115 | |
} |
116 | 9 | if (this.lpSolver == null) { |
117 | 0 | throw new IllegalParameterException("LP-solver must be set."); |
118 | |
} |
119 | 9 | this.lpModelSolver.setLPSolver(this.lpSolver); |
120 | |
|
121 | 9 | GraphAsLPModelColumns networkLPComponent = |
122 | |
new GraphAsLPModelColumns("flow", "bal", this.neigh); |
123 | |
|
124 | 9 | NodesAsLPConstraintSequence nodeFlowBalanceConstraints = |
125 | |
new NodesAsLPConstraintSequence("bal", this.numberedGraph); |
126 | 9 | nodeFlowBalanceConstraints.setNodeRhs( |
127 | |
new ScalingDoubleNodeMapDecorator(this.inflow, -1.0)); |
128 | 9 | nodeFlowBalanceConstraints.setRelation(LPConstraint.REL_EQUAL); |
129 | |
|
130 | 9 | EdgesAsLPVariableSequence edgeFlowVariables = |
131 | |
new EdgesAsLPVariableSequence("flow", this.numberedGraph); |
132 | 9 | edgeFlowVariables.setEdgeCost(this.edgeWeights); |
133 | 9 | edgeFlowVariables.setEdgeUpperBound(this.edgeCapacities); |
134 | |
|
135 | 9 | ConstructableLPModel lpModel = new ConstructableLPModel(); |
136 | 9 | lpModel.addConstraintSequence(nodeFlowBalanceConstraints); |
137 | 9 | lpModel.addVariableSequence(edgeFlowVariables); |
138 | 9 | lpModel.appendModelComponent(networkLPComponent); |
139 | |
|
140 | 9 | this.lpModelSolver.loadModel(lpModel); |
141 | |
|
142 | 9 | if (log.isInfoEnabled()) { |
143 | 0 | log.info("Starting LP-solver " + this.lpModelSolver.getLPSolver()); |
144 | |
} |
145 | |
|
146 | 9 | this.lpModelSolver.solve(); |
147 | |
|
148 | 9 | if (log.isInfoEnabled()) { |
149 | 0 | log.info("LP-solver terminated with state " + |
150 | |
this.lpSolver.getSolutionStatus()); |
151 | |
} |
152 | |
|
153 | 9 | if (this.lpSolver.getSolutionStatus() == LPSolver.LPSTAT_FAILURE) { |
154 | 0 | throw new IllegalParameterException("LP-solver failed"); |
155 | |
} |
156 | 9 | if (this.lpSolver.getSolutionStatus() == LPSolver.LPSTAT_UNBOUNDED) { |
157 | 0 | throw new IllegalParameterException("LP-solver returns unbounded flow"); |
158 | |
} |
159 | 9 | } |
160 | |
|
161 | |
|
162 | |
|
163 | |
|
164 | |
public boolean isFeasible() { |
165 | 9 | return this.lpSolver.getSolutionStatus() == LPSolver.LPSTAT_SOLVED; |
166 | |
} |
167 | |
|
168 | |
|
169 | |
|
170 | |
|
171 | |
public double getTotalCost() { |
172 | 3 | return this.lpSolver.getSolutionValue(); |
173 | |
} |
174 | |
|
175 | |
|
176 | |
|
177 | |
|
178 | |
public FixedDoubleEdgeMap getFlowMap() { |
179 | 3 | return new LPModelSolverAsFixedDoubleEdgeMap(this.lpModelSolver, |
180 | |
this.numberedGraph, "flow"); |
181 | |
} |
182 | |
} |