or-tools/examples/cpp/network_routing.cc File Reference

#include "base/hash.h"
#include <string>
#include <utility>
#include <vector>
#include "base/callback.h"
#include "base/commandlineflags.h"
#include "base/integral_types.h"
#include "base/logging.h"
#include "base/scoped_ptr.h"
#include "base/stringprintf.h"
#include "base/concise_iterator.h"
#include "base/map-util.h"
#include "constraint_solver/constraint_solveri.h"
#include "graph/shortestpaths.h"
#include "util/tuple_set.h"
#include "base/random.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Classes
class	operations_research::NetworkRoutingData
	Data Contains problem data. More...
class	operations_research::NetworkRoutingDataBuilder
	Data Generation. More...
struct	operations_research::Demand
	Solving the Problem. More...
class	operations_research::NetworkRoutingSolver
class	operations_research::NetworkRoutingSolver::PathBasedLns
	Implement 'clever' Large Neighborhood Search. More...
struct	operations_research::NetworkRoutingSolver::PathBasedLns::ArcWrapper
class	operations_research::NetworkRoutingSolver::ApplyMaxDiscrepancy
class	operations_research::NetworkRoutingSolver::StoreUsageCosts
	Auxilliary Decision Builder to Store the Cost of a Solution. More...
Functions
	DEFINE_int32 (clients, 0,"Number of network clients nodes. If equal to zero, ""then all backbones nodes are also client nodes.")
	Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.
	DEFINE_int32 (backbones, 0,"Number of backbone nodes")
	DEFINE_int32 (demands, 0,"Number of network demands.")
	DEFINE_int32 (traffic_min, 0,"Min traffic of a demand.")
	DEFINE_int32 (traffic_max, 0,"Max traffic of a demand.")
	DEFINE_int32 (min_client_degree, 0,"Min number of connections from a client to the backbone.")
	DEFINE_int32 (max_client_degree, 0,"Max number of connections from a client to the backbone.")
	DEFINE_int32 (min_backbone_degree, 0,"Min number of connections from a backbone node to the rest of ""the backbone nodes.")
	DEFINE_int32 (max_backbone_degree, 0,"Max number of connections from a backbone node to the rest of ""the backbone nodes.")
	DEFINE_int32 (max_capacity, 0,"Max traffic on any arc.")
	DEFINE_int32 (fixed_charge_cost, 0,"Fixed charged cost when using an arc.")
	DEFINE_int32 (seed, 0,"Random seed")
	DEFINE_bool (print_model, false,"Print model.")
	Reporting.
	DEFINE_int32 (report, 1,"Report which links and which demands are ""responsible for the congestion.")
	DEFINE_int32 (log_period, 100000,"Period for the search log")
	DEFINE_int64 (comfort_zone, 850,"Above this limit in 1/1000th, the link is said to be ""congestioned.")
	CP Model.
	DEFINE_int32 (extra_hops, 6,"When creating all paths for a demand, we look at paths with ""maximum length 'shortest path + extra_hops'")
	DEFINE_int32 (max_paths, 1200,"Max number of possible paths for a demand.")
	DEFINE_int32 (time_limit, 60000,"Time limit for search in ms, 0 = no time limit.")
	CP LNS.
	DEFINE_int32 (fail_limit, 0,"Failure limit for search, 0 = no limit.")
	DEFINE_int32 (lns_size, 6,"Number of vars to relax in a lns loop.")
	DEFINE_int32 (lns_seed, 1,"Seed for the LNS random number generator.")
	DEFINE_int32 (lns_limit, 30,"Limit the number of failures of the lns loop.")
	DEFINE_bool (focus_lns, true,"Focus LNS on highest cost arcs.")
int	main (int argc, char **argv)
	namespace operations_research
Variables
static const int64	operations_research::kDisconnectedDistance = -1LL
	Data and Data Generation.

---

Function Documentation

DEFINE_bool	(	focus_lns	,
		true	,
		"Focus LNS on highest cost arcs."
	)

DEFINE_bool	(	print_model	,
		false	,
		"Print model."
	)

Reporting.

DEFINE_int32	(	lns_limit	,
		30	,
		"Limit the number of failures of the lns loop."
	)

DEFINE_int32	(	lns_seed	,
		1	,
		"Seed for the LNS random number generator."
	)

DEFINE_int32	(	lns_size	,
		6	,
		"Number of vars to relax in a lns loop."
	)

DEFINE_int32	(	fail_limit	,
		0	,
		"Failure limit for	search
	)

DEFINE_int32	(	time_limit	,
		60000	,
		"Time limit for search in	ms
	)

CP LNS.

DEFINE_int32	(	max_paths	,
		1200	,
		"Max number of possible paths for a demand."
	)

DEFINE_int32	(	extra_hops	,
		6	,
		"When creating all paths for a	demand,
		we look at paths with""maximum length 'shortest path+extra_hops'"
	)

DEFINE_int32	(	log_period	,
		100000	,
		"Period for the search log"
	)

DEFINE_int32	(	report	,
		1	,
		"Report which links and which demands are ""responsible for the congestion."
	)

DEFINE_int32	(	seed	,
		0	,
		"Random seed"
	)

DEFINE_int32	(	fixed_charge_cost	,
		0	,
		"Fixed charged cost when using an arc."
	)

DEFINE_int32	(	max_capacity	,
		0	,
		"Max traffic on any arc."
	)

DEFINE_int32	(	max_backbone_degree	,
		0	,
		"Max number of connections from a backbone node to the rest of ""the backbone nodes."
	)

DEFINE_int32	(	min_backbone_degree	,
		0	,
		"Min number of connections from a backbone node to the rest of ""the backbone nodes."
	)

DEFINE_int32	(	max_client_degree	,
		0	,
		"Max number of connections from a client to the backbone."
	)

DEFINE_int32	(	min_client_degree	,
		0	,
		"Min number of connections from a client to the backbone."
	)

DEFINE_int32	(	traffic_max	,
		0	,
		"Max traffic of a demand."
	)

DEFINE_int32	(	traffic_min	,
		0	,
		"Min traffic of a demand."
	)

DEFINE_int32	(	demands	,
		0	,
		"Number of network demands."
	)

DEFINE_int32	(	backbones	,
		0	,
		"Number of backbone nodes"
	)

DEFINE_int32	(	clients	,
		0	,
		"Number of network clients nodes. If equal to	zero,
		""then all backbones nodes are also client nodes."
	)

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. This model solves a multicommodity mono-routing problem with capacity constraints and a max usage cost structure. This means that given a graph with capacity on edges, and a set of demands (source, destination, traffic), the goal is to assign one unique path for each demand such that the cost is minimized. The cost is defined by the maximum ratio utilization (traffic/capacity) for all arcs. There is also a penalty associated with an traffic of an arc being above the comfort zone, 85% of the capacity by default. Please note that constraint programming is well suited here because we cannot have multiple active paths for a single demand. Otherwise, a approach based on a linear solver is a better match. A random problem generator is also included. Data Generator

DEFINE_int64	(	comfort_zone	,
		850	,
		"Above this limit in 1/	1000th,
		the link is said to be""congestioned."
	)

CP Model.

int main	(	int	argc,
		char **	argv
	)

namespace operations_research

Definition at line 1031 of file network_routing.cc.