Toggle navigation
SCIP Optimization Suite
SCIP
SoPlex
ZIMPL
UG
GCG
Documentation
SoPlex 6.0.3
SoPlex 5.0.2
SoPlex 4.0.2
SoPlex 3.1.0
SoPlex 3.0.1
SoPlex 2.2.1
SoPlex
Sequential object-oriented simPlex
Main Page
Related Pages
Modules
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Friends
Macros
Groups
Pages
soplex-repo
src
spxsteeppr.h
Go to the documentation of this file.
1
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2
/* */
3
/* This file is part of the class library */
4
/* SoPlex --- the Sequential object-oriented simPlex. */
5
/* */
6
/* Copyright (C) 1996-2015 Konrad-Zuse-Zentrum */
7
/* fuer Informationstechnik Berlin */
8
/* */
9
/* SoPlex is distributed under the terms of the ZIB Academic Licence. */
10
/* */
11
/* You should have received a copy of the ZIB Academic License */
12
/* along with SoPlex; see the file COPYING. If not email to soplex@zib.de. */
13
/* */
14
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16
17
/**@file spxsteeppr.h
18
* @brief Steepest edge pricer.
19
*/
20
#ifndef _SPXSTEEPPR_H_
21
#define _SPXSTEEPPR_H_
22
23
24
#include <assert.h>
25
26
#include "
spxdefines.h
"
27
#include "
spxpricer.h
"
28
#include "
random.h
"
29
30
namespace
soplex
31
{
32
33
/**@brief Steepest edge pricer.
34
@ingroup Algo
35
36
Class SPxSteepPR implements a steepest edge pricer to be used with
37
SoPlex.
38
39
See SPxPricer for a class documentation.
40
*/
41
class
SPxSteepPR
:
public
SPxPricer
42
{
43
public
:
44
45
//-------------------------------------
46
/**@name Types */
47
//@{
48
/// How to setup the direction multipliers.
49
/** Possible settings are #EXACT for starting with exactly computed
50
values, or #DEFAULT for starting with multipliers set to 1. The
51
latter is the default.
52
*/
53
enum
Setup
{
54
EXACT
,
///< starting with exactly computed values
55
DEFAULT
///< starting with multipliers set to 1
56
};
57
//@}
58
/// setup steepest edge weights
59
void
setupWeights
(
SPxSolver::Type
type);
60
61
private
:
62
63
//-------------------------------------
64
/**@name Data */
65
//@{
66
/// working vector
67
SSVector
workVec
;
68
/// working vector
69
SSVector
workRhs
;
70
/// temporary array of precomputed pricing values
71
DataArray<IdxElement>
prices
;
72
/// temporary array of precomputed pricing values
73
DataArray<IdxElement>
pricesCo
;
74
/// array of best pricing candidates
75
DIdxSet
bestPrices
;
76
/// array of best pricing candidates
77
DIdxSet
bestPricesCo
;
78
///
79
Real
pi_p
;
80
///
81
int
prefSetup
;
82
/// preference multiplier for selecting as pivot
83
DataArray < Real >
coPref
;
84
/// preference multiplier for selecting as pivot
85
DataArray < Real >
pref
;
86
///
87
DataArray < Real >
leavePref
;
88
/// setup type.
89
Setup
setup
;
90
/// has a refinement step already been tried?
91
bool
refined
;
92
//@}
93
94
//-------------------------------------
95
/**@name Preferences */
96
//@{
97
///
98
void
setupPrefsX
(
Real
mult,
Real
/*tie*/
,
Real
/*cotie*/
,
Real
shift,
Real
coshift);
99
///
100
void
setupPrefs
(
SPxSolver::Type
);
101
//@}
102
103
//-------------------------------------
104
/// prepare data structures for hyper sparse pricing
105
int
buildBestPriceVectorLeave
(
Real
feastol );
106
/// implementation of full pricing
107
int
selectLeaveX
(
Real
tol);
108
/// implementation of sparse pricing in the leaving Simplex
109
int
selectLeaveSparse
(
Real
tol);
110
/// implementation of hyper sparse pricing in the leaving Simplex
111
int
selectLeaveHyper
(
Real
tol);
112
/// build up vector of pricing values for later use
113
SPxId
buildBestPriceVectorEnterDim
(
Real
& best,
Real
feastol);
114
SPxId
buildBestPriceVectorEnterCoDim
(
Real
& best,
Real
feastol);
115
/// choose the best entering index among columns and rows but prefer sparsity
116
SPxId
selectEnterX
(
Real
tol);
117
/// implementation of sparse pricing for the entering Simplex (slack variables)
118
SPxId
selectEnterSparseDim
(
Real
& best,
Real
tol);
119
/// implementation of sparse pricing for the entering Simplex
120
SPxId
selectEnterSparseCoDim
(
Real
& best,
Real
tol);
121
/// implementation of selectEnter() in dense case (slack variables)
122
SPxId
selectEnterDenseDim
(
Real
& best,
Real
tol);
123
/// implementation of selectEnter() in dense case
124
SPxId
selectEnterDenseCoDim
(
Real
& best,
Real
tol);
125
/// implementation of hyper sparse pricing in the entering Simplex
126
SPxId
selectEnterHyperDim
(
Real
& best,
Real
feastol);
127
/// implementation of hyper sparse pricing in the entering Simplex
128
SPxId
selectEnterHyperCoDim
(
Real
& best,
Real
feastol);
129
130
public
:
131
132
//-------------------------------------
133
/**@name Construction / destruction */
134
//@{
135
///
136
SPxSteepPR
(
const
char
* name =
"Steep"
,
Setup
mode =
DEFAULT
)
137
:
SPxPricer
(name)
138
,
workVec
(0)
139
,
workRhs
(0)
140
,
pi_p
(1.0)
141
,
prefSetup
(0)
142
,
setup
(mode)
143
,
refined
(false)
144
{
145
assert(
isConsistent
());
146
}
147
/// copy constructor
148
SPxSteepPR
(
const
SPxSteepPR
& old)
149
:
SPxPricer
(old)
150
,
workVec
(old.
workVec
)
151
,
workRhs
(old.
workRhs
)
152
,
pi_p
(old.
pi_p
)
153
,
prefSetup
(old.
prefSetup
)
154
,
coPref
(old.
coPref
)
155
,
pref
(old.
pref
)
156
,
leavePref
(old.
leavePref
)
157
,
setup
(old.
setup
)
158
,
refined
(old.
refined
)
159
{
160
assert(
isConsistent
());
161
}
162
/// assignment operator
163
SPxSteepPR
&
operator=
(
const
SPxSteepPR
& rhs)
164
{
165
if
(
this
!= &rhs)
166
{
167
SPxPricer::operator=
(rhs);
168
workVec
= rhs.
workVec
;
169
workRhs
= rhs.
workRhs
;
170
pi_p
= rhs.
pi_p
;
171
prefSetup
= rhs.
prefSetup
;
172
coPref
= rhs.
coPref
;
173
pref
= rhs.
pref
;
174
leavePref
= rhs.
leavePref
;
175
setup
= rhs.
setup
;
176
refined
= rhs.
refined
;
177
178
assert(
isConsistent
());
179
}
180
181
return
*
this
;
182
}
183
/// destructor
184
virtual
~SPxSteepPR
()
185
{}
186
/// clone function for polymorphism
187
inline
virtual
SPxPricer
*
clone
()
const
188
{
189
return
new
SPxSteepPR
(*
this
);
190
}
191
//@}
192
193
//-------------------------------------
194
/**@name Access / modification */
195
//@{
196
/// sets the solver
197
virtual
void
load
(
SPxSolver
* base);
198
/// clear solver and preferences
199
virtual
void
clear
();
200
/// set entering/leaving algorithm
201
virtual
void
setType
(
SPxSolver::Type
);
202
/// set row/column representation
203
virtual
void
setRep
(
SPxSolver::Representation
rep);
204
///
205
virtual
int
selectLeave
();
206
///
207
virtual
void
left4
(
int
n,
SPxId
id
);
208
///
209
virtual
SPxId
selectEnter
();
210
///
211
virtual
void
entered4
(
SPxId
id
,
int
n);
212
/// \p n vectors have been added to loaded LP.
213
virtual
void
addedVecs
(
int
n);
214
/// \p n covectors have been added to loaded LP.
215
virtual
void
addedCoVecs
(
int
n);
216
/// \p the i'th vector has been removed from the loaded LP.
217
virtual
void
removedVec
(
int
i);
218
/// \p the i'th covector has been removed from the loaded LP.
219
virtual
void
removedCoVec
(
int
i);
220
/// \p n vectors have been removed from loaded LP.
221
virtual
void
removedVecs
(
const
int
perm[]);
222
/// \p n covectors have been removed from loaded LP.
223
virtual
void
removedCoVecs
(
const
int
perm[]);
224
//@}
225
226
//-------------------------------------
227
/**@name Consistency check */
228
//@{
229
///
230
virtual
bool
isConsistent
()
const
;
231
//@}
232
};
233
234
}
// namespace soplex
235
#endif // _SPXSTEEPPR_H_