Google OR-Tools v9.12
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Public Member Functions | Static Public Attributes | Properties | List of all members
Google.OrTools.Sat.RoutesConstraintProto Class Referencesealed

The "VRP" (Vehicle Routing Problem) constraint. More...

Inheritance diagram for Google.OrTools.Sat.RoutesConstraintProto:

Public Member Functions

 RoutesConstraintProto ()
 
 RoutesConstraintProto (RoutesConstraintProto other)
 
RoutesConstraintProto Clone ()
 
override bool Equals (object other)
 
bool Equals (RoutesConstraintProto other)
 
override int GetHashCode ()
 
override string ToString ()
 
void WriteTo (pb::CodedOutputStream output)
 
int CalculateSize ()
 
void MergeFrom (RoutesConstraintProto other)
 
void MergeFrom (pb::CodedInputStream input)
 

Static Public Attributes

const int TailsFieldNumber = 1
 Field number for the "tails" field.
 
const int HeadsFieldNumber = 2
 Field number for the "heads" field.
 
const int LiteralsFieldNumber = 3
 Field number for the "literals" field.
 
const int DemandsFieldNumber = 4
 Field number for the "demands" field.
 
const int CapacityFieldNumber = 5
 Field number for the "capacity" field.
 

Properties

static pb::MessageParser< RoutesConstraintProto > Parser [get]
 
static pbr::MessageDescriptor Descriptor [get]
 
pbc::RepeatedField< int > Tails [get]
 
pbc::RepeatedField< int > Heads [get]
 
pbc::RepeatedField< int > Literals [get]
 
pbc::RepeatedField< int > Demands [get]
 EXPERIMENTAL. The demands for each node, and the maximum capacity for each route. Note that this is currently only used for the LP relaxation and one need to add the corresponding constraint to enforce this outside of the LP.
 
long Capacity [get, set]
 

Detailed Description

The "VRP" (Vehicle Routing Problem) constraint.

The direct graph where arc #i (from tails[i] to head[i]) is present iff literals[i] is true must satisfy this set of properties:

  • #incoming arcs == 1 except for node 0.
  • #outgoing arcs == 1 except for node 0.
  • for node zero, #incoming arcs == #outgoing arcs.
  • There are no duplicate arcs.
  • Self-arcs are allowed except for node 0.
  • There is no cycle in this graph, except through node 0.
    Note
    Currently this constraint expect all the nodes in [0, num_nodes) to have at least one incident arc. The model will be considered invalid if it is not the case. You can add self-arc fixed to one to ignore some nodes if needed.
    Todo
    (user): It is probably possible to generalize this constraint to a no-cycle in a general graph, or a no-cycle with sum incoming <= 1 and sum outgoing <= 1 (more efficient implementation). On the other hand, having this specific constraint allow us to add specific "cuts" to a VRP problem.

Definition at line 3705 of file CpModel.pb.cs.

Constructor & Destructor Documentation

◆ RoutesConstraintProto() [1/2]

Google.OrTools.Sat.RoutesConstraintProto.RoutesConstraintProto ( )
inline

Definition at line 3730 of file CpModel.pb.cs.

◆ RoutesConstraintProto() [2/2]

Google.OrTools.Sat.RoutesConstraintProto.RoutesConstraintProto ( RoutesConstraintProto other)
inline

Definition at line 3738 of file CpModel.pb.cs.

Member Function Documentation

◆ CalculateSize()

int Google.OrTools.Sat.RoutesConstraintProto.CalculateSize ( )
inline

Definition at line 3905 of file CpModel.pb.cs.

◆ Clone()

RoutesConstraintProto Google.OrTools.Sat.RoutesConstraintProto.Clone ( )
inline

Definition at line 3749 of file CpModel.pb.cs.

◆ Equals() [1/2]

override bool Google.OrTools.Sat.RoutesConstraintProto.Equals ( object other)
inline

Definition at line 3823 of file CpModel.pb.cs.

◆ Equals() [2/2]

bool Google.OrTools.Sat.RoutesConstraintProto.Equals ( RoutesConstraintProto other)
inline

Definition at line 3829 of file CpModel.pb.cs.

◆ GetHashCode()

override int Google.OrTools.Sat.RoutesConstraintProto.GetHashCode ( )
inline

Definition at line 3846 of file CpModel.pb.cs.

◆ MergeFrom() [1/2]

void Google.OrTools.Sat.RoutesConstraintProto.MergeFrom ( pb.CodedInputStream input)
inline

Definition at line 3938 of file CpModel.pb.cs.

◆ MergeFrom() [2/2]

void Google.OrTools.Sat.RoutesConstraintProto.MergeFrom ( RoutesConstraintProto other)
inline

Definition at line 3922 of file CpModel.pb.cs.

◆ ToString()

override string Google.OrTools.Sat.RoutesConstraintProto.ToString ( )
inline

Definition at line 3861 of file CpModel.pb.cs.

◆ WriteTo()

void Google.OrTools.Sat.RoutesConstraintProto.WriteTo ( pb.CodedOutputStream output)
inline

Definition at line 3867 of file CpModel.pb.cs.

Member Data Documentation

◆ CapacityFieldNumber

const int Google.OrTools.Sat.RoutesConstraintProto.CapacityFieldNumber = 5
static

Field number for the "capacity" field.

Definition at line 3810 of file CpModel.pb.cs.

◆ DemandsFieldNumber

const int Google.OrTools.Sat.RoutesConstraintProto.DemandsFieldNumber = 4
static

Field number for the "demands" field.

Definition at line 3787 of file CpModel.pb.cs.

◆ HeadsFieldNumber

const int Google.OrTools.Sat.RoutesConstraintProto.HeadsFieldNumber = 2
static

Field number for the "heads" field.

Definition at line 3765 of file CpModel.pb.cs.

◆ LiteralsFieldNumber

const int Google.OrTools.Sat.RoutesConstraintProto.LiteralsFieldNumber = 3
static

Field number for the "literals" field.

Definition at line 3776 of file CpModel.pb.cs.

◆ TailsFieldNumber

const int Google.OrTools.Sat.RoutesConstraintProto.TailsFieldNumber = 1
static

Field number for the "tails" field.

Definition at line 3754 of file CpModel.pb.cs.

Property Documentation

◆ Capacity

long Google.OrTools.Sat.RoutesConstraintProto.Capacity
getset

Definition at line 3814 of file CpModel.pb.cs.

◆ Demands

pbc.RepeatedField<int> Google.OrTools.Sat.RoutesConstraintProto.Demands
get

EXPERIMENTAL. The demands for each node, and the maximum capacity for each route. Note that this is currently only used for the LP relaxation and one need to add the corresponding constraint to enforce this outside of the LP.

Todo
(user): Ideally, we should be able to extract any dimension like these (i.e. capacity, route_length, etc..) automatically from the encoding. The classical way to encode that is to have "current_capacity" variables along the route and linear equations of the form: arc_literal => (current_capacity_tail + demand <= current_capacity_head)

Definition at line 3805 of file CpModel.pb.cs.

◆ Descriptor

pbr.MessageDescriptor Google.OrTools.Sat.RoutesConstraintProto.Descriptor
staticget

Definition at line 3718 of file CpModel.pb.cs.

◆ Heads

pbc.RepeatedField<int> Google.OrTools.Sat.RoutesConstraintProto.Heads
get

Definition at line 3771 of file CpModel.pb.cs.

◆ Literals

pbc.RepeatedField<int> Google.OrTools.Sat.RoutesConstraintProto.Literals
get

Definition at line 3782 of file CpModel.pb.cs.

◆ Parser

pb.MessageParser<RoutesConstraintProto> Google.OrTools.Sat.RoutesConstraintProto.Parser
staticget

Definition at line 3714 of file CpModel.pb.cs.

◆ Tails

pbc.RepeatedField<int> Google.OrTools.Sat.RoutesConstraintProto.Tails
get

Definition at line 3760 of file CpModel.pb.cs.

The documentation for this class was generated from the following file: