#include <cp_model_presolve.h>

Public Member Functions
	CpModelPresolver (PresolveContext context, std::vector< int > postsolve_mapping)

CpSolverStatus	Presolve ()

bool	PresolveOneConstraint (int c)
	Executes presolve method for the given constraint. Public for testing only.

void	RemoveEmptyConstraints ()
	Public for testing only.

Detailed Description

Presolves the initial content of presolved_model.

This also creates a mapping model that encode the correspondence between the two problems. This works as follow:

The first variables of mapping_model are in one to one correspondence with the variables of the initial model.
The presolved_model variables are in one to one correspondence with the variable at the indices given by postsolve_mapping in the mapping model.
Fixing one of the two sets of variables and solving the model will assign the other set to a feasible solution of the other problem. Moreover, the objective value of these solutions will be the same. Note that solving such problems will take little time in practice because the propagation will basically do all the work.

Note(user): an optimization model can be transformed into a decision problem, if for instance the objective is fixed, or independent from the rest of the problem.

Todo: (user): Identify disconnected components and returns a vector of presolved model? If we go this route, it may be nicer to store the indices inside the model. We can add a IntegerVariableProto::initial_index;

Definition at line 74 of file cp_model_presolve.h.

Constructor & Destructor Documentation

◆ CpModelPresolver()

operations_research::sat::CpModelPresolver::CpModelPresolver	(	PresolveContext *	context,
		std::vector< int > *	postsolve_mapping )

Definition at line 12602 of file cp_model_presolve.cc.

Member Function Documentation

◆ Presolve()

CpSolverStatus operations_research::sat::CpModelPresolver::Presolve ( )

We returns the status of the problem after presolve:

UNKNOWN if everything was ok.
INFEASIBLE if the model was proven so during presolve
MODEL_INVALID if the model caused some issues, like if we are not able to scale a floating point objective with enough precision.

The presolve works as follow:

First stage: We will process all active constraints until a fix point is reached. During this stage:

Variable will never be deleted, but their domain will be reduced.
Constraint will never be deleted (they will be marked as empty if needed).
New variables and new constraints can be added after the existing ones.
Constraints are added only when needed to the mapping_problem if they are needed during the postsolve.

Second stage:

All the variables domain will be copied to the mapping_model.
Everything will be remapped so that only the variables appearing in some constraints will be kept and their index will be in [0, num_new_variables).

Todo: (user): move in the context.

We copy the search strategy to the mapping_model.

Initialize the initial context.working_model domains.

If the objective is a floating point one, we scale it.

Todo: (user): We should probably try to delay this even more. For that we just need to isolate more the "dual" reduction that usually need to look at the objective.

At this point, we didn't create any new variables, so the integer objective is in term of the orinal problem variables. We save it so that we can expose to the user what exact objective we are actually optimizing.

Initialize the objective and the constraint <-> variable graph.

Note: we did some basic presolving during the first copy of the model. This is important has initializing the constraint <-> variable graph can be costly, so better to remove trivially feasible constraint for instance.

If presolve is false, just run expansion.

We still write back the canonical objective has we don't deal well with uninitialized domain or duplicate variables.

We need to append all the variable equivalence that are still used!

Make sure we also have an initialized mapping model as we use this for filling the tightened variables. Even without presolve, we do some trivial presolving during the initial copy of the model, and expansion might do more.

Presolve all variable domain once. The PresolveToFixPoint() function will only reprocess domain that changed.

Try to canonicalize the domain, note that we should have detected all affine relations before, so we don't recreate "canononical" variables if they already exist in the model.

Main propagation loop.

Todo: (user): The presolve transformations we do after this is called might result in even more presolve if we were to call this again! improve the code. See for instance plusexample_6_sat.fzn were represolving the presolved problem reduces it even more.

Call expansion.

Todo: (user): Make sure we can't have duplicate in these constraint. These are due to ExpandCpModel() were we create such constraint with duplicate. The problem is that some code assumes these are presolved before being called.

We need to re-evaluate the degree because some presolve rule only run after expansion.

We run the symmetry before more complex presolve rules as many of them are heuristic based and might break the symmetry present in the original problems. This happens for example on the flatzinc wordpress problem.

Todo: (user): Decide where is the best place for this.

Todo: (user): try not to break symmetry in our clique extension or other more advanced presolve rule? Ideally we could even exploit them. But in this case, it is still good to compute them early.

Runs SAT specific presolve on the pure-SAT part of the problem.

Note: because this can only remove/fix variable not used in the other part of the problem, there is no need to redo more presolve afterwards.

Extract redundant at most one constraint form the linear ones.

Todo: (user): more generally if we do some probing, the same relation will be detected (and more). Also add an option to turn this off?

Todo: (user): instead of extracting at most one, extract pairwise conflicts and add them to bool_and clauses? this is some sort of small scale probing, but good for sat presolve and clique later?

Deal with pair of constraints.

Todo: (user): revisit when different transformation appear.

Todo

Todo: (user): merge these code instead of doing many passes?

Heuristic: vertical introduce smaller defining constraint and appear in many constraints, so might be more constrained. We might also still make horizontal rectangle with the variable introduced.

We do that after the duplicate, SAT and SetPPC constraints.

Merge clauses that differ in just one literal. Heuristic use at_most_one to try to tighten the initial LP Relaxation.

The TransformIntoMaxCliques() call above transform all bool and into at most one of size 2. This does the reverse and merge them.

Call the main presolve to remove the fixed variables and do more deductions.

Exit the loop if no operations were performed.

Todo: (user): try to be smarter and avoid looping again if little changed.

Regroup no-overlaps into max-cliques.

Tries to spread the objective amongst many variables. We re-do a canonicalization with the final linear expression.

We re-do a canonicalization with the final linear expression.

Take care of linear constraint with a complex rhs.

Adds all needed affine relation to context_->working_model.

The strategy variable indices will be remapped in ApplyVariableMapping() but first we use the representative of the affine relations for the variables that are not present anymore.

Note: we properly take into account the sign of the coefficient which will result in the same domain reduction strategy. Moreover, if the variable order is not CHOOSE_FIRST, then we also encode the associated affine transformation in order to preserve the order.

Canonicalize each expression to use affine representative.

Remove fixed expression and affine corresponding to same variables.

Sync the domains and initialize the mapping model variables.

Remove all the unused variables from the presolved model.

Heuristic: If a variable is removed and has a representative that is not, we "move" the representative to the spot of that variable in the original order. This is to preserve any info encoded in the variable order by the modeler.

Deal with unused variables.

If the variable is not fixed, we have multiple feasible solution for this variable, so we can't remove it if we want all of them.

Tricky. Variables that where not removed by a presolve rule should be fixed first during postsolve, so that more complex postsolve rules can use their values. One way to do that is to fix them here.

We prefer to fix them to zero if possible.

Merge identical constant. Note that the only place were constant are still left are in the circuit and route constraint for fixed arcs.

The mapping might merge variable, so we have to be careful here.

Compact all non-empty constraint at the beginning.

Hack to display the number of deductions stored.

Stats and checks.

This is not supposed to happen, and is more indicative of an error than an INVALID model. But for our no-overflow preconditions, we might run into bad situation that causes the final model to be invalid.

Definition at line 12645 of file cp_model_presolve.cc.

◆ PresolveOneConstraint()

bool operations_research::sat::CpModelPresolver::PresolveOneConstraint ( int c )

Executes presolve method for the given constraint. Public for testing only.

Generic presolve to exploit variable/literal equivalence.

Generic presolve for reified constraint.

Call the presolve function for this constraint if any.

We first propagate the domains before calling this presolve rule.

There is no need to re-do a propagation here, but the constraint size might have been reduced.

If we extracted some enforcement, we redo some presolve.

Definition at line 8067 of file cp_model_presolve.cc.

◆ RemoveEmptyConstraints()

void operations_research::sat::CpModelPresolver::RemoveEmptyConstraints ( )

Public for testing only.

Remove all empty constraints and duplicated intervals. Note that we need to remap the interval references.

Now that they have served their purpose, we also remove dummy constraints, otherwise that causes issue because our model are invalid in tests.

Warning: interval_representative_ holds a pointer to the working model to compute hashes, so we need to be careful about not changing a constraint after its index is added to the map.

Definition at line 115 of file cp_model_presolve.cc.

The documentation for this class was generated from the following files:

ortools/sat/cp_model_presolve.h
ortools/sat/cp_model_presolve.cc