class Cbc::ConflictSolver

Public Class Methods

new(problem) click to toggle source
# File lib/ruby-cbc/conflict_solver.rb, line 3
def initialize(problem)
  # clone the model minus the objective
  @model = Model.new
  @model.vars = problem.model.vars
  @model.constraints = problem.model.constraints
  @problem = problem
end

Public Instance Methods

continuous_conflict?(crs) click to toggle source
# File lib/ruby-cbc/conflict_solver.rb, line 58
def continuous_conflict?(crs)
  problem = Problem.from_compressed_row_storage(crs, continuous: true)
  infeasible?(problem)
end
find_conflict() click to toggle source
# File lib/ruby-cbc/conflict_solver.rb, line 11
def find_conflict
  crs = Util::CompressedRowStorage.from_model(@model)
  continuous = continuous_conflict?(crs)
  unless continuous
    p = Problem.from_compressed_row_storage(crs, continuous: false)
    return [] unless infeasible?(p)
  end
  clusters = [crs.nb_constraints]
  max_iter = 1
  conflict_set_size = 0
  loop do
    range_idxs = first_failing(conflict_set_size, crs, continuous: continuous, max_iterations: max_iter)
    break if range_idxs.nil?
    crs = crs.restrict_to_n_constraints(range_idxs.max + 1)
    crs.move_constraint_to_start(range_idxs)
    clusters.insert(0, range_idxs.size)
    clusters[-1] = range_idxs.min - conflict_set_size
    conflict_set_size += range_idxs.size

    # Test conflict set
    crs2 = crs.restrict_to_n_constraints(conflict_set_size)
    problem = Problem.from_compressed_row_storage(crs2, continuous: continuous)
    if infeasible?(problem)
      clusters.delete_at(-1)
      break if clusters.size == conflict_set_size

      crs = crs2
    end

    nb_clusters_one_constraint = 0
    clusters.reverse_each do |nb_constraints|
      break if nb_constraints > 1
      nb_clusters_one_constraint += 1
    end
    if nb_clusters_one_constraint > 0
      crs.move_constraint_to_start((crs.nb_constraints - nb_clusters_one_constraint)..(crs.nb_constraints - 1))
      clusters[nb_clusters_one_constraint, clusters.size - nb_clusters_one_constraint] =
        clusters[0, clusters.size - nb_clusters_one_constraint]
      clusters[0, nb_clusters_one_constraint] = Array.new(nb_clusters_one_constraint, 1)
    end

    conflict_set_size = crs.nb_constraints - clusters[-1]
    # puts "CLUSTERS #{clusters.inspect}"
  end
  crs.model.constraints[0, conflict_set_size]
end

Private Instance Methods

first_failing(conflict_set_size, crs, continuous: false, max_iterations: nil) click to toggle source

finds the first constraint from constraints that makes the problem infeasible

# File lib/ruby-cbc/conflict_solver.rb, line 66
def first_failing(conflict_set_size, crs, continuous: false, max_iterations: nil)
  min_idx = conflict_set_size
  max_idx = crs.nb_constraints - 1

  loop do
    unless max_iterations.nil?
      return min_idx..max_idx if max_iterations <= 0
      max_iterations -= 1
    end
    half_constraint_idx = (max_idx + min_idx) / 2
    # puts "Refining: [#{min_idx}:#{max_idx}] -> #{half_constraint_idx}"
    crs2 = crs.restrict_to_n_constraints(half_constraint_idx + 1)
    problem = Problem.from_compressed_row_storage(crs2, continuous: continuous)
    if infeasible?(problem)
      max_idx = half_constraint_idx
      # puts "                                INFEAS"
    else
      min_idx = half_constraint_idx + 1
      # puts "                                FEAS"
    end
    if max_idx == min_idx
      # puts "found: max = #{max_idx} min = #{min_idx} nb = #{crs.nb_constraints}"
      return nil if max_idx > crs.nb_constraints
      return min_idx..max_idx
    end
  end
  # Shouldn't come here if the whole problem is infeasible
  return nil
end
infeasible?(problem) click to toggle source
# File lib/ruby-cbc/conflict_solver.rb, line 96
def infeasible?(problem)
  problem.solve
  problem.proven_infeasible?
end