1 | /* $Id: CouenneFPFindSolution.cpp 961 2013-05-24 17:05:10Z pbelotti $ |
---|
2 | * |
---|
3 | * Name: CouenneFPFindSolution.cpp |
---|
4 | * Authors: Pietro Belotti |
---|
5 | * Timo Berthold, ZIB Berlin |
---|
6 | * Purpose: Find solution by looping through MILP solvers/heuristics |
---|
7 | * |
---|
8 | * This file is licensed under the Eclipse Public License (EPL) |
---|
9 | */ |
---|
10 | |
---|
11 | #include "CoinTime.hpp" |
---|
12 | |
---|
13 | #include "CouenneFeasPump.hpp" |
---|
14 | #include "CouenneFPpool.hpp" |
---|
15 | #include "CouenneProblem.hpp" |
---|
16 | #include "CouenneExprVar.hpp" |
---|
17 | |
---|
18 | #include "cons_rowcuts.h" |
---|
19 | |
---|
20 | #ifdef COIN_HAS_SCIP |
---|
21 | #include "scip/scip.h" |
---|
22 | #endif |
---|
23 | |
---|
24 | using namespace Couenne; |
---|
25 | |
---|
26 | /// find a feasible or optimal solution of MILP |
---|
27 | double CouenneFeasPump::findSolution (double* &iSol, int niter, int* nsuciter) { |
---|
28 | |
---|
29 | /// As found on the notes, these methods can be used, from the most |
---|
30 | /// expensive and accurate (exact) method to a cheap, inexact one: |
---|
31 | /// |
---|
32 | /// 1. Solve a MILP relaxation with Manhattan distance as objective |
---|
33 | /// 2. Partially solve the MILP with emphasis on good solutions |
---|
34 | /// 3. Apply RENS to 1 |
---|
35 | /// 4. Use Objective FP 2.0 for MILPs |
---|
36 | /// 5. round-and-propagate |
---|
37 | /// 6. choose from pool, see 4 |
---|
38 | /// 7. random perturbation |
---|
39 | |
---|
40 | // What order should we use? I suggest we use priorities, assigned |
---|
41 | // at the beginning but changeable in the event of multiple failures |
---|
42 | // (or successes) of a given method. |
---|
43 | // |
---|
44 | // Rule of thumb: |
---|
45 | // |
---|
46 | // 1) Assign all methods i a number p[i] (for instance those in the |
---|
47 | // list above) |
---|
48 | // |
---|
49 | // 2) Call each in the order defined by p[i], return a solution if |
---|
50 | // found, otherwise proceed to next method |
---|
51 | // |
---|
52 | // 3) If K consecutive successes at finding new solution (not |
---|
53 | // necessarily new best feasible), --p[i] |
---|
54 | // |
---|
55 | // 4) if H consecutive failures, ++p[i] |
---|
56 | |
---|
57 | double obj; |
---|
58 | |
---|
59 | /// solve MILP |
---|
60 | |
---|
61 | if (0) { |
---|
62 | static int nSolves = 0; |
---|
63 | char name [40]; |
---|
64 | sprintf (name, "fp_milp_%d", nSolves++); |
---|
65 | milp_ -> writeLp (name); |
---|
66 | } |
---|
67 | |
---|
68 | #ifdef COIN_HAS_SCIP |
---|
69 | |
---|
70 | if (useSCIP_ && problem_ -> nIntVars () > 0) { // if LP, use Clp below |
---|
71 | |
---|
72 | SCIP_RETCODE retcode = ScipSolve (iSol, niter, nsuciter, obj); |
---|
73 | |
---|
74 | if (retcode != SCIP_OKAY) { |
---|
75 | |
---|
76 | printf ("Couenne Feasibility Pump: SCIP did not return a feasible solution\n"); |
---|
77 | return COIN_DBL_MAX; |
---|
78 | } |
---|
79 | } else |
---|
80 | |
---|
81 | #endif |
---|
82 | { |
---|
83 | |
---|
84 | milp_ -> messageHandler () -> setLogLevel (0); |
---|
85 | |
---|
86 | if (problem_ -> nIntVars () > 0) milp_ -> branchAndBound (); |
---|
87 | else milp_ -> initialSolve (); |
---|
88 | |
---|
89 | if (!iSol) |
---|
90 | iSol = new CouNumber [problem_ -> nVars ()]; |
---|
91 | |
---|
92 | if (milp_ -> getColSolution ()) |
---|
93 | CoinCopyN (milp_ -> getColSolution (), problem_ -> nVars (), iSol); |
---|
94 | else { |
---|
95 | |
---|
96 | if (iSol) |
---|
97 | delete [] iSol; |
---|
98 | iSol = NULL; |
---|
99 | } |
---|
100 | |
---|
101 | obj = milp_ -> getObjValue (); |
---|
102 | } |
---|
103 | |
---|
104 | return obj; |
---|
105 | } |
---|
106 | |
---|
107 | /// initialize MILP solvers if needed |
---|
108 | void CouenneFeasPump::init_MILP () {} |
---|