Data Generation

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose.

This generator create clustered graphs for the graph coloring problem. It is having a fixed number of nodes and edges which is convenient to have problems of constant size. This is not compulsory (not the case of the knapsack and of the homogeneous graph generator) but it is interesting to be sure we're working on more smooth cases.

This is done by getting a geometric distribution of each node connectivity (number of edges) and then select randomly the connexions.

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)::CPModel

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose ! Density should be more than 1.

Very simple case from: Exploring the k-colorable Landscape with Iterated Greedy by Culberson & Luo https://pdfs.semanticscholar.org/e6cc/ab8f757203bf15680dbf456f295a7a31431a.pdf

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)::CPModel

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose ! Density should be more than 1.

Very simple case from: Exploring the k-colorable Landscape with Iterated Greedy by Culberson & Luo https://pdfs.semanticscholar.org/e6cc/ab8f757203bf15680dbf456f295a7a31431a.pdf

fill_with_generator!(cpmodel::CPModel, gen::BarabasiAlbertGraphGenerator)::CPModel
Creates graphs according to the Barbarasi-Albert attachment model: http://networksciencebook.com/chapter/5

fill_with_generator!(cpmodel::CPModel, gen::ErdosRenyiGraphGenerator)::CPModel    

Generates graphs according to the Erdos-Renyi model: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model

fill_with_generator!(cpmodel::CPModel, gen::WattsStrogatzGraphGenerator)::CPModel

fill_with_generator!(cpmodel::CPModel, gen::KnapsackGenerator)::CPModel

Fill the cpmodel with variables and constraints for the knapsack problem. The weights are uniformly distributed between 1 and gen.max_weight, the values are uniformly distributed between (for each weight) weight - max_weight/(10*correlation) and weight + max_weight/(10*correlation). It is possible to give Inf as the gen.correlation to have a strict equality between the weights and their values. gen.correlation must be strictly positive. This method is from the following paper: https://www.researchgate.net/publication/2548374CoreProblemsinKnapsack_Algorithms

Rng is a random number generator used to ensure experiment reproductibility accross devices. It is often set at the beginning of an experiment to generate deterministic training samples.

fill_with_generator!(cpmodel::CPModel, gen::TsptwGenerator)::CPModel

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose !

It is the same generator as used in "Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization": Quentin Cappart, Thierry Moisan, Louis-Martin Rousseau, Isabeau Prémont-Schwarz & Andre Cire https://arxiv.org/abs/2006.01610

Basicaly finds positions with a uniform distributions, then sets the time windows by creating a feasible tour and adding some randomness by using uniform distributions with gap and the length of the time windows.

Rng is a random number generator used to ensure experiment reproductibility accross devices. It is often set at the beginning of an experiment to generate deterministic training samples.

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose.

Rng is a random number generator used to ensure experiment reproductibility accross devices. It is often set at the beginning of an experiment to generate deterministic training samples.

This generator create graps for the NQueens problem.

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose.

This generator create graphs for the Eternity2 problem.

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose.

Rng is a random number generator used to ensure experiment reproductibility accross devices. It is often set at the beginning of an experiment to generate deterministic training samples.

fill_with_generator!(cpmodel::CPModel, gen::RBGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose !

This is the algorithm proposed by "Random constraint satisfaction: Easy generation of hard (satisfiable) instances" (Xu. et al, 2007) to generate forced satisfiable instance of RB.

fill_with_generator!(cpmodel::CPModel, gen::KepGenerator; rng::AbstractRNG = MersenneTwister())

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose!

The decision matrix x is the adjacent matrix of the graph (i.e. the instance). x[i, j] is branchable => pair i can receive a kidney from pair j x[i, j] is not branchable => pair i can not receive a kidney from pair j

The generator ensure that all pairs have at least one incoming arc and one outgoing arc (i.e. at least one branchable variable per row and column). For this we first place one branchable variable in each line of the matrix with a different column index each time. Then, the remaining edges are assigned randomly between the non-asssigned elements of the decision matrix. For reference, see https://hal.science/hal-01798850/document

fill_with_generator!(cpmodel::CPModel, gen::JobShopGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose.

fill_with_generator!(cpmodel::CPModel, gen::JobShopSoftDeadlinesGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose. Generates jobshop with soft deadlines instances.

fill_with_generator!(cpmodel::CPModel, gen::GraphColoringGenerator)

Fill a CPModel with the variables and constraints generated. We fill it directly instead of creating temporary files for efficiency purpose.

HomogenousGraphColoringGenerator <: AbstractModelGenerator Generator for homogeneous graph coloring problem.

struct ClusterizedGraphColoringGenerator <: AbstractModelGenerator

Generator of Graph Coloring instances : 
- n is the number of nodes
- k is the number of color
- p is the edge density of the graph

struct BarabasiAlbertGraphGenerator <: AbstractModelGenerator

Generator of Graph Coloring instances : 
- n is the number of nodes
- k is the number of color
http://networksciencebook.com/chapter/5

struct ErdosRenyiGraphGenerator <: AbstractModelGenerator

Generator of Graph Coloring instances : 
- n is the number of nodes
- k is the number of color

https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model

Eternity2Generator <: AbstractModelGenerator generator for Eternity2 problem https://en.wikipedia.org/wiki/EternityIIpuzzle.

JobShopGenerator <: AbstractModelGenerator Generator for standard jobshop problem with: - numberOfMachines::Int : Number of available machines - numberOfJobs::Int : Number of jobs to accomplish - maxTime::Int : Maximum available

https://en.wikipedia.org/wiki/Job-shop_scheduling

JobShopSoftDeadlinesGenerator2 <: AbstractModelGenerator Generator for jobshop problem with soft deadlines.

KepGenerator <: AbstractModelGenerator Generator for the kidney exchange problem: https://hal.science/hal-01798850/document

KnapsackGenerator <: AbstractModelGenerator Generator for the knapsack problem: https://en.wikipedia.org/wiki/Knapsack_problem

LatinGenerator <: AbstractModelGenerator Generator for the latin square problem: https://en.wikipedia.org/wiki/Latin_square

MaxCutGenerator <: AbstractModelGenerator Generator for the max-cut problem: https://en.wikipedia.org/wiki/Maximum_cut

MaximumIndependentSetGenerator <: AbstractModelGenerator Generator for the maximal independent set: https://en.wikipedia.org/wiki/Independentset(graphtheory)#Maximalindependent_set

NQueensGenerator <: AbstractModelGenerator Generator for the N-queens problem: https://en.wikipedia.org/wiki/Eightqueenspuzzle

struct RBGenerator <: AbstractModelGenerator

Details of the problem generator can be found in the article "Random constraint satisfaction: Easy generation of hard (satisfiable) instances" (Xu et al., 2007).

Generator of RB instances :

• k ≥ 2 arity of each constraint
• n ≥ 2 number of variables
• α > 0 determines the domain size d = n^α of each variable,
• r > 0 determines the number m = r ⋅ n ⋅ ln(n) of constraints,
• 0 < p < 1 determines the number nb = (1 - p) ⋅ d^k of allowed tuples of each relation.
• d domain size of each variable
• m number of constraints
• nb number of allowed tuples of each relation

TsptwGenerator <: AbstractModelGenerator Generator for the TSPTW problem: https://acrogenesis.com/or-tools/documentation/user_manual/manual/tsp/tsptw.html