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.

Set via the HIGHS_PATH environment variable, or defaults to ‘highs’ on the system PATH. This is used to invoke the HiGHS solver via the command line.

Returns:

  • (String) —

    The path to the HiGHS executable.

ENV.fetch('HIGHS_PATH', 'highs')

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’.



86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/lpsolver/model.rb', line 86

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.



156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
 
# File 'lib/lpsolver/model.rb', line 156

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.



123
124
125
126
127
128
129
130
131
132
 
# File 'lib/lpsolver/model.rb', line 123

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:



191
192
193
 
# File 'lib/lpsolver/model.rb', line 191

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.



308
309
310
311
312
 
# File 'lib/lpsolver/model.rb', line 308

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:



183
184
185
 
# File 'lib/lpsolver/model.rb', line 183

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.



285
286
287
288
289
 
# File 'lib/lpsolver/model.rb', line 285

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 }`



211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/lpsolver/model.rb', line 211

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.



237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
 
# File 'lib/lpsolver/model.rb', line 237

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`
  status = $?.success?

  lp_file.unlink
  opts_file.unlink

  raise SolverError, "HiGHS solver failed:\n#{output}" unless status

  @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.



332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
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
 
# File 'lib/lpsolver/model.rb', line 332

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

#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.



419
420
421
 
# File 'lib/lpsolver/model.rb', line 419

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