Class: LpSolver::Model

Inherits:
Object
  • Object
show all
Defined in:
lib/lpsolver/model.rb

Overview

A high-level interface to HiGHS for building and solving LP/QP/MIP models.

The Model class provides a Ruby DSL for defining variables, constraints, and objectives. Models are serialized to HiGHS LP format and solved via the HiGHS command-line interface.

Problem Types Supported

  • **Linear Programming (LP)**: Linear objective with linear constraints. Example: maximize profit given resource constraints.

  • **Quadratic Programming (QP)**: Quadratic objective (convex) with linear constraints. Example: minimize portfolio variance for a target return.

  • **Mixed Integer Programming (MIP)**: LP or QP with some or all variables restricted to integer values. Example: coin change problem with integer counts.

Usage

The DSL uses Ruby operators to build expressions naturally:

model = LpSolver::Model.new
x = model.add_variable(:x, lb: 0)
y = model.add_variable(:y, lb: 0)

# Constraints
model.add_constraint(:budget, (x * 2 + y) <= 100)
model.add_constraint(:demand, (x + y * 2) >= 50)

# Objective
model.minimize
model.set_objective(x * 3 + y * 5)

# Solve
solution = model.solve
puts solution[:x]  # => optimal value for x

Examples:

Linear Programming

model = LpSolver::Model.new
x = model.add_variable(:x, lb: 0)
y = model.add_variable(:y, lb: 0)
model.add_constraint(:c1, (x + y) >= 4)
model.minimize
model.set_objective(x * 3 + y * 5)
solution = model.solve
solution.objective_value  # => 12.0

Quadratic Programming

model = LpSolver::Model.new
x = model.add_variable(:x, lb: 0)
y = model.add_variable(:y, lb: 0)
model.add_constraint(:c, (x + y) >= 2)
model.minimize
model.set_objective(x * x + y * y)
solution = model.solve
solution.objective_value  # => 2.0 (at x=1, y=1)

Mixed Integer Programming

model = LpSolver::Model.new
x = model.add_variable(:x, lb: 0, integer: true)
y = model.add_variable(:y, lb: 0, integer: true)
model.add_constraint(:c, (x + y) == 10)
model.minimize
model.set_objective(x * 2 + y * 3)
solution = model.solve
solution[:x]  # => 10.0 (integer)

Constant Summary collapse

HIGHS_PATH =

The path to the HiGHS binary.

Resolution order:

1. HIGHS_PATH environment variable
2. Bundled binary at lib/lpsolver/highs (from rake compile)
3. 'highs' on system PATH

Returns:

  • (String) —

    The path to the HiGHS executable.

begin
  env_path = ENV.fetch('HIGHS_PATH', nil)
  if env_path
    env_path
  else
    bundled = File.expand_path('../../lib/lpsolver/highs', __dir__)
    if File.exist?(bundled)
      bundled
    else
      'highs'
    end
  end
end

Instance Method Summary collapse

Constructor Details

#initialize(name = nil) ⇒ Model

Creates a new empty LP/QP/MIP model.

Parameters:

  • name (String) (defaults to: nil) —

    An optional name for this model, used for debugging and identification in logs. Defaults to ‘untitled’.



99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/lpsolver/model.rb', line 99

def initialize(name = nil)
  @name = name || 'untitled'
  @variables = {}       # { symbol => Variable }
  @constraints = {}     # { symbol => index }
  @var_counter = 0
  @constr_counter = 0
  @sense = :minimize
  @solution = nil
  @objective = {}       # { var_index => coefficient }
  @quadratic_terms = [] # [[var1_idx, var2_idx, coefficient], ...]
  @var_types = {}       # { symbol => :continuous | :integer }
  @var_bounds = {}      # { symbol => [lb, ub] }
  @constraints_data = {} # { symbol => { lb:, ub:, expr: [[var_idx, coeff], ...] } }
end

Instance Method Details

#add_constraint(name, expr, lb: -Float::INFINITY,, ub: Float::INFINITY) ⇒ Symbol

Adds a constraint to the model.

Constraints define the feasible region of the optimization problem. They can be specified using the DSL (comparison operators) or the legacy array format.

Examples:

Using DSL comparison operators

model.add_constraint(:budget, (x * 2 + y) <= 100)
model.add_constraint(:demand, (x + y * 2) >= 50)
model.add_constraint(:balance, (x + y) == 10)

Using legacy array format

model.add_constraint(:budget, [[x.index, 2], [y.index, 1]], ub: 100)

Parameters:

  • name (Symbol, String) —

    The name of the constraint.

  • expr (ConstraintSpec, Array<[Integer, Float]>) —

    The constraint specification. Can be either:

    • A ConstraintSpec from comparison operators: (x * 2 + y) <= 100

    • An array of [var_index, coefficient] pairs with explicit bounds

  • lb (Float) (defaults to: -Float::INFINITY,) —

    Lower bound for the constraint (used with array-style expr). Default: -Float::INFINITY.

  • ub (Float) (defaults to: Float::INFINITY) —

    Upper bound for the constraint (used with array-style expr). Default: Float::INFINITY.

Returns:

  • (Symbol) —

    The constraint name.



169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/lpsolver/model.rb', line 169

def add_constraint(name, expr, lb: -Float::INFINITY, ub: Float::INFINITY)
  name = name.to_sym

  if expr.is_a?(ConstraintSpec)
    lb_val, ub_val = expr.bounds
    data_expr = expr.expr
  else
    lb_val = lb
    ub_val = ub
    data_expr = expr
  end

  idx = @constr_counter
  @constraints[name] = idx
  @constraints_data[name] = {
    lb: normalize_bound(lb_val),
    ub: normalize_bound(ub_val),
    expr: data_expr
  }
  @constr_counter += 1
  name
end

#add_variable(name, lb: 0.0, ub: Float::INFINITY, integer: false) ⇒ Variable

Adds a variable to the model.

Variables represent the decision quantities to be determined by the solver. Each variable is assigned a unique internal index and can be used in expressions via arithmetic operators.

Examples:

Adding a continuous variable

x = model.add_variable(:x, lb: 0)

Adding an integer variable

count = model.add_variable(:count, lb: 0, integer: true)

Adding a fixed variable

capacity = model.add_variable(:capacity, lb: 100, ub: 100)

Parameters:

  • name (Symbol, String) —

    The name of the variable. This is used for identification in the LP format output and solution results.

  • lb (Float) (defaults to: 0.0) —

    The lower bound for the variable (default: 0.0). Use -Float::INFINITY for no lower bound.

  • ub (Float) (defaults to: Float::INFINITY) —

    The upper bound for the variable (default: Float::INFINITY). Use Float::INFINITY for no upper bound. Setting lb == ub fixes the variable.

  • integer (Boolean) (defaults to: false) —

    Whether the variable must take integer values (default: false). When true, the model becomes a MIP problem.

Returns:

  • (Variable) —

    The variable object, which supports arithmetic and comparison operators for building expressions and constraints.



136
137
138
139
140
141
142
143
144
145
 
# File 'lib/lpsolver/model.rb', line 136

def add_variable(name, lb: 0.0, ub: Float::INFINITY, integer: false)
  name = name.to_sym
  idx = @var_counter
  var = Variable.new(idx, name)
  @variables[name] = var
  @var_types[name] = integer ? :integer : :continuous
  @var_bounds[name] = [normalize_bound(lb), normalize_bound(ub)]
  @var_counter += 1
  var
end

#maximize ⇒ void

This method returns an undefined value.

Sets the optimization sense to maximization.

See Also:



204
205
206
 
# File 'lib/lpsolver/model.rb', line 204

def maximize
  @sense = :maximize
end

#maximize!(objective) ⇒ Solution

Sets the optimization sense to maximization, sets the objective, and solves the model in a single call.

This is a convenience method that combines #maximize, #set_objective, and #solve into one step.

Examples:

solution = model.maximize!(x * 3 + y * 5)
puts solution.objective_value  # => optimal (maximum) value

Parameters:

  • objective (LinearExpression, QuadraticExpression, Hash{Variable|Integer => Float}) —

    The objective function to maximize. Can be:

    • A LinearExpression: ‘x * 3 + y * 5`

    • A QuadraticExpression: ‘x * x + y * y + (x * y) * 2`

    • A Hash mapping variable indices to coefficients: ‘{ x.index => 3.0, y.index => 5.0 }`

Returns:

  • (Solution) —

    The solution object containing variable values, objective value, and model status.

Raises:

  • (SolverError) —

    If the HiGHS solver encounters an error.



325
326
327
328
329
 
# File 'lib/lpsolver/model.rb', line 325

def maximize!(objective)
  @sense = :maximize
  set_objective(objective)
  solve
end

#minimize ⇒ void

This method returns an undefined value.

Sets the optimization sense to minimization.

See Also:



196
197
198
 
# File 'lib/lpsolver/model.rb', line 196

def minimize
  @sense = :minimize
end

#minimize!(objective) ⇒ Solution

Sets the optimization sense to minimization, sets the objective, and solves the model in a single call.

This is a convenience method that combines #minimize, #set_objective, and #solve into one step.

Examples:

solution = model.minimize!(x * 3 + y * 5)
puts solution.objective_value  # => optimal (minimum) value

Quadratic minimization (QP)

solution = model.minimize!(x * x + y * y)

Parameters:

  • objective (LinearExpression, QuadraticExpression, Hash{Variable|Integer => Float}) —

    The objective function to minimize. Can be:

    • A LinearExpression: ‘x * 3 + y * 5`

    • A QuadraticExpression: ‘x * x + y * y + (x * y) * 2`

    • A Hash mapping variable indices to coefficients: ‘{ x.index => 3.0, y.index => 5.0 }`

Returns:

  • (Solution) —

    The solution object containing variable values, objective value, and model status.

Raises:

  • (SolverError) —

    If the HiGHS solver encounters an error.



302
303
304
305
306
 
# File 'lib/lpsolver/model.rb', line 302

def minimize!(objective)
  @sense = :minimize
  set_objective(objective)
  solve
end

#set_objective(objective) ⇒ void

This method returns an undefined value.

Sets the objective function for the model.

The objective function defines what the solver should optimize. It can be a linear expression (for LP), a quadratic expression (for QP), or a hash of coefficients (legacy format).

Examples:

Linear objective

model.set_objective(x * 3 + y * 5)

Quadratic objective (QP)

model.set_objective(x * x + y * y)

Parameters:

  • objective (LinearExpression, QuadraticExpression, Hash{Variable|Integer => Float}) —

    The objective function. Can be:

    • A LinearExpression: ‘x * 3 + y * 5`

    • A QuadraticExpression: ‘x * x + y * y + (x * y) * 2`

    • A Hash mapping variable indices to coefficients: ‘{ x.index => 3.0, y.index => 5.0 }`



224
225
226
227
228
229
230
231
232
233
234
235
 
# File 'lib/lpsolver/model.rb', line 224

def set_objective(objective)
  if objective.is_a?(QuadraticExpression)
    @objective = objective.linear_terms.transform_values(&:to_f)
    @quadratic_terms = objective.hessian_entries
  elsif objective.is_a?(LinearExpression)
    @objective = objective.terms.transform_values(&:to_f)
    @quadratic_terms = []
  else
    @objective = objective.transform_values { |v| v.is_a?(Variable) ? 1.0 : v.to_f }
    @quadratic_terms = []
  end
end

#solve ⇒ Solution

Solves the model and returns the solution.

Serializes the model to HiGHS LP format, invokes the HiGHS solver, and parses the solution file to return a Solution object.

Examples:

solution = model.solve
solution[:x]        # => optimal value for variable x
solution.objective_value  # => optimal objective value
solution.feasible?  # => true

Returns:

  • (Solution) —

    The solution object containing variable values, objective value, and model status.

Raises:

  • (SolverError) —

    If the HiGHS solver encounters an error.



250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
 
# File 'lib/lpsolver/model.rb', line 250

def solve
  lp_content = to_lp
  lp_file = Tempfile.new(['model', '.lp'])
  lp_file.write(lp_content)
  lp_file.close

  solution_file = Tempfile.new(['solution', '.sol'])
  opts_file = Tempfile.new(['highs_opts', '.txt'])
  opts_file.write("log_to_console = false\noutput_flag = false\n")
  opts_file.close

  cmd = "#{self.class::HIGHS_PATH} " \
        "--model_file #{lp_file.path} " \
        "--options_file #{opts_file.path} " \
        "--solution_file #{solution_file.path}"

  output = `#{cmd} 2>&1`
  lp_file.unlink
  opts_file.unlink

  # HiGHS returns non-zero exit code for infeasible/unbounded problems,
  # but still writes a valid solution file. Check for valid status instead.
  solution_content = File.read(solution_file.path)
  status_match = solution_content.match(/Model status\s*\n\s*(\S+)/i)
  unless status_match
    raise SolverError, "HiGHS solver failed:\n#{output}" unless $?.success?
  end

  @solution = parse_solution_file(solution_file.path)
  solution_file.unlink
  @solution
end

#to_lp ⇒ String

Converts the model to HiGHS LP format string.

The LP format is a text-based representation of the optimization problem that HiGHS can read. It includes the objective function, constraints, variable bounds, and integer declarations.

Examples:

puts model.to_lp
# Minimize
#  obj: 3 x + 5 y
# Subject To
#  budget: 2 x + 1 y <= 100
#  demand: 1 x + 2 y >= 50
# Bounds
#  0 <= x <= +Inf
#  0 <= y <= +Inf
# End

Returns:

  • (String) —

    The LP format content.



349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
 
# File 'lib/lpsolver/model.rb', line 349

def to_lp
  lines = []

  # Objective
  lines << (@sense == :minimize ? 'Minimize' : 'Maximize')

  obj_terms = @objective.map do |var_idx, coeff|
    var_name = find_var_name(var_idx)
    "#{format_coeff(coeff)} #{sanitize_name(var_name)}"
  end.join(' + ')

  if @quadratic_terms.any?
    quad_parts = @quadratic_terms.map do |i1, i2, coeff|
      n1 = sanitize_name(find_var_name(i1))
      n2 = sanitize_name(find_var_name(i2))
      if i1 == i2
        "#{format_coeff(coeff)} #{n1} ^ 2"
      else
        "#{format_coeff(coeff)} #{n1} * #{n2}"
      end
    end.join(' + ')
    lines << " obj: #{obj_terms} + [ #{quad_parts} ] / 2"
  else
    lines << " obj: #{obj_terms}"
  end

  # Constraints
  if @constraints.any?
    lines << 'Subject To'
    @constraints.each do |name, _idx|
      data = @constraints_data[name]
      terms = data[:expr].map do |var_idx, coeff|
        var_name = find_var_name(var_idx)
        "#{format_coeff(coeff)} #{sanitize_name(var_name)}"
      end.join(' + ')

      if data[:lb] == -Float::INFINITY && data[:ub] == Float::INFINITY
        lines << " #{sanitize_name(name)}: #{terms} free"
      elsif data[:lb] == -Float::INFINITY
        lines << " #{sanitize_name(name)}: #{terms} <= #{format_bound(data[:ub])}"
      elsif data[:ub] == Float::INFINITY
        lines << " #{sanitize_name(name)}: #{terms} >= #{format_bound(data[:lb])}"
      elsif (data[:ub] - data[:lb]).abs < 1e-12
        lines << " #{sanitize_name(name)}: #{terms} = #{format_bound(data[:lb])}"
      else
        lines << " #{sanitize_name(name)}: #{terms} >= #{format_bound(data[:lb])}"
        lines << " #{sanitize_name(name)}_ub: #{terms} <= #{format_bound(data[:ub])}"
      end
    end
  end

  # Bounds
  if @var_bounds.any?
    lines << 'Bounds'
    @variables.each do |name, _var|
      lb, ub = @var_bounds[name]
      sname = sanitize_name(name)

      if lb == ub
        lines << " #{sname} = #{format_bound(lb)}"
      elsif lb > -Float::INFINITY && ub < Float::INFINITY
        lines << " #{lb} <= #{sname} <= #{format_bound(ub)}"
      elsif lb > -Float::INFINITY
        lines << " #{sname} >= #{format_bound(lb)}"
      elsif ub < Float::INFINITY
        lines << " #{sname} <= #{format_bound(ub)}"
      end
    end
  end

  # Integer variables
  int_vars = @variables.select { |sym, _| @var_types[sym] == :integer }
  if int_vars.any?
    lines << 'Integers'
    int_vars.each { |name, _| lines << " #{sanitize_name(name)}" }
  end

  lines << 'End'
  lines.join("\n")
end

#variables ⇒ Hash{Symbol => Variable}

Returns all variables defined in this model.

Examples:

model.variables
# => { :x => @x(0), :y => @y(1) }

Returns:

  • (Hash{Symbol => Variable}) —

    Maps variable names (Symbols) to their Variable objects.



447
448
449
 
# File 'lib/lpsolver/model.rb', line 447

def variables
  @variables
end

#write_lp(filename) ⇒ void

This method returns an undefined value.

Writes the model to an LP file.

Examples:

model.write_lp('my_model.lp')

Parameters:

  • filename (String) —

    The output file path.



436
437
438
 
# File 'lib/lpsolver/model.rb', line 436

def write_lp(filename)
  File.write(filename, to_lp)
end