Skip to content
Permalink
554cbccaa9
Switch branches/tags
Go to file
 
 
Cannot retrieve contributors at this time
387 lines (334 sloc) 17.1 KB
// Copyright 2010-2018 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.
// Linear Programming Protocol Buffers.
//
// The protocol buffers below make it possible to store and transfer the
// representation of Linear and Mixed-Integer Programs.
//
// A Linear Program (LP) is a mathematical optimization model with a linear
// objective function, and linear equality and inequality constraints.
// The goal is to achieve the best outcome (such as maximum profit or lowest
// cost) by modeling the real-world problem at hand using linear functions.
// In a Mixed Integer Program (MIP), some variables may also be constrained to
// take integer values.
//
// Check ./linear_solver.h and Wikipedia for more detail:
// http://en.wikipedia.org/wiki/Linear_programming
//
syntax = "proto2";
option java_package = "com.google.ortools.linearsolver";
option java_multiple_files = true;
// import "google/protobuf/wrappers.proto";
import "ortools/util/optional_boolean.proto";
package operations_research;
// A variable is always constrained in the form:
// lower_bound <= x <= upper_bound
// where lower_bound and upper_bound:
// - Can form a singleton: x = constant = lower_bound = upper_bound.
// - Can form a finite interval: lower_bound <= x <= upper_bound. (x is boxed.)
// - Can form a semi-infinite interval.
// - lower_bound = -infinity: x <= upper_bound.
// - upper_bound = +infinity: x >= lower_bound.
// - Can form the infinite interval: lower_bound = -infinity and
// upper_bound = +infinity, x is free.
// MPVariableProto furthermore stores:
// - The coefficient of the variable in the objective.
// - Whether the variable is integer.
message MPVariableProto {
// lower_bound must be <= upper_bound.
optional double lower_bound = 1 [default = -inf];
optional double upper_bound = 2 [default = inf];
// The coefficient of the variable in the objective. Must be finite.
optional double objective_coefficient = 3 [default = 0.0];
// True if the variable is constrained to be integer.
// Ignored if MPModelProto::solver_type is *LINEAR_PROGRAMMING*.
optional bool is_integer = 4 [default = false];
// The name of the variable.
optional string name = 5 [default = ""];
}
// A linear constraint is always of the form:
// lower_bound <= sum of linear term elements <= upper_bound,
// where lower_bound and upper_bound:
// - Can form a singleton: lower_bound == upper_bound. The constraint is an
// equation.
// - Can form a finite interval [lower_bound, upper_bound]. The constraint is
// both lower- and upper-bounded, i.e. "boxed".
// - Can form a semi-infinite interval. lower_bound = -infinity: the constraint
// is upper-bounded. upper_bound = +infinity: the constraint is lower-bounded.
// - Can form the infinite interval: lower_bound = -infinity and
// upper_bound = +infinity. The constraint is free.
message MPConstraintProto {
// var_index[i] is the variable index (w.r.t. to "variable" field of
// MPModelProto) of the i-th linear term involved in this constraint, and
// coefficient[i] is its coefficient. Only the terms with non-zero
// coefficients need to appear. var_index may not contain duplicates.
repeated int32 var_index = 6 [packed = true];
repeated double coefficient = 7 [packed = true]; // Must be finite.
// lower_bound must be <= upper_bound.
optional double lower_bound = 2 [default = -inf];
optional double upper_bound = 3 [default = inf];
// The name of the constraint.
optional string name = 4 [default = ""];
// [Advanced usage: do not use this if you don't know what you're doing.]
// A lazy constraint is handled differently by the core solving engine, but
// it does not change the result. It may or may not impact the performance.
// For more info see: http://tinyurl.com/lazy-constraints.
optional bool is_lazy = 5 [default = false];
}
// This message encodes a partial (or full) assignment of the variables of a
// MPModelProto problem. The indices in var_index should be unique and valid
// variable indices of the associated problem.
message PartialVariableAssignment {
repeated int32 var_index = 1 [packed = true];
repeated double var_value = 2 [packed = true];
}
// MPModelProto contains all the information for a Linear Programming model.
message MPModelProto {
// True if the problem is a maximization problem. Minimize by default.
optional bool maximize = 1 [default = false];
// Offset for the objective function. Must be finite.
optional double objective_offset = 2 [default = 0.0];
// All the variables appearing in the model.
repeated MPVariableProto variable = 3;
// All the constraints appearing in the model.
repeated MPConstraintProto constraint = 4;
// Name of the model.
optional string name = 5 [default = ""];
// Solution hint.
//
// If a feasible or almost-feasible solution to the problem is already known,
// it may be helpful to pass it to the solver so that it can be used. A solver
// that supports this feature will try to use this information to create its
// initial feasible solution.
//
// Note that it may not always be faster to give a hint like this to the
// solver. There is also no guarantee that the solver will use this hint or
// try to return a solution "close" to this assignment in case of multiple
// optimal solutions.
optional PartialVariableAssignment solution_hint = 6;
}
// To support 'unspecified' double value in proto3, the simplest is to wrap
// any double value in a nested message (has_XXX works for message fields).
// We don't use google/protobuf/wrappers.proto because depending on it makes
// the following android integration test fail:
// http://sponge/c4bce1fd-41bd-4d0b-b4ca-fc04d4d64621
message OptionalDouble {
optional double value = 1;
}
// MPSolverCommonParameters holds advanced usage parameters that apply to any of
// the solvers we support.
// All of the fields in this proto can have a value of unspecified. In this
// case each inner solver will use their own safe defaults.
// Some values won't be supported by some solvers. The behavior in that case is
// not defined yet.
message MPSolverCommonParameters {
// Limit for relative MIP gap.
// If the relative MIP gap reaches this value or below, stop the solve before
// the time limit.
// The relative MIP gap is an upper bound of the relative distance to the
// optimal:
// for a maximization problem, it is defined as either
// (best_bound - objective) / abs(objective) (Gurobi)
// abs((best_bound - objective) / best_bound) (SCIP)
// where "objective" is the max objective of any solution found so far, and
// "best_bound" is the tightest (i.e. lowest) upper bound of the objective
// determined so far.
// The MIP Gap is sensitive to objective offset.
// If the denominator is 0 the MIP Gap is INFINITY for SCIP and Gurobi.
// Ask or-core-team@ for other solvers.
optional OptionalDouble relative_mip_gap = 1;
// Tolerance for primal feasibility of basic solutions: this is the maximum
// allowed error in constraint satisfiability.
// For SCIP this includes integrality constraints. For Gurobi it does not, you
// need to set the custom parameter IntFeasTol.
optional OptionalDouble primal_tolerance = 2;
// Tolerance for dual feasibility.
// For SCIP and Gurobi this is the feasibility tolerance for reduced costs in
// LP solution: reduced costs must all be smaller than this value in the
// improving direction in order for a model to be declared optimal.
// Not supported for other solvers.
optional OptionalDouble dual_tolerance = 3;
enum LPAlgorithmValues {
LP_ALGO_UNSPECIFIED = 0;
LP_ALGO_DUAL = 1; // Dual simplex.
LP_ALGO_PRIMAL = 2; // Primal simplex.
LP_ALGO_BARRIER = 3; // Barrier algorithm.
}
// Algorithm to solve linear programs.
// Ask or-core-team@ if you want to know what this does exactly.
optional LPAlgorithmValues lp_algorithm = 4 [default = LP_ALGO_UNSPECIFIED];
// Gurobi and SCIP enable presolve by default.
// Ask or-core-team@ for other solvers.
optional OptionalBoolean presolve = 5 [default = BOOL_UNSPECIFIED];
// Enable automatic scaling of matrix coefficients and objective. Available
// for Gurobi and GLOP.
// Ask or-core-team@ if you want more details.
optional OptionalBoolean scaling = 7 [default = BOOL_UNSPECIFIED];
}
message MPModelRequest {
// The model to be optimized by the server.
optional MPModelProto model = 1;
// The solver type, which will select a specific implementation, and will also
// impact the interpretation of the model (i.e. are we solving the problem
// as a mixed integer program or are we relaxing it as a continuous linear
// program?).
// This must remain consistent with MPSolver::OptimizationProblemType.
enum SolverType {
GLOP_LINEAR_PROGRAMMING = 2; // Recommended default for LP models.
CLP_LINEAR_PROGRAMMING = 0;
GLPK_LINEAR_PROGRAMMING = 1;
GUROBI_LINEAR_PROGRAMMING = 6; // Commercial, needs a valid license.
CPLEX_LINEAR_PROGRAMMING = 10; // Commercial, needs a valid license.
SCIP_MIXED_INTEGER_PROGRAMMING = 3; // Recommended default for MIP models.
GLPK_MIXED_INTEGER_PROGRAMMING = 4;
CBC_MIXED_INTEGER_PROGRAMMING = 5;
GUROBI_MIXED_INTEGER_PROGRAMMING = 7; // Commercial, needs a valid license.
CPLEX_MIXED_INTEGER_PROGRAMMING = 11; // Commercial, needs a valid license.
BOP_INTEGER_PROGRAMMING = 12;
// WARNING: This solver will currently interpret all variables as integer,
// so any solution you get will be valid, but the optimal might be far away
// for the real one (when you authorise non-integer value for continuous
// variables).
SAT_INTEGER_PROGRAMMING = 14;
KNAPSACK_MIXED_INTEGER_PROGRAMMING = 13;
}
optional SolverType solver_type = 2;
// Maximum time to be spent by the solver to solve 'model'. If the server is
// busy and the RPC's deadline_left is less than this, it will immediately
// give up and return an error, without even trying to solve.
//
// The client can use this to have a guarantee on how much time the
// solver will spend on the problem (unless it finds and proves
// an optimal solution more quickly).
//
// If not specified, the time limit on the solver is the RPC's deadline_left.
optional double solver_time_limit_seconds = 3;
// If this is set, then EnableOutput() will be set on the internal MPSolver
// that solves the model.
// WARNING: if you set this on a request to prod servers, it will be rejected
// and yield the RPC Application Error code MPSOLVER_SOLVER_TYPE_UNAVAILABLE.
optional bool enable_internal_solver_output = 4 [default = false];
// Advanced usage. Solver-specific parameters in the solver's own format,
// different for each solver. For example, if you use SCIP and you want to
// stop the solve earlier than the time limit if it reached a solution that is
// at most 1% away from the optimal, you can set this to "limits/gap=0.01".
//
// Note however that there is no "security" mechanism in place so it is up to
// the client to make sure that the given options don't make the solve
// non thread safe or use up too much memory for instance.
//
// If the option format is not understood by the solver, the request will be
// rejected and yield an RPC Application error with code
// MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS.
optional string solver_specific_parameters = 5;
}
// Status returned by the solver. They follow a hierarchical nomenclature, to
// allow us to add more enum values in the future. Clients should use
// InCategory() to match these enums, with the following C++ pseudo-code:
//
// bool InCategory(MPSolverResponseStatus status, MPSolverResponseStatus cat) {
// if (cat == MPSOLVER_OPTIMAL) return status == MPSOLVER_OPTIMAL;
// while (status > cat) status >>= 4;
// return status == cat;
// }
enum MPSolverResponseStatus {
// Normal responses -- the model was valid, and the solver ran.
// These statuses should be "somewhat" repeatable, modulo the fact that the
// solver's time limit makes it undeterministic, and could change a FEASIBLE
// model to an OPTIMAL and vice-versa (the others, except NOT_SOLVED, should
// normally be deterministic). Also, the solver libraries can be buggy.
// The solver found the proven optimal solution. This is what should be
// returned in most cases.
//
// WARNING: for historical reason, the value is zero, which means that this
// value can't have any subcategories.
MPSOLVER_OPTIMAL = 0x0;
// The solver had enough time to find some solution that satisfies all
// constraints, but it did not prove optimality (which means it may or may
// not have reached the optimal).
//
// This can happen for large LP models (Linear Programming), and is a frequent
// response for time-limited MIPs (Mixed Integer Programming). In the MIP
// case, the difference between the solution 'objective_value' and
// 'best_objective_bound' fields of the MPSolutionResponse will give an
// indication of how far this solution is from the optimal one.
MPSOLVER_FEASIBLE = 0x1;
// The model does not have any solution, according to the solver (which
// "proved" it, with the caveat that numerical proofs aren't actual proofs),
// or based on trivial considerations (eg. a variable whose lower bound is
// strictly greater than its upper bound).
MPSOLVER_INFEASIBLE = 0x2;
// There exist solutions that make the magnitude of the objective value
// as large as wanted (i.e. -infinity (resp. +infinity) for a minimization
// (resp. maximization) problem.
MPSOLVER_UNBOUNDED = 0x3;
// An error (most probably numerical) occurred.
// One likely cause for such errors is a large numerical range among variable
// coefficients (eg. 1e-16, 1e20), in which case one should try to shrink it.
MPSOLVER_ABNORMAL = 0x4;
// The solver did not have a chance to diagnose the model in one of the
// categories above.
MPSOLVER_NOT_SOLVED = 0x6;
// Like "NOT_SOLVED", but typically used by model validation functions
// returning a "model status", to enhance readability of the client code.
MPSOLVER_MODEL_IS_VALID = 0x61;
// Special value: the solver status could not be properly translated and is
// unknown.
MPSOLVER_UNKNOWN_STATUS = 0x63;
// Model errors. These are always deterministic and repeatable.
// They should be accompanied with a string description of the error.
MPSOLVER_MODEL_INVALID = 0x5;
// Something is wrong with the fields "solution_hint_var_index" and/or
// "solution_hint_var_value".
MPSOLVER_MODEL_INVALID_SOLUTION_HINT = 0x54;
// Something is wrong with the solver_specific_parameters request field.
MPSOLVER_MODEL_INVALID_SOLVER_PARAMETERS = 0x55;
// Implementation error: the requested solver implementation is not
// available (see MPModelRequest.solver_type).
// The linear solver binary was probably not linked with the required library,
// eg //ortools/linear_solver:linear_solver_scip for SCIP.
MPSOLVER_SOLVER_TYPE_UNAVAILABLE = 0x7;
};
message MPSolutionResponse {
// Result of the optimization.
optional /*required*/ MPSolverResponseStatus status = 1
[default = MPSOLVER_UNKNOWN_STATUS];
// Objective value corresponding to the "variable_value" below, taking into
// account the source "objective_offset" and "objective_coefficient".
// This is set iff 'status' is OPTIMAL or FEASIBLE.
optional double objective_value = 2;
// This field is only filled for MIP problems. For a minimization problem,
// this is a lower bound on the optimal objective value. For a maximization
// problem, it is an upper bound. It is only filled if the status is OPTIMAL
// or FEASIBLE. In the former case, best_objective_bound should be equal to
// objective_value (modulo numerical errors).
optional double best_objective_bound = 5;
// Variable values in the same order as the MPModelProto::variable field.
// This is a dense representation. These are set iff 'status' is OPTIMAL or
// FEASIBLE.
repeated double variable_value = 3 [packed = true];
// [Advanced usage.]
// Values of the dual variables values in the same order as the
// MPModelProto::constraint field. This is a dense representation.
// These are not set if the problem was solved with a MIP solver (even if
// it is actually a linear program).
// These are set iff 'status' is OPTIMAL or FEASIBLE.
repeated double dual_value = 4 [packed = true];
// [Advanced usage.]
// Values of the reduced cost of the variables in the same order as the
// MPModelProto::variable. This is a dense representation.
// These are not set if the problem was solved with a MIP solver (even if it
// is actually a linear program).
// These are set iff 'status' is OPTIMAL or FEASIBLE.
repeated double reduced_cost = 6 [packed = true];
}