operations_research Namespace Reference

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. More...

Classes

class OrderedLNS

Cycles all possible permutations. More...

class RandomLNS

RandomLNS is used for the local search and frees the number of elements specified in 'free_elements' randomly. More...

class Evaluator

class SymbolsSharedByTwoCardsConstraint

Dedicated constraint to count the symbols shared by two cards. More...

class DobbleOperator

Local Search. More...

class SwapSymbols

Swap 2 symbols. More...

class SwapSymbolsOnCardPairs

Multiple swaps of two symbols. More...

class DobbleFilter

Local Search Filter. More...

class SubstitutionMap

SubstitutionMap. More...

struct Bounds

Bounds. More...

class BoundsStore

BoundsStore. More...

class ArithmeticConstraint

ArithmeticConstraint. More...

class ArithmeticPropagator

ArithmeticPropagator. More...

class RowConstraint

Custom Constraints. More...

class OrConstraint

class ConstraintRef

class GlobalArithmeticConstraint

class JobShopData

JobShopData. More...

class SwapIntervals

Exchange 2 intervals on a sequence variable. More...

class ShuffleIntervals

Shuffle a fixed-length sub-sequence on one sequence variable. More...

class SequenceLns

LNS Operator. More...

class MultiDimKnapsackData

Data. More...

class NetworkRoutingData

Data Contains problem data. More...

class NetworkRoutingDataBuilder

Data Generation. More...

struct Demand

Solving the Problem. More...

class NetworkRoutingSolver

class NQueenSymmetry

class SX

Symmetry vertical axis. More...

class SY

Symmetry horizontal axis. More...

class SD1

Symmetry first diagonal axis. More...

class SD2

Symmetry second diagonal axis. More...

class R90

Rotate 1/4 turn. More...

class R180

Rotate 1/2 turn. More...

class R270

Rotate 3/4 turn. More...

struct ParserState

struct Instance

Data Instances. More...

class Box

Box. More...

struct BoxLessThan

class CoveringProblem

Covering Problem. More...

Typedefs

typedef std::vector< std::pair
< int, int > > Coordinates

Vector of (x,y) node coordinates, *unscaled*, in some imaginary planar, metric grid.

Functions

void CheckConstraintViolators (const std::vector< int64 > &vars, std::vector< int > *const violators)

Checks that all pairwise distances are unique and returns all violators.

bool CheckCostas (const std::vector< int64 > &vars)

Check that all pairwise differences are unique.

void CostasSoft (const int dim)

Computes a Costas Array using soft constraints.

void CostasHard (const int dim)

Computes a Costas Array.

void Cryptoarithmetics ()

CostValue BuildAndSolveHungarianInstance (const LinearSumAssignment< ForwardStarGraph > &assignment)

void DisplayAssignment (const LinearSumAssignment< ForwardStarGraph > &assignment)

int solve_dimacs_assignment (int argc, char *argv[])

IntVar * CreateViolationVar (Solver *const solver, const std::vector< IntVar * > &card1_symbol_vars, const std::vector< IntVar * > &card2_symbol_vars, int num_symbols_per_card)

Creates two integer variables: one that counts the number of symbols common to two cards, and one that counts the absolute difference between the first var and 1 (i.e.

void SolveDobble (int num_cards, int num_symbols, int num_symbols_per_card)

Main Method.

void MinCostFlowOn4x4Matrix ()

Min Cost Flow.

void MaxFeasibleFlow ()

Max Flow.

void GolombRuler (int size)

void RunIntegerProgrammingExample (MPSolver::OptimizationProblemType optimization_problem_type)

void RunAllExamples ()

void Jobshop (const JobShopData &data)

void JobshopLs (const JobShopData &data)

Model and Solve.

void AssignmentOn4x4Matrix ()

Test assignment on a 4x4 matrix.

void RunLinearProgrammingExample (MPSolver::OptimizationProblemType optimization_problem_type)

void BuildLinearProgrammingMaxExample (MPSolver::OptimizationProblemType type)

void MagicSquare (int grid_size)

string ExprLabel (int index)

Creates node labels.

string IntervalLabel (int index)

string SequenceLabel (int index)

string ConstraintLabel (int index)

template<class T>

void ExportLinks (const CPModelProto &model, const string &source, const T &proto, GraphExporter *const exporter)

Scans argument to add links in the graph.

bool GetValueIfConstant (const CPModelProto &model, const CPIntegerExpressionProto &proto, int64 *const value)

Scans the expression protobuf to see if it corresponds to an integer variable with min_value == max_value.

void DeclareExpression (int index, const CPModelProto &proto, GraphExporter *const exporter)

Declares a labelled expression in the graph file.

void DeclareInterval (int index, const CPModelProto &proto, GraphExporter *const exporter)

void DeclareSequence (int index, const CPModelProto &proto, GraphExporter *const exporter)

void DeclareConstraint (int index, const CPModelProto &proto, GraphExporter *const exporter)

void ExportToGraphFile (const CPModelProto &proto, File *const file, GraphExporter::GraphFormat format)

Parses the proto and exports it to a graph file.

int Run ()

Main Method.

int64 EvaluateItem (MultiDimKnapsackData *const data, int64 var, int64 val)

void SolveKnapsack (MultiDimKnapsackData *const data)

void CheckNumberOfSolutions (int size, int num_solutions)

void NQueens (int size)

static void ParseProblemLine (const char *line, ParserState *state, ForwardStarGraph **graph)

static void ParseNodeLine (const char *line, ParserState *state)

static void ParseArcLine (const char *line, ParserState *state, ForwardStarGraph *graph, LinearSumAssignment< ForwardStarGraph > **assignment)

static void ParseOneLine (ParserState *state, ForwardStarGraph **graph, LinearSumAssignment< ForwardStarGraph > **assignment, char *line)

Parameters out of style-guide order because this function is used as a callback that varies the input line.

void ParseFileByLines (const string &filename, Callback1< char * > *line_parser)

LinearSumAssignment
< ForwardStarGraph > * ParseDimacsAssignment (const string &filename, string *error_message, ForwardStarGraph **graph_handle)

Reads an assignment problem description from the given file in DIMACS format and returns a LinearSumAssignment object representing the problem description.

int64 Travel (const Coordinates *const coords, RoutingModel::NodeIndex from, RoutingModel::NodeIndex to)

Returns the scaled Euclidean distance between two nodes, coords holding the coordinates of the nodes.

int64 ServiceTime (const std::vector< int64 > *const service_times, RoutingModel::NodeIndex node)

Returns the scaled service time at a given node, service_times holding the service times.

int64 TravelPlusServiceTime (const Coordinates *const coords, const std::vector< int64 > *const service_times, RoutingModel::NodeIndex from, RoutingModel::NodeIndex to)

Returns the scaled (distance plus service time) between two nodes, coords holding the coordinates of the nodes and service_times holding the service times.

int64 Demand (const std::vector< int64 > *const demands, RoutingModel::NodeIndex from, RoutingModel::NodeIndex to)

Returns the demand (quantity picked up or delivered) of a node, demands holds the demand of each node.

string VerboseOutput (const RoutingModel &routing, const Assignment &assignment, const Coordinates &coords, const std::vector< int64 > &service_times)

Outputs a solution to the current model in a string.

bool SafeParseInt64Array (const string &str, std::vector< int64 > *parsed_int)

An inefficient but convenient method to parse a whitespace-separated list of integers.

bool LoadAndSolve (const string &pdp_file)

Builds and solves a model from a file in the format defined by Li & Lim (http://www.sintef.no/static/am/opti/projects/top/vrp/format_pdp.htm).

static void WriteOrDie (const char *buffer, size_t item_size, size_t buffer_length, FILE *fp)

void PrintDimacsAssignmentProblem (const LinearSumAssignment< ForwardStarGraph > &assignment, const TailArrayManager< ForwardStarGraph > &tail_array_manager, const string &output_filename)

Given a LinearSumAssigment object representing an assignment problem description, outputs the problem in DIMACS format in the output file.

void ComputeOneDayOneTeamTuples (int num_teams, IntTupleSet *const tuples)

Utility functions to help create the model.

void AddOneDayOneTeamConstraint (Solver *const solver, IntVar *const opponent, IntVar *const home_away, IntVar *const signed_opponent, const IntTupleSet &intra_day_tuples)

void ComputeOneDayTuples (int num_teams, IntTupleSet *const day_tuples)

Constraints for one day and all teams.

void AddOneTeamConstraints (Solver *const solver, const std::vector< IntVar * > &opponents, const std::vector< IntVar * > &home_aways, const std::vector< IntVar * > &signed_opponents, const IntTupleSet &home_away_tuples, IntVar *const break_var, int num_teams)

Adds all constraints relating to one teams and the complete schedule.

void ComputeOneTeamHomeAwayTuples (int num_teams, IntTupleSet *const home_away_tuples)

Constraints for one team and all days.

void SportsScheduling (int num_teams)

Main solving method.

void SolveInstance (const Instance &instance, MPSolver::OptimizationProblemType solver_type)

Main Solve Method.

Variables

static const char *const kUsageTemplate = "usage: %s <filename>"

static const int kProblem = -1

Utilities.

static const int kOk = 0

static const char kGreen1 [] = "#A2CD5A"

Colors.

static const char kGreen2 [] = "#76EEC6"

static const char kGreen3 [] = "#00CD00"

static const char kWhite [] = "#FAFAFA"

static const char kBlue [] = "#87CEFA"

static const char kYellow [] = "#FFF68F"

static const char kRed [] = "#A52A2A"

static const int64 kDisconnectedDistance = -1LL

Data and Data Generation.

const int64 kScalingFactor = 1000

Scaling factor used to scale up distances, allowing a bit more precision from Euclidean distances.

Instance kInstances []

const int kInstanceCount = 10

Detailed Description

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License.