OR-Tools  8.2
initial_basis.h
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_GLOP_INITIAL_BASIS_H_
15#define OR_TOOLS_GLOP_INITIAL_BASIS_H_
16
20
21namespace operations_research {
22namespace glop {
23
24// This class implements two initial basis algorithms. The idea is to replace as
25// much as possible the columns of B that correspond to fixed slack variables
26// with some column of A in order to have more freedom in the values the basic
27// variables can take.
28//
29// The first algorithm is Bixby's initial basis algorithm, described in the
30// paper below. It considers the columns of A in a particular order (the ones
31// with more freedom first) and adds the current column to the basis if it keeps
32// B almost triangular and with coefficients close to 1.0 on the diagonal for
33// good numerical stability.
34//
35// Robert E. Bixby, "Implementing the Simplex Method: The Initial Basis"
36// ORSA Jounal on Computing, Vol. 4, No. 3, Summer 1992.
37// http://joc.journal.informs.org/content/4/3/267.abstract
38//
39// The second algorithm is is similar to the "advanced initial basis" that GLPK
40// uses by default. It adds columns one by one to the basis B while keeping it
41// triangular (not almost triangular as in Bixby's algorithm). The next
42// column to add is chosen amongst the set of possible candidates using a
43// heuristic similar to the one used by Bixby.
45 public:
46 // Takes references to the linear program data we need.
47 InitialBasis(const CompactSparseMatrix& compact_matrix,
48 const DenseRow& objective, const DenseRow& lower_bound,
49 const DenseRow& upper_bound,
50 const VariableTypeRow& variable_type);
51
52 // Completes the entries of the given basis that are equal to kInvalidCol with
53 // one of the first num_cols columns of A using Bixby's algorithm.
54 //
55 // Important: For this function, the matrix must be scaled such that the
56 // maximum absolute value in each column is 1.0.
57 void CompleteBixbyBasis(ColIndex num_cols, RowToColMapping* basis);
58
59 // Similar to CompleteBixbyBasis() but completes the basis into a triangular
60 // one. This function usually produces better initial bases. The dual version
61 // just restricts the possible entering columns to the ones with a cost of 0.0
62 // in order to always start with the all-zeros vector of dual values.
63 //
64 // Returns false if an error occurred during the algorithm (numerically
65 // instable basis).
66 void CompleteTriangularPrimalBasis(ColIndex num_cols, RowToColMapping* basis);
67 void CompleteTriangularDualBasis(ColIndex num_cols, RowToColMapping* basis);
68
69 // Use Maros's LTSF crash from the book "Computational Techniques of the
70 // Simplex Method". Unlike the other crashes this does not use the initial
71 // content of the basis parameter.
72 void GetPrimalMarosBasis(ColIndex num_cols, RowToColMapping* basis);
73 void GetDualMarosBasis(ColIndex num_cols, RowToColMapping* basis);
74
75 // Visible for testing. Computes a list of candidate column indices out of the
76 // fist num_candidate_columns of A and sorts them using the
77 // bixby_column_comparator_. This also fills max_scaled_abs_cost_.
78 void ComputeCandidates(ColIndex num_cols, std::vector<ColIndex>* candidates);
79
80 private:
81 // Internal implementation of the Primal/Dual CompleteTriangularBasis().
82 template <bool only_allow_zero_cost_column>
83 void CompleteTriangularBasis(ColIndex num_cols, RowToColMapping* basis);
84
85 template <bool only_allow_zero_cost_column>
86 void GetMarosBasis(ColIndex num_cols, RowToColMapping* basis);
87
88 // Returns an integer representing the order (the lower the better)
89 // between column categories (known as C2, C3 or C4 in the paper).
90 // Also returns a greater index for fixed columns.
91 int GetColumnCategory(ColIndex col) const;
92
93 // Row and column priorities for Maros crash.
94 int GetMarosPriority(RowIndex row) const;
95 int GetMarosPriority(ColIndex col) const;
96
97 // Returns the penalty (the lower the better) of a column. This is 'q_j' for a
98 // column 'j' in the paper.
99 Fractional GetColumnPenalty(ColIndex col) const;
100
101 // Maximum scaled absolute value of the objective for the columns which are
102 // entering candidates. This is used by GetColumnPenalty().
103 Fractional max_scaled_abs_cost_;
104
105 // Comparator used to sort column indices according to their penalty.
106 // Lower is better.
107 struct BixbyColumnComparator {
108 explicit BixbyColumnComparator(const InitialBasis& initial_basis)
109 : initial_basis_(initial_basis) {}
110 bool operator()(ColIndex col_a, ColIndex col_b) const;
111 const InitialBasis& initial_basis_;
112 } bixby_column_comparator_;
113
114 // Comparator used by CompleteTriangularBasis(). Note that this one is meant
115 // to be used by a priority queue, so higher is better.
116 struct TriangularColumnComparator {
117 explicit TriangularColumnComparator(const InitialBasis& initial_basis)
118 : initial_basis_(initial_basis) {}
119 bool operator()(ColIndex col_a, ColIndex col_b) const;
120 const InitialBasis& initial_basis_;
121 } triangular_column_comparator_;
122
123 const CompactSparseMatrix& compact_matrix_;
124 const DenseRow& objective_;
125 const DenseRow& lower_bound_;
126 const DenseRow& upper_bound_;
127 const VariableTypeRow& variable_type_;
128
129 DISALLOW_COPY_AND_ASSIGN(InitialBasis);
130};
131
132} // namespace glop
133} // namespace operations_research
134
135#endif // OR_TOOLS_GLOP_INITIAL_BASIS_H_
void CompleteTriangularPrimalBasis(ColIndex num_cols, RowToColMapping *basis)
void CompleteTriangularDualBasis(ColIndex num_cols, RowToColMapping *basis)
InitialBasis(const CompactSparseMatrix &compact_matrix, const DenseRow &objective, const DenseRow &lower_bound, const DenseRow &upper_bound, const VariableTypeRow &variable_type)
void CompleteBixbyBasis(ColIndex num_cols, RowToColMapping *basis)
void GetDualMarosBasis(ColIndex num_cols, RowToColMapping *basis)
void GetPrimalMarosBasis(ColIndex num_cols, RowToColMapping *basis)
void ComputeCandidates(ColIndex num_cols, std::vector< ColIndex > *candidates)
ColIndex col
Definition: markowitz.cc:176
RowIndex row
Definition: markowitz.cc:175
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...