1 /* $Id$
2 *
3 * Name: isOptimumCut.cpp
4 * Author: Pietro Belotti
5 * Purpose: check if known optimal solution (read from .txt) is
6 * erroneously cut by the row/col cuts we've added
7 *
8 * (C) Carnegie-Mellon University, 2009.
9 * This file is licensed under the Eclipse Public License (EPL)
10 */
11
12 #include "CglCutGenerator.hpp"
13 #include "CoinHelperFunctions.hpp"
14
15 #include "CouenneCutGenerator.hpp"
16 #include "CouenneProblem.hpp"
17 #include "CouenneExprVar.hpp"
18
19 namespace Couenne {
20
isOptimumCut(const CouNumber * opt,OsiCuts & cs,CouenneProblem * p)21 bool isOptimumCut (const CouNumber *opt, OsiCuts &cs, CouenneProblem *p) {
22
23 bool retval = false;
24
25 // Column cuts ////////////////////////////////////////////////////////////////////////
26
27 if (cs.sizeColCuts ()) {
28
29 //printf ("Checking col cuts:\n");
30
31 for (int i = cs.sizeColCuts (); i--;) {
32
33 // lower bounds
34
35 const CoinPackedVector &lbs = cs.colCutPtr (i) -> lbs ();
36 const int *lindices = lbs.getIndices ();
37 const double *lvalues = lbs.getElements ();
38
39 for (int j = lbs.getNumElements (); j--;) {
40 register double lb = *lvalues++;
41 register int ind = *lindices++;
42
43 if (lb > opt [ind] + COUENNE_EPS) {
44 printf ("################################## new lb [%d] = %g cuts opt %g by %g\n",
45 ind, lb, opt [ind], lb - opt [ind]);
46 retval = true;
47 }
48 }
49
50 // upper bounds
51
52 const CoinPackedVector &ubs = cs.colCutPtr (i) -> ubs ();
53 const int *uindices = ubs.getIndices ();
54 const double *uvalues = ubs.getElements ();
55
56 for (int j = ubs.getNumElements (); j--;) {
57 register double ub = *uvalues++;
58 register int ind = *uindices++;
59
60 if (ub < opt [ind] - COUENNE_EPS) {
61 printf ("################################## new ub [%d] = %g cuts opt %g by %g\n",
62 ind, ub, opt [ind], opt [ind] - ub);
63 retval = true;
64 }
65 }
66 }
67 }
68
69 // Row cuts ///////////////////////////////////////////////////////////////////////////
70
71 if (cs.sizeRowCuts ()) {
72
73 //printf ("Checking row cuts:\n");
74
75 for (int jj=0; jj < cs.sizeRowCuts (); jj++) {
76
77 OsiRowCut *cut = cs.rowCutPtr (jj);
78 CoinPackedVector row = cut -> row ();
79
80 int n = cut -> row (). getNumElements();
81 const double *el = row. getElements ();
82 const int *ind = row. getIndices ();
83
84 double lb = cut -> lb ();
85 double ub = cut -> ub ();
86
87 double lhs = 0;
88
89 while (n--)
90 lhs += el [n] * opt [ind [n]];
91
92
93 if ((lhs < lb - COUENNE_EPS) ||
94 (lhs > ub + COUENNE_EPS)) {
95
96 printf ("################################## new cut [%d] [%g,%g] cuts opt %g by %g:",
97 jj, lb, ub, lhs, CoinMax (lb - lhs, lhs - ub));
98
99 cut -> print ();
100 retval = true;
101 }
102 }
103 }
104
105 if (retval) {
106
107 printf ("== genrowcuts on LP =============");
108
109 for (int i = 0; i < p -> nVars (); i++) {
110 if (!(i % 3))
111 printf ("\n");
112 if (p -> Var (i) -> Multiplicity () > 0)
113 printf ("%3d %+10.3g [%+10.3g,%+10.3g] ", i,
114 p -> X (i),
115 p -> Lb (i),
116 p -> Ub (i));
117 }
118
119 printf ("\n=============================\n");
120 }
121
122 return retval;
123 }
124
125 }
126