Module: Relax4

Defined in:
lib/relax4.rb,
lib/relax4/version.rb

Overview

Methods for calling the RELAX IV solver.

There is a Ruby-friendly wrapper method called Relax4.solve.

There are also lower-level methods. Unfortunately, swig and rdoc don’t work very well together, so the best references for these calls are currently the source of Relax4.solve and the relax4.h header file listed below:

:include:../ext/relax4/relax4.h

Defined Under Namespace

Classes: InfeasibleError, IntegerArray

Constant Summary collapse

VERSION_MAJOR = 
1
VERSION_MINOR = 
2
VERSION_PATCH = 
0
VERSION = 
[VERSION_MAJOR, VERSION_MINOR, VERSION_PATCH].join('.')

Class Method Summary collapse

Class Method Details

.solve(args) ⇒ Array<Integer>

Solve a minimum cost network flow problem.

each arc, where the first node is numbered 1.

arc, where the first node is numbered 1.

allowed; negative cost cycles are allowed (edges involved in the cycle are set to large); all costs must be less than large and should be less than large/10 to avoid overflow (see RELAX4_DEFAULT_MAX_COST in relax4.h, above).

specified (problem is uncapacitated), all arc capacities are set to RELAX4_UNCAPACITATED; capacities must be in [0, large].

demand is a surplus node; demands should balance (sum to zero), or else the problem will be infeasible (but you can add a dummy node).

an initial feasible solution; this is recommended only for hard problems.

represent infinity; see the relax4.h listing above for more info.

cost, in order to avoid integer overflow; see the relax4.h listing above for more info.

Parameters:

  • args (Hash) —

    named arguments

Options Hash (args):

  • :start_nodes (Array<Integer>) —

    index of node at the start of

  • :end_nodes (Array<Integer>) —

    index of node at the end of each

  • :costs (Array<Integer>) —

    for each arc; negative costs are

  • :capacities (Array<Integer>) — default: nil —

    for each arc; if not

  • :demands (Array<Integer>) —

    for each node; a node with negative

  • :auction_init (Boolean) — default: false —

    use the auction routine to find

  • :large (Integer) — default: RELAX4_DEFAULT_LARGE —

    a very large integer to

  • :max_cost (Integer) — default: RELAX4_DEFAULT_MAX_COST —

    largest allowed

Returns:

  • (Array<Integer>) —

    optimal flows for each arc

Raises:

  • (ArgumentError) —

    if problem inputs are invalid

  • (InfeasibleError) —

    if problem is infeasible



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/relax4.rb', line 56

def self.solve args

  start_nodes = get_arg(args, :start_nodes)
  end_nodes   = get_arg(args, :end_nodes)
  costs       = get_arg(args, :costs)
  large       = args[:large] || RELAX4_DEFAULT_LARGE
  max_cost    = args[:max_cost] || RELAX4_DEFAULT_MAX_COST
  num_arcs    = start_nodes.size
  capacities  = args[:capacities] ||
    [[large, RELAX4_UNCAPACITATED].min]*num_arcs

  sizes = [start_nodes, end_nodes, costs, capacities].map{|a| a.size}
  raise ArgumentError.new("bad sizes for start/end_nodes, costs, capacities:"\
    " #{sizes.join(',')}") unless sizes.all? {|s| s == num_arcs}

  demands     = get_arg(args, :demands)
  num_nodes   = demands.size

  flows_ia = IntegerArray.new(num_arcs)
  case relax4_init(num_nodes, num_arcs,
                   IntegerArray.from_array(start_nodes),
                   IntegerArray.from_array(end_nodes),
                   IntegerArray.from_array(costs),
                   IntegerArray.from_array(capacities),
                   IntegerArray.from_array(demands),
                   flows_ia, large)
  when RELAX4_OK then
    # continue
  when RELAX4_FAIL_OUT_OF_MEMORY then
    raise "could not allocate enough memory in relax4_init"
  else
    raise "relax4_init_phase_1 failed with unrecognized code"
  end

  begin
    case relax4_check_inputs(max_cost)
    when RELAX4_OK then
      # continue
    when RELAX4_FAIL_BAD_SIZE then
      raise ArgumentError.new('problem has zero nodes or zero arcs')
    when RELAX4_FAIL_BAD_NODE then
      raise ArgumentError.new('start_nodes or end_nodes has a bad index')
    when RELAX4_FAIL_BAD_COST then
      raise ArgumentError.new("a cost exceeds the maximum (#{max_cost})")
    when RELAX4_FAIL_BAD_CAPACITY then
      raise ArgumentError.new("a capacity exceeds the maximum (#{large})")
    else
      raise "relax4_check_inputs failed with unrecognized code"
    end

    case relax4_init_phase_1()
    when RELAX4_OK then
      # continue
    when RELAX4_INFEASIBLE then
      raise InfeasibleError.new("infeasibility detected in phase 1 init")
    else
      raise "relax4_init_phase_1 failed with unrecognized code"
    end

    if args[:auction_init]
      case relax4_auction()
      when RELAX4_OK then
        # continue
      when RELAX4_INFEASIBLE then
        raise InfeasibleError.new("infeasibility detected in auction")
      else
        raise "relax4_auction failed with unrecognized code"
      end
    else
      case relax4_init_phase_2()
      when RELAX4_OK then
        # continue
      when RELAX4_INFEASIBLE then
        raise InfeasibleError.new("infeasibility detected in phase 2 init")
      else
        raise "relax4_init_phase_2 failed with unrecognized code"
      end
    end

    case relax4_run()
    when RELAX4_OK then
      # continue
    when RELAX4_INFEASIBLE then
      raise InfeasibleError.new("infeasibility detected in relax4_run")
    else
      raise "relax4_run failed with unrecognized code"
    end

    case relax4_check_output()
    when RELAX4_OK then
      # continue
    when RELAX4_OUTPUT_FAIL_NONZERO_DEMAND then
      raise "relax4 failed: output contains nonzero demands"
    when RELAX4_OUTPUT_FAIL_COMPLEMENTARY_SLACKNESS then
      raise "relax4 failed: output does not satisfy complementary slackness"
    else
      raise "relax4_check_output failed with unrecognized code"
    end 

    flows_ia.to_a!(num_arcs)
  ensure
    relax4_free()
  end
end

.solve_assignment_problem(args) ⇒ Array<Integer>

Solve a square assignment problem.

There are n agents and n tasks, and each agent must be assigned to exactly one task. The cost of each assignment is given, and the objective is to find the assignment with the lowest cost.

Some assignments can be made illegal by passing nil in the relevant entry in the cost matrix. If you have more agents than tasks (or vice versa), you can add some columns (or rows) of zeros to the cost matrix.

for each agent) and n columns (one for each task); a cost of nil means that the corresponding assignment is not allowed; negative costs are allowed.

Parameters:

  • args (Hash) —

    named arguments

Options Hash (args):

  • :costs (Array<Array<Integer>>) —

    square matrix with n rows (one

  • :auction_init (Boolean) —

    see solve

  • :large (Integer) —

    see solve

  • :max_cost (Integer) —

    see solve

Returns:

  • (Array<Integer>) —

    zero-based index of task assigned to each agent.

Raises:

  • (ArgumentError) —

    if problem inputs are invalid

  • (InfeasibleError) —

    if problem is infeasible



255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
 
# File 'lib/relax4.rb', line 255

def self.solve_assignment_problem args
  args  = args.dup
  costs = get_arg(args, :costs)

  n = costs.size

  arcs = set_args_from_cost_matrix(args, costs, n, n)
  args[:demands]     = [-1]*n + [1]*n

  arc_flows = Relax4.solve(args)

  # Find indexes.
  assignment = Array.new(n)
  arcs.zip(arc_flows).each do |(i,j),fij|
    assignment[i] = j if fij > 0
  end
  assignment
end

.solve_transportation_problem(args) ⇒ Array<Array<Integer>>

Solve a transportation problem.

There are m suppliers and n consumers of some commodity. Each supplier has a given supply which must be used, and each consumer has a given demand which must be satisfied; it is assumed that the total supply equals the total demand. The cost of transporting one unit of the commodity from each supplier to each consumer is given, and the objective is to perform the transport with minimum cost. The output is a m by n matrix that gives the flow from each supplier to each consumer.

each supplier) and n columns (one for each consumer); a cost of nil means that there is no corresponding edge (transport is impossible); negative costs are allowed; may be non-square but must be rectangular (all rows must have the same size).

demand should equal total supply, or else the problem will be infeasible (but you can add a dummy node to fix this).

demand should equal total supply, or else the problem will be infeasible (but you can add a dummy node to fix this).

consumer; size m by n; nil entries in the cost matrix will have flow 0 here.

Parameters:

  • args (Hash) —

    named arguments

Options Hash (args):

  • :costs (Array<Array<Integer>>) —

    matrix with m rows (one for

  • :supplies (Array<Integer>) —

    for each supplier; size m; total

  • :demands (Array<Integer>) —

    for each consumer; size n; total

  • :auction_init (Boolean) —

    see solve

  • :large (Integer) —

    see solve

  • :max_cost (Integer) —

    see solve

Returns:

  • (Array<Array<Integer>>) —

    optimal flows from each supplier to each

Raises:

  • (ArgumentError) —

    if problem inputs are invalid

  • (InfeasibleError) —

    if problem is infeasible



202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/relax4.rb', line 202

def self.solve_transportation_problem args
  args     = args.dup
  costs    = get_arg(args, :costs)
  supplies = get_arg(args, :supplies)
  demands  = get_arg(args, :demands)

  m = supplies.size
  n = demands.size

  arcs = set_args_from_cost_matrix(args, costs, m, n)
  args[:demands] = supplies.map{|x| -x} + demands

  arc_flows = Relax4.solve(args)

  # Extract output into matrix with same dims as input cost matrix.
  flows = Array.new(m) { Array.new(n, 0) }
  arcs.zip(arc_flows).each do |(i,j),fij|
    flows[i][j] = fij
  end
  flows
end