source: trunk/Cbc/src/CbcNWay.cpp @ 1899

Last change on this file since 1899 was 1899, checked in by stefan, 6 years ago

fixup svn properties

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.2 KB
Line 
1// $Id: CbcNWay.cpp 1899 2013-04-09 18:12:08Z stefan $
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6// Edwin 11/9/2009-- carved out of CbcBranchActual
7
8#if defined(_MSC_VER)
9// Turn off compiler warning about long names
10#  pragma warning(disable:4786)
11#endif
12#include <cassert>
13#include <cstdlib>
14#include <cmath>
15#include <cfloat>
16//#define CBC_DEBUG
17
18#include "CoinTypes.hpp"
19#include "OsiSolverInterface.hpp"
20#include "OsiSolverBranch.hpp"
21#include "CbcModel.hpp"
22#include "CbcMessage.hpp"
23#include "CbcNWay.hpp"
24#include "CbcBranchActual.hpp"
25#include "CoinSort.hpp"
26#include "CoinError.hpp"
27
28//##############################################################################
29
30// Default Constructor
31CbcNWay::CbcNWay ()
32        : CbcObject(),
33        numberMembers_(0),
34        members_(NULL),
35        consequence_(NULL)
36{
37}
38
39// Useful constructor (which are integer indices)
40CbcNWay::CbcNWay (CbcModel * model, int numberMembers,
41                  const int * which, int identifier)
42        : CbcObject(model)
43{
44    id_ = identifier;
45    numberMembers_ = numberMembers;
46    if (numberMembers_) {
47        members_ = new int[numberMembers_];
48        memcpy(members_, which, numberMembers_*sizeof(int));
49    } else {
50        members_ = NULL;
51    }
52    consequence_ = NULL;
53}
54
55// Copy constructor
56CbcNWay::CbcNWay ( const CbcNWay & rhs)
57        : CbcObject(rhs)
58{
59    numberMembers_ = rhs.numberMembers_;
60    consequence_ = NULL;
61    if (numberMembers_) {
62        members_ = new int[numberMembers_];
63        memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
64        if (rhs.consequence_) {
65            consequence_ = new CbcConsequence * [numberMembers_];
66            for (int i = 0; i < numberMembers_; i++) {
67                if (rhs.consequence_[i])
68                    consequence_[i] = rhs.consequence_[i]->clone();
69                else
70                    consequence_[i] = NULL;
71            }
72        }
73    } else {
74        members_ = NULL;
75    }
76}
77
78// Clone
79CbcObject *
80CbcNWay::clone() const
81{
82    return new CbcNWay(*this);
83}
84
85// Assignment operator
86CbcNWay &
87CbcNWay::operator=( const CbcNWay & rhs)
88{
89    if (this != &rhs) {
90        CbcObject::operator=(rhs);
91        delete [] members_;
92        numberMembers_ = rhs.numberMembers_;
93        if (consequence_) {
94            for (int i = 0; i < numberMembers_; i++)
95                delete consequence_[i];
96            delete [] consequence_;
97            consequence_ = NULL;
98        }
99        if (numberMembers_) {
100            members_ = new int[numberMembers_];
101            memcpy(members_, rhs.members_, numberMembers_*sizeof(int));
102        } else {
103            members_ = NULL;
104        }
105        if (rhs.consequence_) {
106            consequence_ = new CbcConsequence * [numberMembers_];
107            for (int i = 0; i < numberMembers_; i++) {
108                if (rhs.consequence_[i])
109                    consequence_[i] = rhs.consequence_[i]->clone();
110                else
111                    consequence_[i] = NULL;
112            }
113        }
114    }
115    return *this;
116}
117
118// Destructor
119CbcNWay::~CbcNWay ()
120{
121    delete [] members_;
122    if (consequence_) {
123        for (int i = 0; i < numberMembers_; i++)
124            delete consequence_[i];
125        delete [] consequence_;
126    }
127}
128// Set up a consequence for a single member
129void
130CbcNWay::setConsequence(int iColumn, const CbcConsequence & consequence)
131{
132    if (!consequence_) {
133        consequence_ = new CbcConsequence * [numberMembers_];
134        for (int i = 0; i < numberMembers_; i++)
135            consequence_[i] = NULL;
136    }
137    for (int i = 0; i < numberMembers_; i++) {
138        if (members_[i] == iColumn) {
139            consequence_[i] = consequence.clone();
140            break;
141        }
142    }
143}
144
145// Applies a consequence for a single member
146void
147CbcNWay::applyConsequence(int iSequence, int state) const
148{
149    assert (state == -9999 || state == 9999);
150    if (consequence_) {
151        CbcConsequence * consequence = consequence_[iSequence];
152        if (consequence)
153            consequence->applyToSolver(model_->solver(), state);
154    }
155}
156double
157CbcNWay::infeasibility(const OsiBranchingInformation * /*info*/,
158                       int &preferredWay) const
159{
160    int numberUnsatis = 0;
161    int j;
162    OsiSolverInterface * solver = model_->solver();
163    const double * solution = model_->testSolution();
164    const double * lower = solver->getColLower();
165    const double * upper = solver->getColUpper();
166    double largestValue = 0.0;
167
168    double integerTolerance =
169        model_->getDblParam(CbcModel::CbcIntegerTolerance);
170
171    for (j = 0; j < numberMembers_; j++) {
172        int iColumn = members_[j];
173        double value = solution[iColumn];
174        value = CoinMax(value, lower[iColumn]);
175        value = CoinMin(value, upper[iColumn]);
176        double distance = CoinMin(value - lower[iColumn], upper[iColumn] - value);
177        if (distance > integerTolerance) {
178            numberUnsatis++;
179            largestValue = CoinMax(distance, largestValue);
180        }
181    }
182    preferredWay = 1;
183    if (numberUnsatis) {
184        return largestValue;
185    } else {
186        return 0.0; // satisfied
187    }
188}
189
190// This looks at solution and sets bounds to contain solution
191void
192CbcNWay::feasibleRegion()
193{
194    int j;
195    OsiSolverInterface * solver = model_->solver();
196    const double * solution = model_->testSolution();
197    const double * lower = solver->getColLower();
198    const double * upper = solver->getColUpper();
199    double integerTolerance =
200        model_->getDblParam(CbcModel::CbcIntegerTolerance);
201    for (j = 0; j < numberMembers_; j++) {
202        int iColumn = members_[j];
203        double value = solution[iColumn];
204        value = CoinMax(value, lower[iColumn]);
205        value = CoinMin(value, upper[iColumn]);
206        if (value >= upper[iColumn] - integerTolerance) {
207            solver->setColLower(iColumn, upper[iColumn]);
208        } else {
209            assert (value <= lower[iColumn] + integerTolerance);
210            solver->setColUpper(iColumn, lower[iColumn]);
211        }
212    }
213}
214// Redoes data when sequence numbers change
215void
216CbcNWay::redoSequenceEtc(CbcModel * model, int numberColumns, const int * originalColumns)
217{
218    model_ = model;
219    int n2 = 0;
220    for (int j = 0; j < numberMembers_; j++) {
221        int iColumn = members_[j];
222        int i;
223        for (i = 0; i < numberColumns; i++) {
224            if (originalColumns[i] == iColumn)
225                break;
226        }
227        if (i < numberColumns) {
228            members_[n2] = i;
229            consequence_[n2++] = consequence_[j];
230        } else {
231            delete consequence_[j];
232        }
233    }
234    if (n2 < numberMembers_) {
235        printf("** NWay number of members reduced from %d to %d!\n", numberMembers_, n2);
236        numberMembers_ = n2;
237    }
238}
239CbcBranchingObject *
240CbcNWay::createCbcBranch(OsiSolverInterface * solver, const OsiBranchingInformation * /*info*/, int /*way*/)
241{
242    int numberFree = 0;
243    int j;
244
245    //OsiSolverInterface * solver = model_->solver();
246    const double * solution = model_->testSolution();
247    const double * lower = solver->getColLower();
248    const double * upper = solver->getColUpper();
249    int * list = new int[numberMembers_];
250    double * sort = new double[numberMembers_];
251
252    for (j = 0; j < numberMembers_; j++) {
253        int iColumn = members_[j];
254        double value = solution[iColumn];
255        value = CoinMax(value, lower[iColumn]);
256        value = CoinMin(value, upper[iColumn]);
257        if (upper[iColumn] > lower[iColumn]) {
258            double distance = upper[iColumn] - value;
259            list[numberFree] = j;
260            sort[numberFree++] = distance;
261        }
262    }
263    assert (numberFree);
264    // sort
265    CoinSort_2(sort, sort + numberFree, list);
266    // create object
267    CbcBranchingObject * branch;
268    branch = new CbcNWayBranchingObject(model_, this, numberFree, list);
269    branch->setOriginalObject(this);
270    delete [] list;
271    delete [] sort;
272    return branch;
273}
274
275// Default Constructor
276CbcNWayBranchingObject::CbcNWayBranchingObject()
277        : CbcBranchingObject()
278{
279    order_ = NULL;
280    object_ = NULL;
281    numberInSet_ = 0;
282    way_ = 0;
283}
284
285// Useful constructor
286CbcNWayBranchingObject::CbcNWayBranchingObject (CbcModel * model,
287        const CbcNWay * nway,
288        int number, const int * order)
289        : CbcBranchingObject(model, nway->id(), -1, 0.5)
290{
291    numberBranches_ = number;
292    order_ = new int [number];
293    object_ = nway;
294    numberInSet_ = number;
295    memcpy(order_, order, number*sizeof(int));
296}
297
298// Copy constructor
299CbcNWayBranchingObject::CbcNWayBranchingObject ( const CbcNWayBranchingObject & rhs) : CbcBranchingObject(rhs)
300{
301    numberInSet_ = rhs.numberInSet_;
302    object_ = rhs.object_;
303    if (numberInSet_) {
304        order_ = new int [numberInSet_];
305        memcpy(order_, rhs.order_, numberInSet_*sizeof(int));
306    } else {
307        order_ = NULL;
308    }
309}
310
311// Assignment operator
312CbcNWayBranchingObject &
313CbcNWayBranchingObject::operator=( const CbcNWayBranchingObject & rhs)
314{
315    if (this != &rhs) {
316        CbcBranchingObject::operator=(rhs);
317        object_ = rhs.object_;
318        delete [] order_;
319        numberInSet_ = rhs.numberInSet_;
320        if (numberInSet_) {
321            order_ = new int [numberInSet_];
322            memcpy(order_, rhs.order_, numberInSet_*sizeof(int));
323        } else {
324            order_ = NULL;
325        }
326    }
327    return *this;
328}
329CbcBranchingObject *
330CbcNWayBranchingObject::clone() const
331{
332    return (new CbcNWayBranchingObject(*this));
333}
334
335
336// Destructor
337CbcNWayBranchingObject::~CbcNWayBranchingObject ()
338{
339    delete [] order_;
340}
341double
342CbcNWayBranchingObject::branch()
343{
344    int which = branchIndex_;
345    branchIndex_++;
346    assert (numberBranchesLeft() >= 0);
347    if (which == 0) {
348        // first branch so way_ may mean something
349        assert (way_ == -1 || way_ == 1);
350        if (way_ == -1)
351            which++;
352    } else if (which == 1) {
353        // second branch so way_ may mean something
354        assert (way_ == -1 || way_ == 1);
355        if (way_ == -1)
356            which--;
357        // switch way off
358        way_ = 0;
359    }
360    const double * lower = model_->solver()->getColLower();
361    const double * upper = model_->solver()->getColUpper();
362    const int * members = object_->members();
363    for (int j = 0; j < numberInSet_; j++) {
364        int iSequence = order_[j];
365        int iColumn = members[iSequence];
366        if (j != which) {
367            model_->solver()->setColUpper(iColumn, lower[iColumn]);
368            //model_->solver()->setColLower(iColumn,lower[iColumn]);
369            assert (lower[iColumn] > -1.0e20);
370            // apply any consequences
371            object_->applyConsequence(iSequence, -9999);
372        } else {
373            model_->solver()->setColLower(iColumn, upper[iColumn]);
374            //model_->solver()->setColUpper(iColumn,upper[iColumn]);
375#ifdef FULL_PRINT
376            printf("Up Fix %d to %g\n", iColumn, upper[iColumn]);
377#endif
378            assert (upper[iColumn] < 1.0e20);
379            // apply any consequences
380            object_->applyConsequence(iSequence, 9999);
381        }
382    }
383    return 0.0;
384}
385void
386CbcNWayBranchingObject::print()
387{
388    printf("NWay - Up Fix ");
389    const int * members = object_->members();
390    for (int j = 0; j < way_; j++) {
391        int iColumn = members[order_[j]];
392        printf("%d ", iColumn);
393    }
394    printf("\n");
395}
396
397/** Compare the original object of \c this with the original object of \c
398    brObj. Assumes that there is an ordering of the original objects.
399    This method should be invoked only if \c this and brObj are of the same
400    type.
401    Return negative/0/positive depending on whether \c this is
402    smaller/same/larger than the argument.
403*/
404int
405CbcNWayBranchingObject::compareOriginalObject
406(const CbcBranchingObject* /*brObj*/) const
407{
408    throw("must implement");
409}
410
411/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
412    same type and must have the same original object, but they may have
413    different feasible regions.
414    Return the appropriate CbcRangeCompare value (first argument being the
415    sub/superset if that's the case). In case of overlap (and if \c
416    replaceIfOverlap is true) replace the current branching object with one
417    whose feasible region is the overlap.
418*/
419CbcRangeCompare
420CbcNWayBranchingObject::compareBranchingObject
421(const CbcBranchingObject* /*brObj*/, const bool /*replaceIfOverlap*/)
422{
423    throw("must implement");
424}
425
Note: See TracBrowser for help on using the repository browser.