SolveState.hpp

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

Note

Status: BETA

Defines

INCLUDE_EMP_TOOLS_SOLVE_STATE_HPP_GUARD

class SolveState

#include <SolveState.hpp>

Often in branch-and-bound algorithms, we must identify the sub-set of items that maximizes (or minimizes) an optimization metric. SolveState tracks the current state for which items have been “included” in a prospective solution, which have been “excluded”, and which are still “unknown” (yet be decided upon.)

Public Functions

inline SolveState(size_t state_size = 0)

SolveState(const SolveState&) = default

SolveState(SolveState&&) = default

inline ~SolveState()

SolveState &operator=(const SolveState&) = default

SolveState &operator=(SolveState&&) = default

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

inline void Reset()

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 items have been excluded for sure.

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

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

inline void Include(size_t id): Mark a specific item as to be included; okay if it was previously excluded.

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 expect this type of change 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.