1 /* $Id$
2 *
3 * Name: CouenneLPtightenBoundsCLP-light.cpp
4 * Authors: Pietro Belotti, Carnegie Mellon University
5 * Purpose: adaptation of OsiClpSolverInterface::tightenBounds() -- light version
6 *
7 * (C) Carnegie-Mellon University, 2009.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "CouennePrecisions.hpp"
12 #include "CouenneProblem.hpp"
13 #include "CouenneCutGenerator.hpp"
14 #include "CouenneExprVar.hpp"
15
16 namespace Couenne {
17
18 // Tighten bounds - lightweight. Returns -1 if infeasible, otherwise
19 // number of variables tightened.
20 template <class T>
tightenBoundsCLP_Light(int lightweight)21 int CouenneSolverInterface<T>::tightenBoundsCLP_Light (int lightweight) {
22
23 // Copied from OsiClpSolverInterface::tightenBounds
24
25 int
26 numberRows = T::getNumRows(),
27 numberColumns = T::getNumCols();
28
29 const double * columnUpper = T::getColUpper();
30 const double * columnLower = T::getColLower();
31 const double * rowUpper = T::getRowUpper();
32 const double * rowLower = T::getRowLower();
33
34 // Column copy of matrix
35 const double * element = T::getMatrixByCol()->getElements();
36 const int * row = T::getMatrixByCol()->getIndices();
37 const CoinBigIndex * columnStart = T::getMatrixByCol()->getVectorStarts();
38 const int * columnLength = T::getMatrixByCol()->getVectorLengths();
39 //const double *objective = T::getObjCoefficients() ;
40
41 //double direction = T::getObjSense();
42 double * down = new double [numberRows];
43
44 int * first = new int[numberRows];
45 CoinZeroN(first,numberRows);
46 CoinZeroN(down,numberRows);
47 double * sum = new double [numberRows];
48 CoinZeroN(sum,numberRows);
49 int numberTightened=0;
50
51 for (int iColumn=0;iColumn<numberColumns;iColumn++) {
52 CoinBigIndex start = columnStart[iColumn];
53 CoinBigIndex end = start + columnLength[iColumn];
54 double lower = columnLower[iColumn];
55 double upper = columnUpper[iColumn];
56 if (lower==upper) {
57 for (CoinBigIndex j=start;j<end;j++) {
58 int iRow = row[j];
59 double value = element[j];
60 down[iRow] += value*lower;
61 sum[iRow] += fabs(value*lower);
62 }
63 } else {
64 for (CoinBigIndex j=start;j<end;j++) {
65 int iRow = row[j];
66 int n=first[iRow];
67 if (n==0&&element[j])
68 first[iRow]=-iColumn-1;
69 else if (n<0)
70 first[iRow]=2;
71 }
72 }
73 }
74
75 double tolerance = 1.0e-6;
76
77 std::vector <exprVar *> &vars = cutgen_ -> Problem () -> Variables ();
78
79 for (int iRow=0;iRow<numberRows;iRow++) {
80
81 int iColumn = first[iRow];
82
83 if (iColumn<0) {
84
85 iColumn = -iColumn-1;
86
87 double lowerRow = rowLower[iRow];
88 if (lowerRow>-1.0e20)
89 lowerRow -= down[iRow];
90 double upperRow = rowUpper[iRow];
91 if (upperRow<1.0e20)
92 upperRow -= down[iRow];
93 double lower = columnLower[iColumn];
94 double upper = columnUpper[iColumn];
95 double value=0.0;
96 for (CoinBigIndex j = columnStart[iColumn];
97 j<columnStart[iColumn]+columnLength[iColumn];j++) {
98 if (iRow==row[j]) {
99 value=element[j];
100 break;
101 }
102 }
103
104 assert (value);
105
106 // convert rowLower and Upper to implied bounds on column
107
108 double
109 newLower = -COIN_DBL_MAX,
110 newUpper = COIN_DBL_MAX;
111
112 if (value > 0.0) {
113 if (lowerRow > -1.0e20) newLower = lowerRow / value;
114 if (upperRow < 1.0e20) newUpper = upperRow / value;
115 } else {
116 if (upperRow < 1.0e20) newLower = upperRow / value;
117 if (lowerRow > -1.0e20) newUpper = lowerRow / value;
118 }
119
120 double tolerance2 = 1.0e-6 + 1.0e-8 * sum [iRow];
121
122 if (vars [iColumn] -> isInteger ()) {
123
124 newLower = (newLower-floor(newLower)<tolerance2) ?
125 floor (newLower) :
126 ceil (newLower);
127
128 newUpper = (ceil(newUpper)-newUpper<tolerance2) ?
129 ceil (newUpper) :
130 floor (newUpper);
131 }
132
133 if (newLower>lower+10.0*tolerance2||
134 newUpper<upper-10.0*tolerance2) {
135 numberTightened++;
136 newLower = CoinMax(lower,newLower);
137 newUpper = CoinMin(upper,newUpper);
138 if (newLower>newUpper+tolerance) {
139 //printf("XXYY inf on bound\n");
140 numberTightened=-1;
141 break;
142 }
143 T::setColLower(iColumn,newLower);
144 T::setColUpper(iColumn,CoinMax(newLower,newUpper));
145 }
146 }
147 }
148
149 delete [] first;
150 delete [] down;
151 delete [] sum;
152 return numberTightened;
153 }
154
155 }
156