Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
capacity.proto
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14syntax = "proto3";
15
16package operations_research;
17
18option java_package = "com.google.ortools.setcover";
19option java_multiple_files = true;
20
21// Represents a capacity constraint to be used in conjunction with a
22// SetCoverProto. This constraint only considers one dimension.
23//
24// Such a capacity constraint mathematically looks like:
25// min_capacity <= \sum_{e in elements} weight_e * x_e <= max_capacity
26// where either `min_capacity` or `max_capacity` can be omitted. `x_e` indicates
27// for a given solution `x` whether the element `e` is selected and counts for
28// this capacity constraint (`x_e == 1`) or not (`x_e == 0`). The weights are
29// given in `capacity_term`, each of them being a reference to an element being
30// present in a subset (in set-covering parlance) and its weight.
31//
32// For instance, this constraint can be used together with a set-covering
33// problem where parcels (element) must be covered by trucks (subsets) while
34// respecting truck capacities (this object). Each element can be covered by a
35// given set of trucks (set-covering problem); if an element is taken within a
36// truck, it uses some capacity for this truck (such as weight).
37//
38// In particular, this representation does not imply that a given element must
39// have the same weight in all the capacity constraints of a set-covering
40// problem (e.g., the same parcel might have different weights depending on
41// which truck is being considered).
42message CapacityConstraintProto {
43 message CapacityTerm {
44 // The subset this weight corresponds to (index of the subset in the
45 // `subset` repeated field in `SetCoverProto`).
46 int64 subset = 1;
47
48 message ElementWeightPair {
49 // The element this weight corresponds to (value of `element` in
50 // `SetCoverProto.Subset`).
51 int64 element = 1;
52
53 // The weight of the element.
54 int64 weight = 2;
55 }
56
57 repeated ElementWeightPair element_weights = 2;
58 }
59
60 // The list of terms in the constraint.
61 //
62 // The list is supposed to be in canonical form, which means it is sorted
63 // first by increasing subset index then increasing element index.
64 // No duplicate term is allowed (two terms for the same element in the same
65 // subset).
66 repeated CapacityTerm capacity_term = 1;
67
68 // The minimum amount of resource that must be consumed. At least one of
69 // `min_capacity` and `max_capacity` must be present.
70 int64 min_capacity = 2;
71
72 // The maximum amount of resource that can be consumed. At least one of
73 // `min_capacity` and `max_capacity` must be present.
74 int64 max_capacity = 3;
75}