rmwcs_solver: Generate a rmwcs solver

In mwcsr: Solvers for Maximum Weight Connected Subgraph Problem and Its Variants

Generate a rmwcs solver

Description

The method is based on relax-and-cut approach and allows to solve Maximum Weight Subgraph Probleam and its budget and cardinality variants. By constructing lagrangian relaxation of MWCS problem necessary graph connectivity constraints are introduced in the objective function giving upper bound on the weight of the optimal solution. On the other side, primal heuristic uses individul contribution of the variables to lagrangian relaxation to find possible solution of the initial problem. The relaxation is then optimized by using iterative subgradient method.

Usage

rmwcs_solver(
  timelimit = 1800L,
  max_iterations = 1000L,
  beta_iterations = 5L,
  separation = "strong",
  start_constraints = TRUE,
  pegging = TRUE,
  max_age = 10,
  sep_iterations = 10L,
  sep_iter_freeze = 50L,
  heur_iterations = 10L,
  subgradient = "classic",
  beta = 2,
  verbose = FALSE
)

Arguments

timelimit	Timelimit in seconds
max_iterations	Maximum number of iterations
beta_iterations	Number of nonimproving iterations until beta is halved
separation	Separation: "strong" or "fast"
start_constraints	Whether to add flow-conservation/degree constraints at start
pegging	variable fixing
max_age	number of iterations in aging procedure for non-violated cuts
sep_iterations	Frequency of separating cuts (in iterations)
sep_iter_freeze	Number of iterations when a newly separated cut is anaffected by subgradient algorithm.
heur_iterations	Frequency of calling heuristic method (in iterations)
subgradient	Subgradient: "classic", "average", "cft"
beta	Initial step size of subgradient algorithm
verbose	Should the solving progress and stats be printed?

Details

One iteration of algorithm includes solving lagrangian relaxation and updating lagrange multipliers. It may also contain cuts (or connectivity constraints) separation process, run of heuristic method, variable fixing routine. The initial step size for subgradient method can be passed as beta argument. If there is no improvement in upper bound in consequtive beta_iterations iterations the step size is halved. There are three possible strategies for updating multipliers. See the references section for the article where differences are discussed.

Some initial cuts are added at the start of the algorithm if start_constraints is set to TRUE. Other constraints are separated on the fly and are unaffected in the next sep_iter_freeze iterations of the subgradient mehod. Then the corresponding lagrange mutipliers are updated from iteration to iteration. Aging procedure for cuts is incorporated in the algorithm meaning constraint multipliers are updated for non-violated cuts for up to max_age iterations from the point where a cut was violated last time. There are two separation methods implemented: fast and strong, where tha latter is supposed to minimize number of variables used in generated constraint while in the former case there is no need to explore whole graph to construct a constraint.

A variant of MST approximation of PCSTP is used as Primal Heuristic. See references for more details.

The frequences of running separation process and heuristic are specified in sep_iterations and heur_iterations.

Value

An object of class mwcs_solver.

References

Álvarez-Miranda E., Sinnl M. (2017) "A Relax-and-Cut framework for large-scale maximum weight connected subgraph problems" \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1016/j.cor.2017.05.015")}

mwcsr documentation built on May 31, 2023, 8:41 p.m.