21 #ifndef OR_TOOLS_GLOP_PREPROCESSOR_H_
22 #define OR_TOOLS_GLOP_PREPROCESSOR_H_
27 #include "ortools/glop/parameters.pb.h"
117 void RunAndPushIfRelevant(std::unique_ptr<Preprocessor> preprocessor,
126 mutable std::vector<std::unique_ptr<Preprocessor>> preprocessors_;
129 EntryIndex initial_num_entries_;
130 RowIndex initial_num_rows_;
131 ColIndex initial_num_cols_;
162 return col < is_column_deleted_.
size() && is_column_deleted_[
col];
217 return row < is_row_deleted_.
size() && is_row_deleted_[
row];
315 bool lp_is_maximization_problem_;
368 void SingletonRowUndo(
const SparseMatrix& deleted_columns,
370 void ZeroCostSingletonColumnUndo(
const GlopParameters&
parameters,
373 void SingletonColumnInEqualityUndo(
const GlopParameters&
parameters,
380 bool is_maximization_;
410 MatrixEntry GetSingletonColumnMatrixEntry(ColIndex
col,
412 MatrixEntry GetSingletonRowMatrixEntry(RowIndex
row,
422 void UpdateConstraintBoundsWithVariableBounds(MatrixEntry e,
427 bool IntegerSingletonColumnIsRemovable(
const MatrixEntry& matrix_entry,
433 void DeleteZeroCostSingletonColumn(
const SparseMatrix& matrix_transpose,
453 bool MakeConstraintAnEqualityIfPossible(
const SparseMatrix& matrix_transpose,
459 void DeleteSingletonColumnInEquality(
const SparseMatrix& matrix_transpose,
464 std::vector<SingletonUndo> undo_stack_;
534 bool lp_is_maximization_problem_;
639 RowIndex
row[NUM_ROWS];
643 SparseColumn deleted_row_as_column;
646 std::vector<RestoreInfo> restore_stack_;
647 RowDeletionHelper row_deletion_helper_;
796 std::vector<ColIndex> changed_columns_;
822 NUM_DOUBLETON_COLS = 2,
824 static ColChoice OtherColChoice(ColChoice x) {
825 return x == DELETED ? MODIFIED : DELETED;
828 ColumnDeletionHelper column_deletion_helper_;
829 RowDeletionHelper row_deletion_helper_;
838 ColIndex
col[NUM_DOUBLETON_COLS];
842 SparseColumn column[NUM_DOUBLETON_COLS];
843 Fractional objective_coefficient[NUM_DOUBLETON_COLS];
858 ColChoiceAndStatus bound_backtracking_at_lower_bound;
859 ColChoiceAndStatus bound_backtracking_at_upper_bound;
861 void SwapDeletedAndModifiedVariableRestoreInfo(RestoreInfo* r);
863 std::vector<RestoreInfo> restore_stack_;
882 ProblemSolution* solution);
902 LOG(
FATAL) <<
"In the presence of integer variables, "
903 <<
"there is no notion of a dual problem.";
913 RowIndex primal_num_rows_;
914 ColIndex primal_num_cols_;
915 bool primal_is_maximization_problem_;
1040 ColIndex first_slack_col_;
A simple class to enforce both an elapsed time limit and a deterministic time limit in the same threa...
AddSlackVariablesPreprocessor(const AddSlackVariablesPreprocessor &)=delete
AddSlackVariablesPreprocessor(const GlopParameters *parameters)
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
AddSlackVariablesPreprocessor & operator=(const AddSlackVariablesPreprocessor &)=delete
~AddSlackVariablesPreprocessor() final
ColumnDeletionHelper(const ColumnDeletionHelper &)=delete
bool IsColumnMarked(ColIndex col) const
void MarkColumnForDeletionWithState(ColIndex col, Fractional value, VariableStatus status)
void MarkColumnForDeletion(ColIndex col)
const DenseBooleanRow & GetMarkedColumns() const
void RestoreDeletedColumns(ProblemSolution *solution) const
const DenseRow & GetStoredValue() const
ColumnDeletionHelper & operator=(const ColumnDeletionHelper &)=delete
~DoubletonEqualityRowPreprocessor() final
DoubletonEqualityRowPreprocessor(const DoubletonEqualityRowPreprocessor &)=delete
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
DoubletonEqualityRowPreprocessor(const GlopParameters *parameters)
DoubletonEqualityRowPreprocessor & operator=(const DoubletonEqualityRowPreprocessor &)=delete
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
~DoubletonFreeColumnPreprocessor() final
DoubletonFreeColumnPreprocessor(const DoubletonFreeColumnPreprocessor &)=delete
DoubletonFreeColumnPreprocessor(const GlopParameters *parameters)
DoubletonFreeColumnPreprocessor & operator=(const DoubletonFreeColumnPreprocessor &)=delete
DualizerPreprocessor(const DualizerPreprocessor &)=delete
~DualizerPreprocessor() final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
DualizerPreprocessor & operator=(const DualizerPreprocessor &)=delete
ProblemStatus ChangeStatusToDualStatus(ProblemStatus status) const
void UseInMipContext() final
DualizerPreprocessor(const GlopParameters *parameters)
EmptyColumnPreprocessor & operator=(const EmptyColumnPreprocessor &)=delete
EmptyColumnPreprocessor(const GlopParameters *parameters)
~EmptyColumnPreprocessor() final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
EmptyColumnPreprocessor(const EmptyColumnPreprocessor &)=delete
~EmptyConstraintPreprocessor() final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
EmptyConstraintPreprocessor(const EmptyConstraintPreprocessor &)=delete
EmptyConstraintPreprocessor(const GlopParameters *parameters)
EmptyConstraintPreprocessor & operator=(const EmptyConstraintPreprocessor &)=delete
FixedVariablePreprocessor(const FixedVariablePreprocessor &)=delete
FixedVariablePreprocessor & operator=(const FixedVariablePreprocessor &)=delete
~FixedVariablePreprocessor() final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
FixedVariablePreprocessor(const GlopParameters *parameters)
ForcingAndImpliedFreeConstraintPreprocessor(const GlopParameters *parameters)
ForcingAndImpliedFreeConstraintPreprocessor(const ForcingAndImpliedFreeConstraintPreprocessor &)=delete
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
ForcingAndImpliedFreeConstraintPreprocessor & operator=(const ForcingAndImpliedFreeConstraintPreprocessor &)=delete
~ForcingAndImpliedFreeConstraintPreprocessor() final
FreeConstraintPreprocessor & operator=(const FreeConstraintPreprocessor &)=delete
bool Run(LinearProgram *lp) final
FreeConstraintPreprocessor(const FreeConstraintPreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
~FreeConstraintPreprocessor() final
FreeConstraintPreprocessor(const GlopParameters *parameters)
ImpliedFreePreprocessor & operator=(const ImpliedFreePreprocessor &)=delete
bool Run(LinearProgram *lp) final
ImpliedFreePreprocessor(const ImpliedFreePreprocessor &)=delete
void RecoverSolution(ProblemSolution *solution) const final
ImpliedFreePreprocessor(const GlopParameters *parameters)
~ImpliedFreePreprocessor() final
void RecoverSolution(ProblemSolution *solution) const override
MainLpPreprocessor(const MainLpPreprocessor &)=delete
MainLpPreprocessor & operator=(const MainLpPreprocessor &)=delete
MainLpPreprocessor(const GlopParameters *parameters)
bool Run(LinearProgram *lp) final
~MainLpPreprocessor() override
ProblemStatus status() const
virtual void RecoverSolution(ProblemSolution *solution) const =0
bool IsSmallerWithinPreprocessorZeroTolerance(Fractional a, Fractional b) const
Preprocessor(const GlopParameters *parameters)
const GlopParameters & parameters_
Preprocessor(const Preprocessor &)=delete
std::unique_ptr< TimeLimit > infinite_time_limit_
virtual void UseInMipContext()
Preprocessor & operator=(const Preprocessor &)=delete
virtual bool Run(LinearProgram *lp)=0
void SetTimeLimit(TimeLimit *time_limit)
bool IsSmallerWithinFeasibilityTolerance(Fractional a, Fractional b) const
ProportionalColumnPreprocessor(const ProportionalColumnPreprocessor &)=delete
ProportionalColumnPreprocessor(const GlopParameters *parameters)
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
ProportionalColumnPreprocessor & operator=(const ProportionalColumnPreprocessor &)=delete
void UseInMipContext() final
~ProportionalColumnPreprocessor() final
~ProportionalRowPreprocessor() final
bool Run(LinearProgram *lp) final
ProportionalRowPreprocessor(const GlopParameters *parameters)
void RecoverSolution(ProblemSolution *solution) const final
ProportionalRowPreprocessor(const ProportionalRowPreprocessor &)=delete
ProportionalRowPreprocessor & operator=(const ProportionalRowPreprocessor &)=delete
RemoveNearZeroEntriesPreprocessor & operator=(const RemoveNearZeroEntriesPreprocessor &)=delete
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
RemoveNearZeroEntriesPreprocessor(const GlopParameters *parameters)
~RemoveNearZeroEntriesPreprocessor() final
RemoveNearZeroEntriesPreprocessor(const RemoveNearZeroEntriesPreprocessor &)=delete
void MarkRowForDeletion(RowIndex row)
void UnmarkRow(RowIndex row)
void RestoreDeletedRows(ProblemSolution *solution) const
const DenseBooleanColumn & GetMarkedRows() const
RowDeletionHelper & operator=(const RowDeletionHelper &)=delete
bool IsRowMarked(RowIndex row) const
RowDeletionHelper(const RowDeletionHelper &)=delete
ScalingPreprocessor & operator=(const ScalingPreprocessor &)=delete
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
void UseInMipContext() final
ScalingPreprocessor(const ScalingPreprocessor &)=delete
~ScalingPreprocessor() final
ScalingPreprocessor(const GlopParameters *parameters)
ShiftVariableBoundsPreprocessor & operator=(const ShiftVariableBoundsPreprocessor &)=delete
ShiftVariableBoundsPreprocessor(const GlopParameters *parameters)
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
ShiftVariableBoundsPreprocessor(const ShiftVariableBoundsPreprocessor &)=delete
~ShiftVariableBoundsPreprocessor() final
const DenseRow & offsets() const
~SingletonColumnSignPreprocessor() final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
SingletonColumnSignPreprocessor & operator=(const SingletonColumnSignPreprocessor &)=delete
SingletonColumnSignPreprocessor(const GlopParameters *parameters)
SingletonColumnSignPreprocessor(const SingletonColumnSignPreprocessor &)=delete
SingletonPreprocessor(const SingletonPreprocessor &)=delete
~SingletonPreprocessor() final
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
SingletonPreprocessor(const GlopParameters *parameters)
SingletonPreprocessor & operator=(const SingletonPreprocessor &)=delete
SingletonUndo(OperationType type, const LinearProgram &lp, MatrixEntry e, ConstraintStatus status)
@ ZERO_COST_SINGLETON_COLUMN
@ MAKE_CONSTRAINT_AN_EQUALITY
@ SINGLETON_COLUMN_IN_EQUALITY
void Undo(const GlopParameters ¶meters, const SparseMatrix &deleted_columns, const SparseMatrix &deleted_rows, ProblemSolution *solution) const
ToMinimizationPreprocessor & operator=(const ToMinimizationPreprocessor &)=delete
ToMinimizationPreprocessor(const ToMinimizationPreprocessor &)=delete
bool Run(LinearProgram *lp) final
void RecoverSolution(ProblemSolution *solution) const final
ToMinimizationPreprocessor(const GlopParameters *parameters)
~ToMinimizationPreprocessor() final
void RemoveZeroCostUnconstrainedVariable(ColIndex col, Fractional target_bound, LinearProgram *lp)
UnconstrainedVariablePreprocessor & operator=(const UnconstrainedVariablePreprocessor &)=delete
bool Run(LinearProgram *lp) final
UnconstrainedVariablePreprocessor(const GlopParameters *parameters)
void RecoverSolution(ProblemSolution *solution) const final
UnconstrainedVariablePreprocessor(const UnconstrainedVariablePreprocessor &)=delete
~UnconstrainedVariablePreprocessor() final
SharedTimeLimit * time_limit
void FixConstraintWithFixedStatuses(const DenseColumn &row_lower_bounds, const DenseColumn &row_upper_bounds, ProblemSolution *solution)
StrictITIVector< RowIndex, Fractional > DenseColumn
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool IsSmallerWithinTolerance(FloatType x, FloatType y, FloatType tolerance)
ColChoiceAndStatus(ColChoice c, VariableStatus s, Fractional v)
MatrixEntry(RowIndex _row, ColIndex _col, Fractional _coeff)