solution.proto

Go to the documentation of this file.

// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
// The solution to an optimization model.
 
syntax = "proto3";
 
package operations_research.service.v1.mathopt;
 
import "ortools/service/v1/mathopt/sparse_containers.proto";
 
option java_multiple_files = true;
option java_package = "com.google.ortools.service.v1.mathopt";
option csharp_namespace = "Google.OrTools.Service";
 
// Feasibility of a primal or dual solution as claimed by the solver.
enum SolutionStatusProto {
  // Guard value representing no status.
  SOLUTION_STATUS_UNSPECIFIED = 0;
  // Solver does not claim a feasibility status.
  SOLUTION_STATUS_UNDETERMINED = 1;
  // Solver claims the solution is feasible.
  SOLUTION_STATUS_FEASIBLE = 2;
  // Solver claims the solution is infeasible.
  SOLUTION_STATUS_INFEASIBLE = 3;
}
 
// A solution to an optimization problem.
//
// E.g. consider a simple linear program:
//   min c * x
//   s.t. A * x >= b
//   x >= 0.
// A primal solution is assignment values to x. It is feasible if it satisfies
// A * x >= b and x >= 0 from above. In the message PrimalSolutionProto below,
// variable_values is x and objective_value is c * x.
message PrimalSolutionProto {
  // Requirements:
  //  * variable_values.ids are elements of VariablesProto.ids.
  //  * variable_values.values must all be finite.
  SparseDoubleVectorProto variable_values = 1;
 
  // Objective value as computed by the underlying solver. Cannot be infinite or
  // NaN.
  double objective_value = 2;
 
  // Auxiliary objective values as computed by the underlying solver. Keys must
  // be valid auxiliary objective IDs. Values cannot be infinite or NaN.
  map<int64, double> auxiliary_objective_values = 4;
 
  // Feasibility status of the solution according to the underlying solver.
  SolutionStatusProto feasibility_status = 3;
}
 
// A direction of unbounded improvement to an optimization problem;
// equivalently, a certificate of infeasibility for the dual of the
// optimization problem.
//
// E.g. consider a simple linear program:
//   min c * x
//   s.t. A * x >= b
//   x >= 0
// A primal ray is an x that satisfies:
//   c * x < 0
//   A * x >= 0
//   x >= 0
// Observe that given a feasible solution, any positive multiple of the primal
// ray plus that solution is still feasible, and gives a better objective
// value. A primal ray also proves the dual optimization problem infeasible.
//
// In the message PrimalRay below, variable_values is x.
message PrimalRayProto {
  // Requirements:
  //  * variable_values.ids are elements of VariablesProto.ids.
  //  * variable_values.values must all be finite.
  SparseDoubleVectorProto variable_values = 1;
 
  // TODO(b/185365397): indicate if the ray is feasible.
}
 
// A solution to the dual of an optimization problem.
//
// E.g. consider the primal dual pair 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 solution is the pair (y, r). It is feasible if it satisfies the
// constraints from (Dual) above.
//
// In the message below, y is dual_values, r is reduced_costs, and
// b * y is objective value.
message DualSolutionProto {
  // Requirements:
  //  * dual_values.ids are elements of LinearConstraints.ids.
  //  * dual_values.values must all be finite.
  SparseDoubleVectorProto dual_values = 1;
 
  // Requirements:
  //  * reduced_costs.ids are elements of VariablesProto.ids.
  //  * reduced_costs.values must all be finite.
  SparseDoubleVectorProto reduced_costs = 2;
 
  // TODO(b/195295177): consider making this non-optional
  // Objective value as computed by the underlying solver.
  optional double objective_value = 3;
 
  // Feasibility status of the solution according to the underlying solver.
  SolutionStatusProto feasibility_status = 4;
}
 
// A direction of unbounded improvement to the dual of an optimization,
// problem; equivalently, a certificate of primal infeasibility.
//
// E.g. consider the primal dual pair 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 message DualRay below, y is dual_values and r is reduced_costs.
message DualRayProto {
  // Requirements:
  //  * dual_values.ids are elements of LinearConstraints.ids.
  //  * dual_values.values must all be finite.
  SparseDoubleVectorProto dual_values = 1;
 
  // Requirements:
  //  * reduced_costs.ids are elements of VariablesProto.ids.
  //  * reduced_costs.values must all be finite.
  SparseDoubleVectorProto reduced_costs = 2;
 
  // TODO(b/185365397): indicate if the ray is feasible.
}
 
// Status of a variable/constraint in a LP basis.
enum BasisStatusProto {
  // Guard value representing no status.
  BASIS_STATUS_UNSPECIFIED = 0;
 
  // The variable/constraint is free (it has no finite bounds).
  BASIS_STATUS_FREE = 1;
 
  // The variable/constraint is at its lower bound (which must be finite).
  BASIS_STATUS_AT_LOWER_BOUND = 2;
 
  // The variable/constraint is at its upper bound (which must be finite).
  BASIS_STATUS_AT_UPPER_BOUND = 3;
 
  // The variable/constraint has identical finite lower and upper bounds.
  BASIS_STATUS_FIXED_VALUE = 4;
 
  // The variable/constraint is basic.
  BASIS_STATUS_BASIC = 5;
}
 
// A sparse representation of a vector of basis statuses.
message SparseBasisStatusVector {
  // Must be sorted (in increasing ordering) with all elements distinct.
  repeated int64 ids = 1;
 
  // Must have equal length to ids.
  repeated BasisStatusProto values = 2;
}
 
// A combinatorial characterization for a solution to a linear program.
//
// The simplex method for solving linear programs always returns a "basic
// feasible solution" which can be described combinatorially by a Basis. A basis
// assigns a BasisStatusProto for every variable and linear constraint.
//
// E.g. consider a standard form LP:
//   min c * x
//   s.t. A * x = b
//   x >= 0
// that has more variables than constraints and with full row rank A.
//
// Let n be the number of variables and m the number of linear constraints. A
// valid basis for this problem can be constructed as follows:
//  * All constraints will have basis status FIXED.
//  * Pick m variables such that the columns of A are linearly independent and
//    assign the status BASIC.
//  * Assign the status AT_LOWER for the remaining n - m variables.
//
// The basic solution for this basis is the unique solution of A * x = b that
// has all variables with status AT_LOWER fixed to their lower bounds (all
// zero). The resulting solution is called a basic feasible solution if it also
// satisfies x >= 0.
message BasisProto {
  // Constraint basis status.
  //
  // Requirements:
  //  * constraint_status.ids is equal to LinearConstraints.ids.
  SparseBasisStatusVector constraint_status = 1;
 
  // Variable basis status.
  //
  // Requirements:
  //  * constraint_status.ids is equal to VariablesProto.ids.
  SparseBasisStatusVector variable_status = 2;
 
  // This is an advanced feature used by MathOpt to characterize feasibility of
  // suboptimal LP solutions (optimal solutions will always have status
  // SOLUTION_STATUS_FEASIBLE).
  //
  // For single-sided LPs it should be equal to the feasibility status of the
  // associated dual solution. For two-sided LPs it may be different in some
  // edge cases (e.g. incomplete solves with primal simplex).
  //
  // If you are providing a starting basis via
  // ModelSolveParametersProto.initial_basis, this value is ignored. It is only
  // relevant for the basis returned by SolutionProto.basis.
  SolutionStatusProto basic_dual_feasibility = 3;
}
 
// What is included in a solution depends on the kind of problem and solver.
// The current common patterns are
//   1. MIP solvers return only a primal solution.
//   2. Simplex LP solvers often return a basis and the primal and dual
//      solutions associated to this basis.
//   3. Other continuous solvers often return a primal and dual solution
//      solution that are connected in a solver-dependent form.
//
// Requirements:
//  * at least one field must be set; a solution can't be empty.
message SolutionProto {
  optional PrimalSolutionProto primal_solution = 1;
  optional DualSolutionProto dual_solution = 2;
  optional BasisProto basis = 3;
}