Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | List of all members
operations_research::SetCoverMip Class Reference

#include <set_cover_mip.h>

Public Member Functions

 SetCoverMip (SetCoverInvariant *inv)
 Simpler constructor that uses SCIP by default.
 
 SetCoverMip (SetCoverInvariant *inv, SetCoverMipSolver mip_solver)
 
bool NextSolution (bool use_integers, double time_limit_in_seconds)
 
bool NextSolution (absl::Span< const SubsetIndex > focus, bool use_integers, double time_limit_in_seconds)
 
double lower_bound () const
 Returns the lower bound of the linear relaxation of the problem.
 

Detailed Description

Definition at line 30 of file set_cover_mip.h.

Constructor & Destructor Documentation

◆ SetCoverMip() [1/2]

operations_research::SetCoverMip::SetCoverMip ( SetCoverInvariant * inv)
inlineexplicit

Simpler constructor that uses SCIP by default.

Definition at line 33 of file set_cover_mip.h.

◆ SetCoverMip() [2/2]

operations_research::SetCoverMip::SetCoverMip ( SetCoverInvariant * inv,
SetCoverMipSolver mip_solver )
inline

The constructor takes a SetCoverInvariant that will store the resulting variable choices, and a MIP Solver.

Definition at line 38 of file set_cover_mip.h.

Member Function Documentation

◆ lower_bound()

double operations_research::SetCoverMip::lower_bound ( ) const
inline

Returns the lower bound of the linear relaxation of the problem.

Definition at line 55 of file set_cover_mip.h.

◆ NextSolution() [1/2]

bool operations_research::SetCoverMip::NextSolution ( absl::Span< const SubsetIndex > focus,
bool use_integers,
double time_limit_in_seconds )

Computes the next partial solution considering only the subsets whose indices are in focus.

We are using MPSolver, which is deprecated, because MathOpt does not provide an interface without using protobufs. We construct a restricted MIP, omitting all the parts of the problem that are already fixed in the invariant. The goal is to not spend time sending data, and having the MIP solver re-discover fixed variables.

The model should only contain elements that are not forcibly covered by subsets outside the focus.

set_time_limit takes milliseconds as a unit.

Call the solver.

Definition at line 51 of file set_cover_mip.cc.

◆ NextSolution() [2/2]

bool operations_research::SetCoverMip::NextSolution ( bool use_integers,
double time_limit_in_seconds )

Returns true if a solution was found. If use_integers is false, lower_bound_ is populated with a linear lower bound. time_limit_in_seconds is a (rather soft) time limit for the execution time.

Todo
(user): Add time-outs and exit with a partial solution. This seems unlikely, though.

Definition at line 45 of file set_cover_mip.cc.

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