operations_research::sat::MinPropagator Class Reference

#include <integer_expr.h>

Inheritance diagram for operations_research::sat::MinPropagator:

Public Member Functions
	MinPropagator (const std::vector< IntegerVariable > &vars, IntegerVariable min_var, IntegerTrail *integer_trail)
	MinPropagator (const MinPropagator &)=delete
	This type is neither copyable nor movable.
MinPropagator &	operator= (const MinPropagator &)=delete
bool	Propagate () final
void	RegisterWith (GenericLiteralWatcher *watcher)
Public Member Functions inherited from operations_research::sat::PropagatorInterface
	PropagatorInterface ()=default
virtual	~PropagatorInterface ()=default
virtual bool	IncrementalPropagate (const std::vector< int > &)

Detailed Description

A min (resp max) constraint of the form min == MIN(vars) can be decomposed into two inequalities: 1/ min <= MIN(vars), which is the same as for all v in vars, "min <= v". This can be taken care of by the LowerOrEqual(min, v) constraint. 2/ min >= MIN(vars).

And in turn, 2/ can be decomposed in: a) lb(min) >= lb(MIN(vars)) = MIN(lb(var)); b) ub(min) >= ub(MIN(vars)) and we can't propagate anything here unless there is just one possible variable 'v' that can be the min: for all u != v, lb(u) > ub(min); In this case, ub(min) >= ub(v).

This constraint take care of a) and b). That is:

• If the min of the lower bound of the vars increase, then the lower bound of the min_var will be >= to it.
• If there is only one candidate for the min, then if the ub(min) decrease, the ub of the only candidate will be <= to it.

Complexity: This is a basic implementation in O(num_vars) on each call to Propagate(), which will happen each time one or more variables in vars_ changed.

Todo

(user): Implement a more efficient algorithm when the need arise.

Definition at line 220 of file integer_expr.h.

Constructor & Destructor Documentation

MinPropagator() [1/2]

operations_research::sat::MinPropagator::MinPropagator	(	const std::vector< IntegerVariable > &	vars,
		IntegerVariable	min_var,
		IntegerTrail *	integer_trail )

Definition at line 556 of file integer_expr.cc.

MinPropagator() [2/2]

operations_research::sat::MinPropagator::MinPropagator ( const MinPropagator & )

delete

This type is neither copyable nor movable.

Member Function Documentation

operator=()

MinPropagator & operations_research::sat::MinPropagator::operator= ( const MinPropagator & )

delete

Propagate()

bool operations_research::sat::MinPropagator::Propagate ( )

finalvirtual

This will be called after one or more literals that are watched by this propagator changed. It will also always be called on the first propagation cycle after registration.

Count the number of interval that are possible candidate for the min. Only the intervals for which lb > current_min_ub cannot.

Propagation a)

Propagation b)

The reason is that all the other interval start after current_min_ub. And that min_ub has its current value.

Conflict.

Todo

(user): Not sure this code is useful since this will be detected by the fact that the [lb, ub] of the min is empty. It depends on the propagation order though, but probably the precedences propagator would propagate before this one. So change this to a CHECK?

Almost the same as propagation b).

Implements operations_research::sat::PropagatorInterface.

Definition at line 561 of file integer_expr.cc.

RegisterWith()

void operations_research::sat::MinPropagator::RegisterWith

(

GenericLiteralWatcher *

watcher

)

Definition at line 639 of file integer_expr.cc.

---

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

• ortools/sat/integer_expr.h
• ortools/sat/integer_expr.cc