Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::math_opt::DualRay Struct Reference

#include <solution.h>

Public Member Functions

DualRayProto Proto () const
 Returns the proto equivalent of this.

Static Public Member Functions

static absl::StatusOr< DualRay > FromProto (ModelStorageCPtr model, const DualRayProto &dual_ray_proto)

Public Attributes

LinearConstraintMap< double > dual_values
VariableMap< double > reduced_costs

Detailed Description

A direction of unbounded improvement to the dual of an optimization problem; equivalently, a certificate of primal infeasibility.

E.g. consider the primal dual linear program pair: (Primal) (Dual) min c * x max b * y s.t. A * x >= b s.t. y * A + r = c x >= 0 y, r >= 0. The dual ray is the pair (y, r) satisfying: b * y > 0 y * A + r = 0 y, r >= 0 Observe that adding a positive multiple of (y, r) to dual feasible solution maintains dual feasibility and improves the objective (proving the dual is unbounded). The dual ray also proves the primal problem is infeasible.

In the class DualRay, y is dual_values and r is reduced_costs.

Definition at line 175 of file solution.h.

Member Function Documentation

◆ FromProto()

absl::StatusOr< DualRay > operations_research::math_opt::DualRay::FromProto ( ModelStorageCPtr model,
const DualRayProto & dual_ray_proto )
static

Returns the DualRay equivalent of dual_ray_proto.

Returns an error when either of:

  • VariableValuesFromProto(dual_ray_proto.reduced_costs) fails.
  • LinearConstraintValuesFromProto(dual_ray_proto.dual_values) fails.

Definition at line 163 of file solution.cc.

◆ Proto()

DualRayProto operations_research::math_opt::DualRay::Proto ( ) const

Returns the proto equivalent of this.

Definition at line 177 of file solution.cc.

Member Data Documentation

◆ dual_values

LinearConstraintMap<double> operations_research::math_opt::DualRay::dual_values

Definition at line 187 of file solution.h.

◆ reduced_costs

VariableMap<double> operations_research::math_opt::DualRay::reduced_costs

Definition at line 188 of file solution.h.

The documentation for this struct was generated from the following files: