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
spxdevexpr.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
/**@file spxdevexpr.h
17
* @brief Devex pricer.
18
*/
19
#ifndef _SPXDEVEXPR_H_
20
#define _SPXDEVEXPR_H_
21
22
#include <assert.h>
23
24
#include "
spxdefines.h
"
25
#include "
spxpricer.h
"
26
27
namespace
soplex
28
{
29
30
/**@brief Devex pricer.
31
@ingroup Algo
32
33
The Devex Pricer for SoPlex implements an approximate steepest edge pricing,
34
that does without solving an extra linear system and computing the scalar
35
products.
36
37
See SPxPricer for a class documentation.
38
39
@todo There seem to be problems with this pricer especially on the
40
greenbe[ab] problems with the entering algorithm
41
(row representation?).
42
*/
43
class
SPxDevexPR
:
public
SPxPricer
44
{
45
private
:
46
47
//-------------------------------------
48
/**@name Data */
49
//@{
50
Real
last
;
///< penalty, selected at last iteration.
51
DataArray<IdxElement>
prices
;
///< temporary array of precomputed pricing values
52
DataArray<IdxElement>
pricesCo
;
///< temporary array of precomputed pricing values
53
DIdxSet
bestPrices
;
///< set of best pricing candidates
54
DIdxSet
bestPricesCo
;
///< set of best pricing candidates
55
bool
refined;
///< has a refinement step already been tried?
56
///@}
57
58
//-------------------------------------
59
/**@name Private helpers */
60
//@{
61
/// set entering/leaving algorithm
62
void
init
(
SPxSolver::Type
);
63
/// build up vector of pricing values for later use
64
int
buildBestPriceVectorLeave
(
Real
feastol);
65
/// internal implementation of SPxPricer::selectLeave()
66
int
selectLeaveX
(
Real
feastol,
int
start = 0,
int
incr = 1);
67
/// implementation of sparse pricing in the leaving Simplex
68
int
selectLeaveSparse
(
Real
feastol);
69
/// implementation of hyper sparse pricing in the leaving Simplex
70
int
selectLeaveHyper
(
Real
feastol);
71
/// build up vector of pricing values for later use
72
SPxId
buildBestPriceVectorEnterDim
(
Real
& best,
Real
feastol);
73
SPxId
buildBestPriceVectorEnterCoDim
(
Real
& best,
Real
feastol);
74
/// choose the best entering index among columns and rows but prefer sparsity
75
SPxId
selectEnterX
(
Real
tol);
76
/// implementation of sparse pricing in the entering Simplex (slack variables)
77
SPxId
selectEnterSparseDim
(
Real
& best,
Real
feastol);
78
/// implementation of sparse pricing in the entering Simplex
79
SPxId
selectEnterSparseCoDim
(
Real
& best,
Real
feastol);
80
/// SPxPricer::selectEnter() in dense case (slack variabels)
81
SPxId
selectEnterDenseDim
(
Real
& best,
Real
feastol,
int
start = 0,
int
incr = 1);
82
/// SPxPricer::selectEnter() in dense case
83
SPxId
selectEnterDenseCoDim
(
Real
& best,
Real
feastol,
int
start = 0,
int
incr = 1);
84
/// implementation of hyper sparse pricing in the entering Simplex
85
SPxId
selectEnterHyperDim
(
Real
& best,
Real
feastol);
86
/// implementation of hyper sparse pricing in the entering Simplex
87
SPxId
selectEnterHyperCoDim
(
Real
& best,
Real
feastol);
88
//@}
89
90
public
:
91
92
//-------------------------------------
93
/**@name Construction / destruction */
94
//@{
95
/// default constructor
96
SPxDevexPR
()
97
:
SPxPricer
(
"Devex"
)
98
,
last
(0)
99
, refined(false)
100
{}
101
/// copy constructor
102
SPxDevexPR
(
const
SPxDevexPR
& old)
103
:
SPxPricer
(old)
104
,
last
(old.
last
)
105
, refined(false)
106
{}
107
/// assignment operator
108
SPxDevexPR
&
operator=
(
const
SPxDevexPR
& rhs)
109
{
110
if
(
this
!= &rhs)
111
{
112
SPxPricer::operator=
(rhs);
113
last
= rhs.
last
;
114
}
115
116
return
*
this
;
117
}
118
/// destructor
119
virtual
~SPxDevexPR
()
120
{}
121
/// clone function for polymorphism
122
inline
virtual
SPxPricer
*
clone
()
const
123
{
124
return
new
SPxDevexPR
(*
this
);
125
}
126
//@}
127
128
//-------------------------------------
129
/**@name Access / modification */
130
//@{
131
/// sets the solver
132
virtual
void
load
(
SPxSolver
* base);
133
/// set entering/leaving algorithm
134
virtual
void
setType
(
SPxSolver::Type
);
135
/// set row/column representation
136
virtual
void
setRep
(
SPxSolver::Representation
);
137
///
138
virtual
int
selectLeave
();
139
///
140
virtual
SPxId
selectEnter
();
141
///
142
virtual
void
left4
(
int
n,
SPxId
id
);
143
///
144
virtual
void
entered4
(
SPxId
id
,
int
n);
145
/// \p n vectors have been added to loaded LP.
146
virtual
void
addedVecs
(
int
n);
147
/// \p n covectors have been added to loaded LP.
148
virtual
void
addedCoVecs
(
int
n);
149
//@}
150
151
//-------------------------------------
152
/**@name Consistency check */
153
//@{
154
/// consistency check
155
virtual
bool
isConsistent
()
const
;
156
//@}
157
};
158
159
}
// namespace soplex
160
#endif // _SPXDEVEXPR_H_