Clp  1.16.11
AbcSimplexDual.hpp
Go to the documentation of this file.
1 /* $Id: AbcSimplexDual.hpp 1910 2013-01-27 02:00:13Z stefan $ */
2 // Copyright (C) 2002, International Business Machines
3 // Corporation and others, Copyright (C) 2012, FasterCoin. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 /*
6  Authors
7 
8  John Forrest
9 
10 */
11 #ifndef AbcSimplexDual_H
12 #define AbcSimplexDual_H
13 
14 #include "AbcSimplex.hpp"
15 #if 0
16 #undef ABC_PARALLEL
17 #define ABC_PARALLEL 2
18 #undef cilk_for
19 #undef cilk_spawn
20 #undef cilk_sync
21 #include <cilk/cilk.h>
22 #endif
23 typedef struct {
24  double theta;
25  double totalThru;
26  double useThru;
27  double bestEverPivot;
32  double thruThis;
35  int sequence;
36  int block;
49 class AbcSimplexDual : public AbcSimplex {
50 
51 public:
52 
144  int dual();
153  int strongBranching(int numberVariables, const int * variables,
154  double * newLower, double * newUpper,
155  double ** outputSolution,
156  int * outputStatus, int * outputIterations,
157  bool stopOnFirstInfeasible = true,
158  bool alwaysFinish = false,
159  int startFinishOptions = 0);
162  int numberColumns, bool solveLp = false);
166 
183 #if ABC_PARALLEL==1
184  int whileIteratingThread();
185 #endif
186 #if ABC_PARALLEL==2
187  int whileIteratingCilk();
188 #endif
193  int noPivotRow();
200 #if ABC_PARALLEL==1
201  void createDualPricingVectorThread();
203  int getTableauColumnFlipAndStartReplaceThread();
204  void getTableauColumnPart1Thread();
205 #endif
206 #if ABC_PARALLEL==2
207  void createDualPricingVectorCilk();
209  int getTableauColumnFlipAndStartReplaceCilk();
210  void getTableauColumnPart1Cilk();
211 #endif
223  //void updateDualsInValuesPass(CoinIndexedVector * array,
224  // double theta);
229  int flipBounds();
232  void flipBack(int number);
239  void dualColumn1(bool doAll=false);
245  double dualColumn1A();
247  double dualColumn1B();
253  void dualColumn2();
266  void checkPossibleCleanup(CoinIndexedVector * array);
273  void dualPivotRow();
281  int changeBounds(int initialize, double & changeCost);
284  bool changeBound( int iSequence);
286  void originalBound(int iSequence);
289  int checkUnbounded(CoinIndexedVector & ray, double changeCost);
299  void statusOfProblemInDual(int type);
305  int whatNext();
311  int bounceTolerances(int type);
313  void perturb(double factor);
315  void perturbB(double factor,int type);
317  int makeNonFreeVariablesDualFeasible(bool changeCosts=false);
318  int fastDual(bool alwaysFinish = false);
322 
331  void startupSolve();
333  void finishSolve();
334  void gutsOfDual();
335  //int dual2(int ifValuesPass,int startFinishOptions=0);
336  int resetFakeBounds(int type);
337 
339 };
340 #if ABC_PARALLEL==1
341 void * abc_parallelManager(void * simplex);
342 #endif
343 #endif
AbcSimplexDual::numberAtFakeBound
int numberAtFakeBound()
Checks number of variables at fake bounds.
AbcSimplexDual::getTableauColumnFlipAndStartReplaceSerial
int getTableauColumnFlipAndStartReplaceSerial()
AbcSimplexDual::updateDualsInDual
void updateDualsInDual()
The duals are updated.
AbcSimplexDual::perturbB
void perturbB(double factor, int type)
Perturbs problem B.
AbcSimplexDual::dualColumn2
void dualColumn2(dualColumnResult &result)
Chooses part of incoming Puts flipped ones in list If necessary will modify costs.
AbcSimplexDual::strongBranching
int strongBranching(int numberVariables, const int *variables, double *newLower, double *newUpper, double **outputSolution, int *outputStatus, int *outputIterations, bool stopOnFirstInfeasible=true, bool alwaysFinish=false, int startFinishOptions=0)
For strong branching.
AbcSimplexDual::whileIteratingSerial
int whileIteratingSerial()
This has the flow between re-factorizations Broken out for clarity and will be used by strong branchi...
AbcSimplexDual::checkReplacePart1
void checkReplacePart1()
AbcSimplexDual::dualColumn2First
void dualColumn2First(dualColumnResult &result)
AbcSimplexDual::perturb
void perturb(double factor)
Perturbs problem.
AbcSimplexDual::fastDual
int fastDual(bool alwaysFinish=false)
ClpModel::ray
double * ray() const
For advanced users - no need to delete - sign not changed.
Definition: ClpModel.hpp:772
AbcSimplexDual::whatNext
int whatNext()
Fast iterations.
dualColumnResult::lastPivotValue
double lastPivotValue
Definition: AbcSimplexDual.hpp:30
AbcSimplexDual::resetFakeBounds
int resetFakeBounds(int type)
AbcSimplexDual::whileIterating3
int whileIterating3()
AbcSimplexDual::bounceTolerances
int bounceTolerances(int type)
Does something about fake tolerances.
AbcSimplexDual::originalBound
void originalBound(int iSequence)
Restores bound to original bound.
dualColumnResult::useThru
double useThru
Definition: AbcSimplexDual.hpp:26
dualColumnResult::modifyCosts
bool modifyCosts
Definition: AbcSimplexDual.hpp:40
AbcSimplexDual::checkReplace
int checkReplace()
dualColumnResult::thruThis
double thruThis
Definition: AbcSimplexDual.hpp:32
AbcSimplexDual::pivotResultPart1
int pivotResultPart1()
Pivot in a variable and choose an outgoing one.
AbcSimplexDual::flipBack
void flipBack(int number)
Undo a flip.
AbcSimplexDual::dualPivotRow
void dualPivotRow()
Chooses dual pivot row Would be faster with separate region to scan and will have this (with square o...
AbcSimplexFactorization
This just implements AbcFactorization when an AbcMatrix object is passed.
Definition: AbcSimplexFactorization.hpp:28
AbcSimplexDual::whileIterating2
void whileIterating2()
dualColumnResult::block
int block
Definition: AbcSimplexDual.hpp:36
AbcSimplexDual::getTableauColumnPart2
void getTableauColumnPart2()
AbcSimplexDual::getTableauColumnPart1Serial
void getTableauColumnPart1Serial()
AbcSimplexDual::dualPivotColumn
void dualPivotColumn()
AbcSimplexDual::changeBounds
int changeBounds(int initialize, double &changeCost)
Checks if any fake bounds active - if so returns number and modifies updatedDualBound_ and everything...
AbcSimplexDual::noPivotRow
int noPivotRow()
AbcSimplexDual::checkUnbounded
int checkUnbounded(CoinIndexedVector &ray, double changeCost)
Checks if tentative optimal actually means unbounded in dual Returns -3 if not, 2 if is unbounded.
dualColumnResult::increaseInThis
double increaseInThis
Definition: AbcSimplexDual.hpp:33
AbcSimplex::computeObjective
void computeObjective()
Computes nonbasic cost and total cost.
dualColumnResult::totalThru
double totalThru
Definition: AbcSimplexDual.hpp:25
AbcSimplexDual::checkPossibleCleanup
void checkPossibleCleanup(CoinIndexedVector *array)
This sees what is best thing to do in branch and bound cleanup If sequenceIn_ < 0 then can't do anyth...
dualColumnResult::theta
double theta
Definition: AbcSimplexDual.hpp:24
AbcSimplexDual::flipBounds
int flipBounds()
The duals are updated by the given arrays.
AbcSimplex
Definition: AbcSimplex.hpp:62
AbcSimplex::factorization
AbcSimplexFactorization * factorization() const
factorization
Definition: AbcSimplex.hpp:199
AbcSimplexDual::changeBound
bool changeBound(int iSequence)
As changeBounds but just changes new bounds for a single variable.
dualColumnResult::sequence
int sequence
Definition: AbcSimplexDual.hpp:35
dualColumnResult::bestEverPivot
double bestEverPivot
Definition: AbcSimplexDual.hpp:27
dualColumnResult::tentativeTheta
double tentativeTheta
Definition: AbcSimplexDual.hpp:29
dualColumnResult::increaseInObjective
double increaseInObjective
Definition: AbcSimplexDual.hpp:28
AbcSimplexDual::dual
int dual()
Dual algorithm.
AbcSimplexDual::cleanupAfterStrongBranching
void cleanupAfterStrongBranching(AbcSimplexFactorization *factorization)
This cleans up after strong branching.
AbcSimplexDual::checkReplacePart1a
void checkReplacePart1a()
dualColumnResult::numberLastSwapped
int numberLastSwapped
Definition: AbcSimplexDual.hpp:39
AbcSimplexDual::createDualPricingVectorSerial
void createDualPricingVectorSerial()
Create dual pricing vector.
ClpModel::numberIterations
int numberIterations() const
Number of iterations.
Definition: ClpModel.hpp:363
AbcSimplexDual::dualColumn2
void dualColumn2()
Chooses incoming Puts flipped ones in list If necessary will modify costs.
AbcSimplex.hpp
AbcSimplexDual::checkReplacePart1b
void checkReplacePart1b()
dualColumnResult::numberRemaining
int numberRemaining
Definition: AbcSimplexDual.hpp:38
dualColumnResult::numberSwapped
int numberSwapped
Definition: AbcSimplexDual.hpp:37
AbcSimplexDual::makeNonFreeVariablesDualFeasible
int makeNonFreeVariablesDualFeasible(bool changeCosts=false)
Make non free variables dual feasible by moving to a bound.
ClpModel::numberColumns
int numberColumns() const
Definition: ClpModel.hpp:325
AbcSimplexDual
This solves LPs using the dual simplex method.
Definition: AbcSimplexDual.hpp:49
AbcSimplexDual::statusOfProblemInDual
void statusOfProblemInDual(int type)
Refactorizes if necessary Checks if finished.
AbcSimplexDual::gutsOfDual
void gutsOfDual()
dualColumnResult::thisPivotValue
double thisPivotValue
Definition: AbcSimplexDual.hpp:31
AbcSimplexDual::updatePrimalSolution
void updatePrimalSolution()
AbcSimplexDual::noPivotColumn
int noPivotColumn()
AbcSimplexDual::replaceColumnPart3
void replaceColumnPart3()
AbcSimplexDual::nextSuperBasic
int nextSuperBasic()
Get next free , -1 if none.
AbcSimplexDual::checkCutoff
bool checkCutoff(bool computeObjective)
see if cutoff reached
dualColumnResult
Definition: AbcSimplexDual.hpp:23
AbcSimplexDual::setupForStrongBranching
AbcSimplexFactorization * setupForStrongBranching(char *arrays, int numberRows, int numberColumns, bool solveLp=false)
This does first part of StrongBranching.
AbcSimplexDual::dualColumn1
void dualColumn1(bool doAll=false)
Array has tableau row (row section) Puts candidates for rows in list Returns guess at upper theta (in...
AbcSimplexDual::finishSolve
void finishSolve()
Ending part of dual.
AbcSimplexDual::dualColumn1A
double dualColumn1A()
Array has tableau row (row section) Just does slack part Returns guess at upper theta (infinite if no...
dualColumnResult::lastSequence
int lastSequence
Definition: AbcSimplexDual.hpp:34
AbcSimplexDual::startupSolve
void startupSolve()
Startup part of dual.
AbcSimplexDual::dualColumn1B
double dualColumn1B()
Do all given tableau row.
AbcSimplexDual::dualColumn2Most
void dualColumn2Most(dualColumnResult &result)
ClpModel::numberRows
int numberRows() const
Number of rows.
Definition: ClpModel.hpp:315
AbcSimplexDual::whileIteratingParallel
int whileIteratingParallel(int numberIterations)