1 /* $Id$
2 *
3 * Name: obbt_supplement.cpp
4 * Author: Pietro Belotti
5 * Purpose: Post-OBBT computations that use dual information to infer
6 *
7 * This file is licensed under the Eclipse Public License (EPL)
8 */
9
10 #include "OsiSolverInterface.hpp"
11
12 // Use dual information lambda to obtain, from solution to this
13 // problem, a dual bound to OBBT subproblem (min|max) for every
14 // other variable.
15
obbt_supplement(const OsiSolverInterface * csi,int index,int sense)16 int obbt_supplement (const OsiSolverInterface *csi, /// interface to use as a solver
17 int index, /// variable being looked at
18 int sense) { /// 1: minimize, -1: maximize
19
20 return 0;
21
22 if (!(csi -> isProvenOptimal ()))
23 return 0;
24
25 int
26 n = csi -> getNumCols (),
27 m = csi -> getNumRows ();
28
29 // get dual
30
31 const double *lambda = csi -> getRowPrice ();
32
33 double alpha_i = (sense==1 ? 1. : -1.);
34
35 double *beta = new double [m];
36
37 // The problem just solved was either (depending on sense):
38 //
39 // LB) min { x_i: Ax>=b, l<=x<=u}
40 // UB) min { -x_i: Ax>=b, l<=x<=u}
41 //
42 // lambda contains the dual variables at the optimal solution,
43 // i.e., the Lagrangian multipliers of the problems
44 //
45 // L_lb (lambda) = min { x_i + lambda^T (b-Ax): l<=x<=u}
46 // U_lb (lambda) = min {-x_i + lambda^T (b-Ax): l<=x<=u}
47 //
48 // Suppose M={1..m} and N={1..n} index the set of rows and columns,
49 // respectively. Rewrite both problems above by setting alpha_i as 1
50 // for the LB problem and -1 for the UB problem.
51 //
52 // L (i, lambda) = min {alpha_i x_i + sum {h in M} lambda_h (b_h - sum {k in N} a_hk x_k): l <= x <= u}
53 // = lambda^T b + min {alpha_i x_i - sum {h in M} sum {k in N} lambda_h a_hk x_k: l <= x <= u}
54 // = lambda^T b + min {alpha_i x_i - sum {k in N} (sum {h in M} lambda_h a_hk) x_k: l <= x <= u}
55 // = lambda^T b + min {alpha_i x_i - sum {k in N} beta_k x_k: l <= x <= u}
56 // = lambda^T b + min { sum {k in N} gamma_i_k x_k: l <= x <= u}
57 //
58 // = lambda^T b + sum {k in N: gamma_i_k > 0} gamma_i_k l_k +
59 // sum {k in N: gamma_i_k < 0} gamma_i_k u_k,
60 //
61 // where
62 //
63 // beta_k = sum {h in M} lambda_h a_hk and
64 //
65 // and
66 //
67 // gamma_i_k = - beta_i + alpha_i if i==k
68 // - beta_k otherwise.
69 //
70 // Then any dual solution to the i-th LB or UB problems above can be
71 // used to get a DUAL solution to all other j-th LB/UB problems, for
72 // j!=i. Just compute L (j,lambda) for all j, for alpha_i in {-1,1},
73 // and compare with previous bound.
74
75 for (int j=0; j<n; j++) {
76
77 }
78
79 delete [] beta;
80 }
81