source: trunk/include/ClpNonLinearCost.hpp @ 308

Last change on this file since 308 was 308, checked in by forrest, 16 years ago

Dynamic Gub

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 8.5 KB
Line 
1// Copyright (C) 2002, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#ifndef ClpNonLinearCost_H
4#define ClpNonLinearCost_H
5
6
7#include "CoinPragma.hpp"
8
9class ClpSimplex;
10class CoinIndexedVector;
11
12/** Trivial class to deal with non linear costs
13
14    I don't make any explicit assumptions about convexity but I am
15    sure I do make implicit ones.
16
17    One interesting idea for normal LP's will be to allow non-basic
18    variables to come into basis as infeasible i.e. if variable at
19    lower bound has very large positive reduced cost (when problem
20    is infeasible) could it reduce overall problem infeasibility more
21    by bringing it into basis below its lower bound.
22
23    Another feature would be to automatically discover when problems
24    are convex piecewise linear and re-formulate to use non-linear.
25    I did some work on this many years ago on "grade" problems, but
26    while it improved primal interior point algorithms were much better
27    for that particular problem.
28*/
29
30class ClpNonLinearCost  {
31 
32public:
33 
34public:
35
36  /**@name Constructors, destructor */
37  //@{
38  /// Default constructor.
39  ClpNonLinearCost();
40  /** Constructor from simplex.
41      This will just set up wasteful arrays for linear, but
42      later may do dual analysis and even finding duplicate columns .
43  */
44  ClpNonLinearCost(ClpSimplex * model);
45  /** Constructor from simplex and list of non-linearities (columns only)
46      First lower of each column has to match real lower
47      Last lower has to be <= upper (if == then cost ignored)
48      This could obviously be changed to make more user friendly
49  */
50  ClpNonLinearCost(ClpSimplex * model,const int * starts,
51                   const double * lower, const double * cost);
52  /// Destructor
53  ~ClpNonLinearCost();
54  // Copy
55  ClpNonLinearCost(const ClpNonLinearCost&);
56  // Assignment
57  ClpNonLinearCost& operator=(const ClpNonLinearCost&);
58  //@}
59     
60
61  /**@name Actual work in primal */
62  //@{
63  /** Changes infeasible costs and computes number and cost of infeas
64      Puts all non-basic (non free) variables to bounds
65      and all free variables to zero if oldTolerance is non-zero
66      - but does not move those <= oldTolerance away*/
67  void checkInfeasibilities(double oldTolerance=0.0);
68  /** Changes infeasible costs for each variable
69      The indices are row indices and need converting to sequences
70  */
71  void checkInfeasibilities(int numberInArray, const int * index);
72  /** Puts back correct infeasible costs for each variable
73      The input indices are row indices and need converting to sequences
74      for costs.
75      On input array is empty (but indices exist).  On exit just
76      changed costs will be stored as normal CoinIndexedVector
77  */
78  void checkChanged(int numberInArray, CoinIndexedVector * update);
79  /** Goes through one bound for each variable.
80      If multiplier*work[iRow]>0 goes down, otherwise up.
81      The indices are row indices and need converting to sequences
82      Temporary offsets may be set
83      Rhs entries are increased
84  */
85  void goThru(int numberInArray, double multiplier,
86              const int * index, const double * work,
87              double * rhs);
88  /** Takes off last iteration (i.e. offsets closer to 0)
89  */
90  void goBack(int numberInArray, const int * index, 
91              double * rhs);
92  /** Puts back correct infeasible costs for each variable
93      The input indices are row indices and need converting to sequences
94      for costs.
95      At the end of this all temporary offsets are zero
96  */
97  void goBackAll(const CoinIndexedVector * update);
98  /// Temporary zeroing of feasible costs
99  void zapCosts();
100  /** Sets bounds and cost for one variable
101      Returns change in cost
102   May need to be inline for speed */
103  double setOne(int sequence, double solutionValue);
104  /** Sets bounds and infeasible cost and true cost for one variable
105      This is for gub and column generation etc */
106  void setOne(int sequence, double solutionValue, double lowerValue, double upperValue,
107              double costValue=0.0);
108  /** Sets bounds and cost for outgoing variable
109      may change value
110      Returns direction */
111  int setOneOutgoing(int sequence, double &solutionValue);
112  /// Returns nearest bound
113  double nearest(int sequence, double solutionValue);
114  /** Returns change in cost - one down if alpha >0.0, up if <0.0
115      Value is current - new
116   */
117  inline double changeInCost(int sequence, double alpha) const
118  {
119    int iRange = whichRange_[sequence]+offset_[sequence];
120    if (alpha>0.0)
121      return cost_[iRange]-cost_[iRange-1];
122    else
123      return cost_[iRange]-cost_[iRange+1];
124  }
125  inline double changeUpInCost(int sequence) const
126  {
127    int iRange = whichRange_[sequence]+offset_[sequence];
128    if (iRange+1!=start_[sequence+1]&&!infeasible(iRange+1))
129      return cost_[iRange]-cost_[iRange+1];
130    else
131      return -1.0e100;
132  }
133  inline double changeDownInCost(int sequence) const
134  {
135    int iRange = whichRange_[sequence]+offset_[sequence];
136    if (iRange!=start_[sequence]&&!infeasible(iRange-1))
137      return cost_[iRange]-cost_[iRange-1];
138    else
139      return 1.0e100;
140  }
141  /// This also updates next bound
142  inline double changeInCost(int sequence, double alpha, double &rhs)
143  {
144    int iRange = whichRange_[sequence]+offset_[sequence];
145    if (alpha>0.0) {
146      assert(iRange-1>=start_[sequence]);
147      offset_[sequence]--;
148      rhs += lower_[iRange]-lower_[iRange-1];
149      return alpha*(cost_[iRange]-cost_[iRange-1]);
150    } else {
151      assert(iRange+1<start_[sequence+1]-1);
152      offset_[sequence]++;
153      rhs += lower_[iRange+2]-lower_[iRange+1];
154      return alpha*(cost_[iRange]-cost_[iRange+1]);
155    }
156  }
157  /// Returns current lower bound
158  inline double lower(int sequence) const
159  { return lower_[whichRange_[sequence]+offset_[sequence]];};
160  /// Returns current upper bound
161  inline double upper(int sequence) const
162  { return lower_[whichRange_[sequence]+offset_[sequence]+1];};
163  /// Returns current cost
164  inline double cost(int sequence) const
165  { return cost_[whichRange_[sequence]+offset_[sequence]];};
166  //@}
167
168
169  /**@name Gets and sets */
170  //@{
171  /// Number of infeasibilities
172  inline int numberInfeasibilities() const
173  {return numberInfeasibilities_;};
174  /// Change in cost
175  inline double changeInCost() const
176  {return changeCost_;};
177  /// Feasible cost
178  inline double feasibleCost() const
179  {return feasibleCost_;};
180  /// Feasible cost with offset and direction (i.e. for reporting)
181  double feasibleReportCost() const;
182  /// Sum of infeasibilities
183  inline double sumInfeasibilities() const
184  {return sumInfeasibilities_;};
185  /// Largest infeasibility
186  inline double largestInfeasibility() const
187  {return largestInfeasibility_;};
188  /// Average theta
189  inline double averageTheta() const
190  {return averageTheta_;};
191  inline void setAverageTheta(double value)
192  {averageTheta_=value;};
193  inline void setChangeInCost(double value) 
194  {changeCost_ = value;};
195  /// See if may want to look both ways
196  inline bool lookBothWays() const
197  { return bothWays_;};
198  //@}
199  ///@name Private functions to deal with infeasible regions
200  inline bool infeasible(int i) const {
201    return ((infeasible_[i>>5]>>(i&31))&1)!=0;
202  }
203  inline void setInfeasible(int i,bool trueFalse) {
204    unsigned int & value = infeasible_[i>>5];
205    int bit = i&31;
206    if (trueFalse)
207      value |= (1<<bit);
208    else
209      value &= ~(1<<bit);
210  }
211  //@}
212   
213private:
214  /**@name Data members */
215  //@{
216  /// Change in cost because of infeasibilities
217  double changeCost_;
218  /// Feasible cost
219  double feasibleCost_;
220  /// Largest infeasibility
221  double largestInfeasibility_;
222  /// Sum of infeasibilities
223  double sumInfeasibilities_;
224  /// Average theta - kept here as only for primal
225  double averageTheta_;
226  /// Number of rows (mainly for checking and copy)
227  int numberRows_;
228  /// Number of columns (mainly for checking and copy)
229  int numberColumns_;
230  /// Starts for each entry (columns then rows)
231  int * start_;
232  /// Range for each entry (columns then rows)
233  int * whichRange_;
234  /// Temporary range offset for each entry (columns then rows)
235  int * offset_;
236  /** Lower bound for each range (upper bound is next lower).
237      For various reasons there is always an infeasible range
238      at bottom - even if lower bound is - infinity */
239  double * lower_;
240  /// Cost for each range
241  double * cost_;
242  /// Model
243  ClpSimplex * model_;
244  // Array to say which regions are infeasible
245  unsigned int * infeasible_;
246  /// Number of infeasibilities found
247  int numberInfeasibilities_;
248  /// If all non-linear costs convex
249  bool convex_;
250  /// If we should look both ways for djs
251  bool bothWays_;
252  //@}
253};
254
255#endif
Note: See TracBrowser for help on using the repository browser.