SolveState.hpp

Used as part of a branching solver to keep track of the current state.

Note

Status: BETA

class SolveState

#include <SolveState.hpp>

Often in a branch-and-bound algorithm, we need to identify the sub-set of items that maximizes (or minimizes) an optimization metric. SolveState keeps track of the current state for which items have been locked in as “included” in the current branks, which have been “excluded”, and which are still “unknown” (still to be decided upon.) All tracking is performed with BitVectors for high efficiency.

Public Functions

inline SolveState(size_t state_size = 0)

inline SolveState(const SolveState &in)

inline ~SolveState()

inline SolveState &operator=(const SolveState &in): Set this SolveState to be identical to another.

inline size_t GetSize() const: How many items are being considered in the current SolveState?

inline bool IsIn(size_t id) const: Test if a particular item is going to be included for sure in the current solve state. (If it has been excluded -OR- is yet to be decided upon, false will be returned)

inline bool IsUnk(size_t id) const: Test if a particular item is yet to be decided upon in the current solve state. (If it has been excluded -OR- is included for sure, false will be returned)

inline bool IsOut(size_t id) const: Test if a particular item is going to be excluded for sure in the current solve state. (If it has been included -OR- is yet to be decided upon, false will be returned)

inline bool IsFinal() const: Test if all items have been decided upon (none are still in the “unknown” state)

inline size_t CountIn() const: How many items have been included for sure?

inline size_t CountUnk() const: How many items have yet to be decided upon (are “unknown”)

inline size_t CountOut() const: How many items have been excluded for sure.

inline const BitVector &GetInVector() const: Get the BitVector associated with which items have been included for sure.

inline const BitVector &GetUnkVector() const: Get the BitVector associated with which items have yet to be decided upon.

inline BitVector GetOutVector() const: Get the BitVector associated with which iterm have been excluded for sure.

inline int GetNextUnk(size_t prev_unk) const: Get the ID of the next unknown item.

inline void Include(size_t id): Mark a specific item as to be included.

inline void Exclude(size_t id): Mark a specific item as to be excluded.

inline void ForceExclude(size_t id): Change our mind about a potentially included node (Be careful since many algorithms don’t requite this type of changes to be made.)

inline void IncludeSet(const BitVector &inc_set): Include ALL of the items specified in the provided BitVector.

inline void ExcludeSet(const BitVector &inc_set): Exclude ALL of the items specified in the provided BitVector.

Private Members

BitVector in_items: Items included for sure.

BitVector unk_items: Items yet to be decided on.