1// Copyright (C) 2005, International Business Machines
2// Corporation and others. All Rights Reserved.
3// This code is licensed under the terms of the Eclipse Public License (EPL).
4
5#if defined(_MSC_VER)
6// Turn off compiler warning about long names
7# pragma warning(disable:4786)
8#endif
9
10#include "CoinHelperFunctions.hpp"
11#include "CoinWarmStartBasis.hpp"
12
13#include "OsiConfig.h"
14#include "CoinFinite.hpp"
15
16#include "OsiSolverInterface.hpp"
17#include "OsiSolverBranch.hpp"
18#include <cassert>
19#include <cmath>
20#include <cfloat>
21//#############################################################################
22// Constructors / Destructor / Assignment
23//#############################################################################
24
25//-------------------------------------------------------------------
26// Default Constructor
27//-------------------------------------------------------------------
28OsiSolverBranch::OsiSolverBranch () :
29 indices_(NULL),
30 bound_(NULL)
31{
32 memset(start_,0,sizeof(start_));
33}
34
35//-------------------------------------------------------------------
36// Copy constructor
37//-------------------------------------------------------------------
38OsiSolverBranch::OsiSolverBranch (const OsiSolverBranch & rhs)
39{
40 memcpy(start_,rhs.start_,sizeof(start_));
41 int size = start_[4];
42 if (size) {
43 indices_ = CoinCopyOfArray(rhs.indices_,size);
44 bound_ = CoinCopyOfArray(rhs.bound_,size);
45 } else {
46 indices_=NULL;
47 bound_=NULL;
48 }
49}
50
51//-------------------------------------------------------------------
52// Destructor
53//-------------------------------------------------------------------
54OsiSolverBranch::~OsiSolverBranch ()
55{
56 delete [] indices_;
57 delete [] bound_;
58}
59
60//----------------------------------------------------------------
61// Assignment operator
62//-------------------------------------------------------------------
63OsiSolverBranch &
64OsiSolverBranch::operator=(const OsiSolverBranch& rhs)
65{
66 if (this != &rhs) {
67 delete [] indices_;
68 delete [] bound_;
69 memcpy(start_,rhs.start_,sizeof(start_));
70 int size = start_[4];
71 if (size) {
72 indices_ = CoinCopyOfArray(rhs.indices_,size);
73 bound_ = CoinCopyOfArray(rhs.bound_,size);
74 } else {
75 indices_=NULL;
76 bound_=NULL;
77 }
78 }
79 return *this;
80}
81
82//-----------------------------------------------------------------------------
83// add simple branch
84//-----------------------------------------------------------------------------
85
86void
87OsiSolverBranch::addBranch(int iColumn, double value)
88{
89 delete [] indices_;
90 delete [] bound_;
91 indices_ = new int[2];
92 bound_ = new double[2];
93 indices_[0]=iColumn;
94 indices_[1]=iColumn;
95 start_[0]=0;
96 start_[1]=0;
97 start_[2]=1;
98 bound_[0]=floor(value);
99 start_[3]=2;
100 bound_[1]=ceil(value);
101 start_[4]=2;
102 assert (bound_[0]!=bound_[1]);
103}
104//-----------------------------------------------------------------------------
105// Add bounds - way =-1 is first , +1 is second
106//-----------------------------------------------------------------------------
107
108void
109OsiSolverBranch::addBranch(int way,int numberTighterLower, const int * whichLower,
110 const double * newLower,
111 int numberTighterUpper, const int * whichUpper, const double * newUpper)
112{
113 assert (way==-1||way==1);
114 int numberNew = numberTighterLower+numberTighterUpper;
115 int base = way+1; // will be 0 or 2
116 int numberNow = start_[4-base]-start_[2-base];
117 int * tempI = new int[numberNow+numberNew];
118 double * tempD = new double[numberNow+numberNew];
119 int putNew = (way==-1) ? 0 : start_[2];
120 int putNow = (way==-1) ? numberNew : 0;
121 memcpy(tempI+putNow,indices_+start_[2-base],numberNow*sizeof(int));
122 memcpy(tempD+putNow,bound_+start_[2-base],numberNow*sizeof(double));
123 memcpy(tempI+putNew,whichLower,numberTighterLower*sizeof(int));
124 memcpy(tempD+putNew,newLower,numberTighterLower*sizeof(double));
125 putNew += numberTighterLower;
126 memcpy(tempI+putNew,whichUpper,numberTighterUpper*sizeof(int));
127 memcpy(tempD+putNew,newUpper,numberTighterUpper*sizeof(double));
128 delete [] indices_;
129 indices_ = tempI;
130 delete [] bound_;
131 bound_ = tempD;
132 int numberOldLower = start_[3-base]-start_[2-base];
133 int numberOldUpper = start_[4-base]-start_[3-base];
134 start_[0]=0;
135 if (way==-1) {
136 start_[1] = numberTighterLower;
137 start_[2] = start_[1] + numberTighterUpper;
138 start_[3] = start_[2] + numberOldLower;
139 start_[4] = start_[3] + numberOldUpper;
140 } else {
141 start_[1] = numberOldLower;
142 start_[2] = start_[1] + numberOldUpper;
143 start_[3] = start_[2] + numberTighterLower;
144 start_[4] = start_[3] + numberTighterUpper;
145 }
146}
147//-----------------------------------------------------------------------------
148// Add bounds - way =-1 is first , +1 is second
149//-----------------------------------------------------------------------------
150
151void
152OsiSolverBranch::addBranch(int way,int numberColumns, const double * oldLower,
153 const double * newLower2,
154 const double * oldUpper, const double * newUpper2)
155{
156 assert (way==-1||way==1);
157 // find
158 int i;
159 int * whichLower = new int[numberColumns];
160 double * newLower = new double[numberColumns];
161 int numberTighterLower=0;
162 for (i=0;i<numberColumns;i++) {
163 if (newLower2[i]>oldLower[i]) {
164 whichLower[numberTighterLower]=i;
165 newLower[numberTighterLower++]=newLower2[i];
166 }
167 }
168 int * whichUpper = new int[numberColumns];
169 double * newUpper = new double[numberColumns];
170 int numberTighterUpper=0;
171 for (i=0;i<numberColumns;i++) {
172 if (newUpper2[i]<oldUpper[i]) {
173 whichUpper[numberTighterUpper]=i;
174 newUpper[numberTighterUpper++]=newUpper2[i];
175 }
176 }
177 int numberNew = numberTighterLower+numberTighterUpper;
178 int base = way+1; // will be 0 or 2
179 int numberNow = start_[4-base]-start_[2-base];
180 int * tempI = new int[numberNow+numberNew];
181 double * tempD = new double[numberNow+numberNew];
182 int putNew = (way==-1) ? 0 : start_[2];
183 int putNow = (way==-1) ? numberNew : 0;
184 memcpy(tempI+putNow,indices_+start_[2-base],numberNow*sizeof(int));
185 memcpy(tempD+putNow,bound_+start_[2-base],numberNow*sizeof(double));
186 memcpy(tempI+putNew,whichLower,numberTighterLower*sizeof(int));
187 memcpy(tempD+putNew,newLower,numberTighterLower*sizeof(double));
188 putNew += numberTighterLower;
189 memcpy(tempI+putNew,whichUpper,numberTighterUpper*sizeof(int));
190 memcpy(tempD+putNew,newUpper,numberTighterUpper*sizeof(double));
191 delete [] indices_;
192 indices_ = tempI;
193 delete [] bound_;
194 bound_ = tempD;
195 int numberOldLower = start_[3-base]-start_[2-base];
196 int numberOldUpper = start_[4-base]-start_[3-base];
197 start_[0]=0;
198 if (way==-1) {
199 start_[1] = numberTighterLower;
200 start_[2] = start_[1] + numberTighterUpper;
201 start_[3] = start_[2] + numberOldLower;
202 start_[4] = start_[3] + numberOldUpper;
203 } else {
204 start_[1] = numberOldLower;
205 start_[2] = start_[1] + numberOldUpper;
206 start_[3] = start_[2] + numberTighterLower;
207 start_[4] = start_[3] + numberTighterUpper;
208 }
209 delete [] whichLower;
210 delete [] newLower;
211 delete [] whichUpper;
212 delete [] newUpper;
213}
214// Apply bounds
215void
216OsiSolverBranch::applyBounds(OsiSolverInterface & solver,int way) const
217{
218 int base = way+1;
219 assert (way==-1||way==1);
220 int numberColumns = solver.getNumCols();
221 const double * columnLower = solver.getColLower();
222 int i;
223 for (i=start_[base];i<start_[base+1];i++) {
224 int iColumn = indices_[i];
225 if (iColumn<numberColumns) {
226 double value = CoinMax(bound_[i],columnLower[iColumn]);
227 solver.setColLower(iColumn,value);
228 } else {
229 int iRow = iColumn-numberColumns;
230 const double * rowLower = solver.getRowLower();
231 double value = CoinMax(bound_[i],rowLower[iRow]);
232 solver.setRowLower(iRow,value);
233 }
234 }
235 const double * columnUpper = solver.getColUpper();
236 for (i=start_[base+1];i<start_[base+2];i++) {
237 int iColumn = indices_[i];
238 if (iColumn<numberColumns) {
239 double value = CoinMin(bound_[i],columnUpper[iColumn]);
240 solver.setColUpper(iColumn,value);
241 } else {
242 int iRow = iColumn-numberColumns;
243 const double * rowUpper = solver.getRowUpper();
244 double value = CoinMin(bound_[i],rowUpper[iRow]);
245 solver.setRowUpper(iRow,value);
246 }
247 }
248}
249// Returns true if current solution satsifies one side of branch
250bool
251OsiSolverBranch::feasibleOneWay(const OsiSolverInterface & solver) const
252{
253 bool feasible = false;
254 int numberColumns = solver.getNumCols();
255 const double * columnLower = solver.getColLower();
256 const double * columnUpper = solver.getColUpper();
257 const double * columnSolution = solver.getColSolution();
258 double primalTolerance;
259 solver.getDblParam(OsiPrimalTolerance,primalTolerance);
260 for (int base = 0; base<4; base +=2) {
261 feasible=true;
262 int i;
263 for (i=start_[base];i<start_[base+1];i++) {
264 int iColumn = indices_[i];
265 if (iColumn<numberColumns) {
266 double value = CoinMax(bound_[i],columnLower[iColumn]);
267 if (columnSolution[iColumn]<value-primalTolerance) {
268 feasible=false;
269 break;
270 }
271 } else {
272 abort(); // do later (other stuff messed up anyway - e.g. CBC)
273 }
274 }
275 if (!feasible)
276 break;
277 for (i=start_[base+1];i<start_[base+2];i++) {
278 int iColumn = indices_[i];
279 if (iColumn<numberColumns) {
280 double value = CoinMin(bound_[i],columnUpper[iColumn]);
281 if (columnSolution[iColumn]>value+primalTolerance) {
282 feasible=false;
283 break;
284 }
285 } else {
286 abort(); // do later (other stuff messed up anyway - e.g. CBC)
287 }
288 }
289 if (feasible)
290 break; // OK this way
291 }
292 return feasible;
293}
294//#############################################################################
295// Constructors / Destructor / Assignment
296//#############################################################################
297
298//-------------------------------------------------------------------
299// Default Constructor
300//-------------------------------------------------------------------
301OsiSolverResult::OsiSolverResult () :
302 objectiveValue_(COIN_DBL_MAX),
303 primalSolution_(NULL),
304 dualSolution_(NULL)
305 {
306}
307
308//-------------------------------------------------------------------
309// Constructor from solver
310//-------------------------------------------------------------------
311OsiSolverResult::OsiSolverResult (const OsiSolverInterface & solver,const double * lowerBefore,
312 const double * upperBefore) :
313 objectiveValue_(COIN_DBL_MAX),
314 primalSolution_(NULL),
315 dualSolution_(NULL)
316{
317 if (solver.isProvenOptimal()&&!solver.isDualObjectiveLimitReached()) {
318 objectiveValue_ = solver.getObjValue()*solver.getObjSense();
319 CoinWarmStartBasis * basis = dynamic_cast<CoinWarmStartBasis *> (solver.getWarmStart());
320 assert (basis);
321 basis_ = * basis;
322 delete basis;
323 int numberRows = basis_.getNumArtificial();
324 int numberColumns = basis_.getNumStructural();
325 assert (numberColumns==solver.getNumCols());
326 assert (numberRows==solver.getNumRows());
327 primalSolution_ = CoinCopyOfArray(solver.getColSolution(),numberColumns);
328 dualSolution_ = CoinCopyOfArray(solver.getRowPrice(),numberRows);
329 fixed_.addBranch(-1,numberColumns,lowerBefore,solver.getColLower(),
330 upperBefore,solver.getColUpper());
331 }
332}
333
334//-------------------------------------------------------------------
335// Copy constructor
336//-------------------------------------------------------------------
337OsiSolverResult::OsiSolverResult (const OsiSolverResult & rhs)
338{
339 objectiveValue_ = rhs.objectiveValue_;
340 basis_ = rhs.basis_;
341 fixed_ = rhs.fixed_;
342 int numberRows = basis_.getNumArtificial();
343 int numberColumns = basis_.getNumStructural();
344 if (numberColumns) {
345 primalSolution_ = CoinCopyOfArray(rhs.primalSolution_,numberColumns);
346 dualSolution_ = CoinCopyOfArray(rhs.dualSolution_,numberRows);
347 } else {
348 primalSolution_=NULL;
349 dualSolution_=NULL;
350 }
351}
352
353//-------------------------------------------------------------------
354// Destructor
355//-------------------------------------------------------------------
356OsiSolverResult::~OsiSolverResult ()
357{
358 delete [] primalSolution_;
359 delete [] dualSolution_;
360}
361
362//----------------------------------------------------------------
363// Assignment operator
364//-------------------------------------------------------------------
365OsiSolverResult &
366OsiSolverResult::operator=(const OsiSolverResult& rhs)
367{
368 if (this != &rhs) {
369 delete [] primalSolution_;
370 delete [] dualSolution_;
371 objectiveValue_ = rhs.objectiveValue_;
372 basis_ = rhs.basis_;
373 fixed_ = rhs.fixed_;
374 int numberRows = basis_.getNumArtificial();
375 int numberColumns = basis_.getNumStructural();
376 if (numberColumns) {
377 primalSolution_ = CoinCopyOfArray(rhs.primalSolution_,numberColumns);
378 dualSolution_ = CoinCopyOfArray(rhs.dualSolution_,numberRows);
379 } else {
380 primalSolution_=NULL;
381 dualSolution_=NULL;
382 }
383 }
384 return *this;
385}
386// Create result
387void
388OsiSolverResult::createResult(const OsiSolverInterface & solver, const double * lowerBefore,
389 const double * upperBefore)
390{
391 delete [] primalSolution_;
392 delete [] dualSolution_;
393 if (solver.isProvenOptimal()&&!solver.isDualObjectiveLimitReached()) {
394 objectiveValue_ = solver.getObjValue()*solver.getObjSense();
395 CoinWarmStartBasis * basis = dynamic_cast<CoinWarmStartBasis *> (solver.getWarmStart());
396 assert (basis);
397 basis_ = * basis;
398 int numberRows = basis_.getNumArtificial();
399 int numberColumns = basis_.getNumStructural();
400 assert (numberColumns==solver.getNumCols());
401 assert (numberRows==solver.getNumRows());
402 primalSolution_ = CoinCopyOfArray(solver.getColSolution(),numberColumns);
403 dualSolution_ = CoinCopyOfArray(solver.getRowPrice(),numberRows);
404 fixed_.addBranch(-1,numberColumns,lowerBefore,solver.getColLower(),
405 upperBefore,solver.getColUpper());
406 } else {
407 // infeasible
408 objectiveValue_ = COIN_DBL_MAX;
409 basis_ = CoinWarmStartBasis();
410 primalSolution_=NULL;
411 dualSolution_=NULL;
412 }
413}
414// Restore result
415void
416OsiSolverResult::restoreResult(OsiSolverInterface & solver) const
417{
418 //solver.setObjValue(objectiveValue_)*solver.getObjSense();
419 solver.setWarmStart(&basis_);
420 solver.setColSolution(primalSolution_);
421 solver.setRowPrice(dualSolution_);
422 fixed_.applyBounds(solver,-1);
423}
424