 |
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
|
#include <preprocessor.h>
Public Member Functions | |
| ProportionalColumnPreprocessor (const GlopParameters *parameters) | |
| ProportionalColumnPreprocessor (const ProportionalColumnPreprocessor &)=delete | |
| ProportionalColumnPreprocessor & | operator= (const ProportionalColumnPreprocessor &)=delete |
| ~ProportionalColumnPreprocessor () final=default | |
| bool | Run (LinearProgram *lp) final |
| void | RecoverSolution (ProblemSolution *solution) const final |
| void | UseInMipContext () final |
 Public Member Functions inherited from operations_research::glop::Preprocessor | |
| Preprocessor (const GlopParameters *parameters) | |
| Preprocessor (const Preprocessor &)=delete | |
| Preprocessor & | operator= (const Preprocessor &)=delete |
| virtual | ~Preprocessor () |
| ProblemStatus | status () const |
| void | SetTimeLimit (TimeLimit *time_limit) |
Additional Inherited Members | |
| Protected Member Functions inherited from operations_research::glop::Preprocessor | |
| bool | IsSmallerWithinFeasibilityTolerance (Fractional a, Fractional b) const |
| bool | IsSmallerWithinPreprocessorZeroTolerance (Fractional a, Fractional b) const |
| Protected Attributes inherited from operations_research::glop::Preprocessor | |
| ProblemStatus | status_ |
| const GlopParameters & | parameters_ |
| bool | in_mip_context_ |
| std::unique_ptr< TimeLimit > | infinite_time_limit_ |
| TimeLimit * | time_limit_ |
ProportionalColumnPreprocessor Removes the proportional columns from the problem when possible. Two columns are proportional if one is a non-zero scalar multiple of the other.
Definition at line 307 of file preprocessor.h.
|
inlineexplicit |
Definition at line 309 of file preprocessor.h.
|
delete |
|
finaldefault |
|
delete |
|
finalvirtual |
Stores the optimal solution of the linear program that was passed to Run(). The given solution needs to be set to the optimal solution of the linear program "modified" by Run().
The rest of this function is to unmerge the columns so that the solution be primal-feasible.
The first pass is a loop over the representatives to compute the current distance to the new bounds.
Restore the representative value to a feasible value of the initial variable. Now all the merged variable are at a feasible value.
Second pass to correct the values.
If the distance is finite, then each variable is set to its corresponding bound (the one from which the distance is computed) and is then changed by as much as possible until the distance is zero.
If the distance is not finite, then only one variable needs to be changed from its current feasible value in order to have a primal-feasible solution.
This should not happen on an OPTIMAL or FEASIBLE solution.
Implements operations_research::glop::Preprocessor.
Definition at line 738 of file preprocessor.cc.
|
finalvirtual |
Runs the preprocessor by modifying the given linear program. Returns true if a postsolve step will be needed (i.e. RecoverSolution() is not the identity function). Also updates status_ to something different from ProblemStatus::INIT if the problem was solved (including bad statuses like ProblemStatus::ABNORMAL, ProblemStatus::INFEASIBLE, etc.).
Compute some statistics and make each class representative point to itself in the mapping. Also store the columns that are proportional to at least another column in proportional_columns to iterate on them more efficiently.
Note(user): using the first coefficient may not give the best precision.
This is only meaningful for column representative.
The reduced cost of a column is 'cost - dual_values.column' and we know that for all proportional columns, 'dual_values.column / column_factors_[col]' is the same. Here, we bound this quantity which is related to the cost 'slope' of a proportional column: cost / column_factors_[col].
We reason in terms of a minimization problem here.
Deal with empty slope intervals.
This is only needed for class representative columns.
Now, fix the columns that can be fixed to one of their bounds.
The scaled reduced cost is slope - quantity.
The scaled reduced cost is < 0.
The scaled reduced cost is > 0.
Clear mapping[col] so this column will not be considered for the next stage.
Merge the variables with the same scaled cost.
This test is needed because we already removed some columns.
All this will be needed during postsolve.
Save the initial bounds before modifying them.
This is a bit counter intuitive, but when a column is divided by x, the corresponding bounds have to be multiplied by x.
We need to shift the variable so that a basic solution of the new problem can easily be converted to a basic solution of the original problem.
A feasible value for the variable must be chosen, and the variable must be shifted by this value. This is done to make sure that it will be possible to recreate a basic solution of the original problem from a basic solution of the pre-solved problem during post-solve.
If at least one column was merged, the target column must be shifted like the other columns in the same equivalence class for the same reason (see above).
Implements operations_research::glop::Preprocessor.
Definition at line 509 of file preprocessor.cc.
|
inlinefinalvirtual |
Some preprocessors only need minimal changes when used with integer variables in a MIP context. Setting this to true allows to consider integer variables as integer in these preprocessors.
Not all preprocessors handle integer variables correctly, calling this function on them will cause a LOG(FATAL).
Reimplemented from operations_research::glop::Preprocessor.
Definition at line 318 of file preprocessor.h.
1.12.0