source: trunk/include/ClpNonLinearCost.hpp @ 114

Last change on this file since 114 was 114, checked in by forrest, 19 years ago

Re-order variables

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 6.3 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 toNearest true*/
66  void checkInfeasibilities(bool toNearest=false);
67  /** Changes infeasible costs for each variable
68      The indices are row indices and need converting to sequences
69  */
70  void checkInfeasibilities(int numberInArray, const int * index);
71  /** Puts back correct infeasible costs for each variable
72      The input indices are row indices and need converting to sequences
73      for costs.
74      On input array is empty (but indices exist).  On exit just
75      changed costs will be stored as normal CoinIndexedVector
76  */
77  void checkChanged(int numberInArray, CoinIndexedVector * update);
78  /** Goes through one bound for each variable.
79      If multiplier*work[iRow]>0 goes down, otherwise up.
80      The indices are row indices and need converting to sequences
81      Temporary offsets may be set
82      Rhs entries are increased
83  */
84  void goThru(int numberInArray, double multiplier,
85              const int * index, const double * work,
86              double * rhs);
87  /** Takes off last iteration (i.e. offsets closer to 0)
88  */
89  void goBack(int numberInArray, const int * index, 
90              double * rhs);
91  /** Puts back correct infeasible costs for each variable
92      The input indices are row indices and need converting to sequences
93      for costs.
94      At the end of this all temporary offsets are zero
95  */
96  void goBackAll(const CoinIndexedVector * update);
97  /** Sets bounds and cost for one variable
98      Returns change in cost
99   May need to be inline for speed */
100  double setOne(int sequence, double solutionValue);
101  /// Returns nearest bound
102  double nearest(int sequence, double solutionValue);
103  /** Returns change in cost - one down if alpha >0.0, up if <0.0
104      Value is current - new
105   */
106  inline double changeInCost(int sequence, double alpha) const
107  {
108    int iRange = whichRange_[sequence]+offset_[sequence];
109    if (alpha>0.0)
110      return cost_[iRange]-cost_[iRange-1];
111    else
112      return cost_[iRange]-cost_[iRange+1];
113  }
114  /// Returns current lower bound
115  inline double lower(int sequence) const
116  { return lower_[whichRange_[sequence]+offset_[sequence]];};
117  /// Returns current upper bound
118  inline double upper(int sequence) const
119  { return lower_[whichRange_[sequence]+offset_[sequence]+1];};
120  /// Returns current cost
121  inline double cost(int sequence) const
122  { return cost_[whichRange_[sequence]+offset_[sequence]];};
123  //@}
124
125
126  /**@name Gets and sets */
127  //@{
128  /// Number of infeasibilities
129  inline int numberInfeasibilities() const
130  {return numberInfeasibilities_;};
131  /// Change in cost
132  inline double changeInCost() const
133  {return changeCost_;};
134  /// Sum of infeasibilities
135  inline double sumInfeasibilities() const
136  {return sumInfeasibilities_;};
137  /// Largest infeasibility
138  inline double largestInfeasibility() const
139  {return largestInfeasibility_;};
140  inline void setChangeInCost(double value) 
141  {changeCost_ = value;};
142  //@}
143  ///@name Private functions to deal with infeasible regions
144  inline bool infeasible(int i) const {
145    return ((infeasible_[i>>5]>>(i&31))&1)!=0;
146  }
147  inline void setInfeasible(int i,bool trueFalse) {
148    unsigned int & value = infeasible_[i>>5];
149    int bit = i&31;
150    if (trueFalse)
151      value |= (1<<bit);
152    else
153      value &= ~(1<<bit);
154  }
155  //@}
156   
157private:
158  /**@name Data members */
159  //@{
160  /// Change in cost because of infeasibilities
161  double changeCost_;
162  /// Largest infeasibility
163  double largestInfeasibility_;
164  /// Sum of infeasibilities
165  double sumInfeasibilities_;
166  /// Number of rows (mainly for checking and copy)
167  int numberRows_;
168  /// Number of columns (mainly for checking and copy)
169  int numberColumns_;
170  /// Starts for each entry (columns then rows)
171  int * start_;
172  /// Range for each entry (columns then rows)
173  int * whichRange_;
174  /// Temporary range offset for each entry (columns then rows)
175  int * offset_;
176  /** Lower bound for each range (upper bound is next lower).
177      For various reasons there is always an infeasible range
178      at bottom - even if lower bound is - infinity */
179  double * lower_;
180  /// Cost for each range
181  double * cost_;
182  /// Model
183  ClpSimplex * model_;
184  // Array to say which regions are infeasible
185  unsigned int * infeasible_;
186  /// Number of infeasibilities found
187  int numberInfeasibilities_;
188  /// If all non-linear costs convex
189  bool convex_;
190  //@}
191};
192
193#endif
Note: See TracBrowser for help on using the repository browser.