Resource allocation problems benchmark generator

This web page gives an implementation in the Java language The aim of this web page is to give and describe an implementation in the Java language of a model for encoding combinatorial resource allocation problems (i.e resource allocation problems where the resource to share is a set of indivisible goods). We also give three random instance generators.

Description of the model

The model for formally representing a combinatorial resource allocation problem is based on propositional logic, and is fully described in the following references:

	Allocation of indivisible goods: a general model and some complexity results Sylvain Bouveret, Hélène Fargier, Jérôme Lang and Michel Lemaître In Proceedings of Autonomous Agents and Multi Agent Systems 2005.	PAPER
	Un modèle général et des résultats de complexité pour le partage de biens indivisibles Sylvain Bouveret, Hélène Fargier, Jérôme Lang et Michel Lemaître In Actes de Modèles Formels de l'Interaction 2005. (in French)	PAPER

An instance of the resource allocation problem in this model is made of:

A set of n agents (numbered from 1 to n).
A set of m objects (numbered from 1 to m).
A set of constraints, restricting the set of admissible allocations, and which can be of several kinds.
- Logical constraints, expressed as propositional formulae over the set of propositional symbols alloc(o,i) (meaning that object o is allocated to agent i). The class ComplexInstance allows for building such constraints in several ways:
  - as a general logical formula (defined as recursive application of logical operators on subformulae),
  - as a clause of the propositional language,
  - as a formula in disjunctive normal form.
- Preemption constraints, which hold on subsets of objects, and which mean that none of these particular objects can be allocated to more than one agent. This kind of constraint is not explicitly present in the model proposed in the above references.
- Volume constraints, which hold on subsets of objects, which are defined by one weight per object and one maximal weight, and which mean that the sum of the weights of the selected objects cannot exceed the maximal weight. This constraint is not explicitely present in the model proposed in the above references.
A set of preferences, which are made of an agent number and a weighted propositional formula over the set of propositional symbols o(j) (one symbol per object). This formulae can be defined in several ways:
- as a general logical formula (defined as recursive application of logical operators on subformulae),
- as a formula in conjunctive normal form,
- as a formula in disjunctive normal form.

Here is an example of how to build an instance manually:


    ComplexInstance inst = new ComplexInstance(3, 4, "Dummy instance");

    int[][] cnf1 = {{1, -2, 3}, {2, 4}};

    int[][] cnf2 = {{1}, {-1, 2, 3, 4}};

    int[][] cnf3 = {{1, 2, 3}, {2, 4}, {-1}};

    inst.addPref(1, new ComplexInstance.WeightedLogicalObjectFormula(new ComplexInstance.ObjectCNF(cnf1), 5));

    inst.addPref(1, new ComplexInstance.WeightedLogicalObjectFormula(new ComplexInstance.ObjectCNF(cnf2), 10));

    inst.addPref(2, new ComplexInstance.WeightedLogicalObjectFormula(new ComplexInstance.ObjectCNF(cnf3), 2));

    

    inst.addConstraint(new ComplexInstance.PreemptionConstraint(4));

    for (int i = 1; i <= 3 ; i++) {

        inst.addConstraint(new ComplexInstance.LogicalConstraint(ComplexInstance.GenericObjectAgentFormula.and(

        ComplexInstance.GenericObjectAgentFormula.not(new ComplexInstance.ObjectAgentAtom(2, i)),

        ComplexInstance.GenericObjectAgentFormula.or(new ComplexInstance.ObjectAgentAtom(3, i), new ComplexInstance.ObjectAgentAtom(4, i))

        )));

    }

Such a code builds the following instance (printed with System.out.println(inst.pretty());):


---------------------------------------

Dummy instance -> 3 agents, 4 objects

---------------------------------------

CONSTRAINTS:

> Preemption Constraint: ( 1 2 3 4 )

> Logical Constraint: ((¬alloc(2,1)) /\ (alloc(3,1) \/ alloc(4,1)))

> Logical Constraint: ((¬alloc(2,2)) /\ (alloc(3,2) \/ alloc(4,2)))

> Logical Constraint: ((¬alloc(2,3)) /\ (alloc(3,3) \/ alloc(4,3)))

PREFERENCES:

Agent 1:

* < ((o1 \/ ¬o2 \/ o3) /\ (o2 \/ o4)), 5 >

* < ((o1) /\ (¬o1 \/ o2 \/ o3 \/ o4)), 10 >

Agent 2:

* < ((o1 \/ o2 \/ o3) /\ (o2 \/ o4) /\ (¬o1)), 2 >

Agent 3:

---------------------------------------

The generic generator

We also created a class for generating random instances of our resource allocation problem. This class generates instances of the following form:

The preferences are disjunctive normal forms of random weights and sizes (with conjunctive terms of random lengths).
The constraints can be of two kinds:
- a particular object is forbidden to a particular agent,
- a set of objects (of random length) cannot be allocated at the same time to the same agent
The preemption constraint holding on the entire set of objects can be present or not.

This random generator is highly customizable; the parameters can be set by using the nested classes described in the API specifications. However, the user can also use the default parameters (also described in the API specifications)

Here is an example of how to generate a random instance with 10 agents and 30 objects by using the default parameters, except that we do not want the preemption constraint:


    RandomComplexInstanceGenerator generator = new RandomComplexInstanceGenerator(10, 30);

    generator.hasPreemptionConstraint = false;

    ComplexInstance inst = generator.generate();

The Pleiades instance generator

The instances created by the previous generator are completely random and have nothing to do with any real-world application (in spite of the fact that we tried to make them as realistic as possible). We implemented a second random generator (that also generates instances of the model described above) that is inspired by a real-world application, described for example in the following reference:

Exploiting a Common Property Resource under a Fairness Constraint: a Case Study.
Michel Lemaître, Gérard Verfaillie and Nicolas Bataille
In Proceedings of the International Joint Conference on Artificial Intelligence 1999.

PAPER (PS)

This real-world application concerns the sharing of a constellation of agile Earth Observation Satellites. The generator first creates an instance of a simplified version of this problem. This version is based on the following elements.

The constellation is only made of one satellite, and the problem considers a number of orbital rotation nbOrbits of the satellite.
The agents post a set of observation requests.
An observation request is made of one (simple request) or several (stereo or wide areas requests) acquisitions, that must be all satisfied to satisfy the observation request. A weight is also associated to an observation request, characterizing the importance of the request for the concerned agent.
An acquisition is made of several opportunities: one per orbital rotation, because one photography can be acquired from any possible rotation. The acquisition is satisfied if and only if at least one of the acquisition opportunities is satisfied.
Each acquisition opportunity is characterized by an identity number and the number of the orbital rotation it concerns.
A set of volume constraints simulating the unequal exogenous rights of the agents: each acquisition opportunity is endowed with a weight, and each agent has a maximal weight. A given agent cannot receive a set of acquisition opportunities whose sum of weights is greater than the agent's maximal weight.
A set of volume constraints simulating the physical constraints of the satellite: due to the physical constraints (onboard memory, time windows, transition times), not all the observation requests can be fulfilled during the time considered. These real constraints (requiring to solve a planning problem) are approximated by volume constraints holding on k successive opportunities, and allowing only l opportunities among the k to be acquired.
Some observation requests are particular: "common requests". Such common requests are posted by all the agents at the same time, and if they are fullfilled, they go to all the agents. It generates some logical constraints.
Some complex observation requests such as stereo or wide area images need to be acquired from the same orbital rotation: it also generates some logical constraints.

From this random instance of the Pleiades problem, the generator creates an instance of the combinatorial resource allocation problem, that represents this instance. The objects are the acquisition opportunities, the preferences of the agents are their observation requests, and the constraints are the logical constraints and the volume constraints.
This random generator is also highly customizable; the parameters can be set by using the nested classes described in the API specifications. One can also use the default parameters (also described in the API specifications). Notice that if one specifies the number of agents nA and the number of objects nO, the instance created by the generator has only approximately nO objects (but not more). If one wants exactly nO objects, one will have to add some objects manually.

Here is an example of how to generate a random instance with 10 agents and approximately 50 objects by using the default parameters, except that want more common requests than the default (default is 20%).


      PleiadesComplexInstanceGenerator generator = new PleiadesComplexInstanceGenerator(5, 50);

      generator.requests.probabilityOfCommonRequest = 0.4;

      ComplexInstance inst = generator.generate();

Here is the example of an instance of the Pleiades problem created by the previous code:


Randomly generated instance:

___________________________________

List of requests:

  Agent 4 -- Weight 58 -> (< ID 1, orb 0 > || < ID 2, orb 1 > || < ID 3, orb 2 >)

  Agent 0 -- Weight 150 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >)

  Agent 1 -- Weight 51 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >)

  Agent 2 -- Weight 2 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >)

  Agent 3 -- Weight 121 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >)

  Agent 4 -- Weight 143 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >)

  Agent 0 -- Weight 111 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >)

  Agent 1 -- Weight 139 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >)

  Agent 2 -- Weight 112 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >)

  Agent 3 -- Weight 1 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >)

  Agent 4 -- Weight 1027848 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >)

  Agent 1 -- Weight 2 -> (< ID 10, orb 0 > || < ID 11, orb 1 > || < ID 12, orb 2 >)

  Agent 2 -- Weight 142 -> (< ID 13, orb 0 > || < ID 14, orb 1 > || < ID 15, orb 2 >)

  Agent 0 -- Weight 1 -> (< ID 16, orb 0 > || < ID 17, orb 1 > || < ID 18, orb 2 >)

  Agent 0 -- Weight 1366696 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >)

  Agent 1 -- Weight 2 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >)

  Agent 2 -- Weight 1 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >)

  Agent 3 -- Weight 572320 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >)

  Agent 4 -- Weight 86 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >)

  Agent 0 -- Weight 2 -> (< ID 22, orb 0 > || < ID 23, orb 1 > || < ID 24, orb 2 >)

  Agent 2 -- Weight 1405055 -> (< ID 25, orb 0 > || < ID 26, orb 1 > || < ID 27, orb 2 >) && (< ID 28, orb 0 > || < ID 29, orb 1 > || < ID 30, orb 2 >) && (< ID 31, orb 0 > || < ID 32, orb 1 > || < ID 33, orb 2 >) && (< ID 34, orb 0 > || < ID 35, orb 1 > || < ID 36, orb 2 >) && (< ID 37, orb 0 > || < ID 38, orb 1 > || < ID 39, orb 2 >)

  Agent 0 -- Weight 2 -> (< ID 40, orb 0 > || < ID 41, orb 1 > || < ID 42, orb 2 >)

  Agent 2 -- Weight 2 -> (< ID 43, orb 0 > || < ID 44, orb 1 > || < ID 45, orb 2 >) && (< ID 46, orb 0 > || < ID 47, orb 1 > || < ID 48, orb 2 >) (must be acquired in one orbit) 

List of common requests among the entire list:

  Common Request: Agent 0 -- Weight 150 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 1 -- Weight 51 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 2 -- Weight 2 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 3 -- Weight 121 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 4 -- Weight 143 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >)

  Common Request: Agent 0 -- Weight 111 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 1 -- Weight 139 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 2 -- Weight 112 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 3 -- Weight 1 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 4 -- Weight 1027848 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >)

  Common Request: Agent 0 -- Weight 1366696 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 1 -- Weight 2 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 2 -- Weight 1 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 3 -- Weight 572320 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 4 -- Weight 86 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >)

List of constraints:

1. Unequal rights constraints

  Agent 0 ->  Objects = [ < ID 4, orb 0 > < ID 5, orb 1 > < ID 6, orb 2 > < ID 7, orb 0 > < ID 8, orb 1 > < ID 9, orb 2 > < ID 16, orb 0 > < ID 17, orb 1 > < ID 18, orb 2 > < ID 19, orb 0 > < ID 20, orb 1 > < ID 21, orb 2 > < ID 22, orb 0 > < ID 23, orb 1 > < ID 24, orb 2 > < ID 40, orb 0 > < ID 41, orb 1 > < ID 42, orb 2 >] -- Weights = [ 4 4 3 2 4 3 1 3 4 2 4 3 1 3 1 2 1 4 ] -- maxWeight = 2

  Agent 1 ->  Objects = [ < ID 4, orb 0 > < ID 5, orb 1 > < ID 6, orb 2 > < ID 7, orb 0 > < ID 8, orb 1 > < ID 9, orb 2 > < ID 10, orb 0 > < ID 11, orb 1 > < ID 12, orb 2 > < ID 19, orb 0 > < ID 20, orb 1 > < ID 21, orb 2 >] -- Weights = [ 4 4 3 2 4 3 3 4 1 2 4 3 ] -- maxWeight = 7

  Agent 2 ->  Objects = [ < ID 4, orb 0 > < ID 5, orb 1 > < ID 6, orb 2 > < ID 7, orb 0 > < ID 8, orb 1 > < ID 9, orb 2 > < ID 13, orb 0 > < ID 14, orb 1 > < ID 15, orb 2 > < ID 19, orb 0 > < ID 20, orb 1 > < ID 21, orb 2 > < ID 25, orb 0 > < ID 26, orb 1 > < ID 27, orb 2 > < ID 28, orb 0 > < ID 29, orb 1 > < ID 30, orb 2 > < ID 31, orb 0 > < ID 32, orb 1 > < ID 33, orb 2 > < ID 34, orb 0 > < ID 35, orb 1 > < ID 36, orb 2 > < ID 37, orb 0 > < ID 38, orb 1 > < ID 39, orb 2 > < ID 43, orb 0 > < ID 44, orb 1 > < ID 45, orb 2 > < ID 46, orb 0 > < ID 47, orb 1 > < ID 48, orb 2 >] -- Weights = [ 4 4 3 2 4 3 3 1 4 2 4 3 3 2 2 4 4 3 2 4 3 4 1 3 2 2 1 3 3 2 3 4 3 ] -- maxWeight = 25

  Agent 3 ->  Objects = [ < ID 4, orb 0 > < ID 5, orb 1 > < ID 6, orb 2 > < ID 7, orb 0 > < ID 8, orb 1 > < ID 9, orb 2 > < ID 19, orb 0 > < ID 20, orb 1 > < ID 21, orb 2 >] -- Weights = [ 4 4 3 2 4 3 2 4 3 ] -- maxWeight = 90

  Agent 4 ->  Objects = [ < ID 1, orb 0 > < ID 2, orb 1 > < ID 3, orb 2 > < ID 4, orb 0 > < ID 5, orb 1 > < ID 6, orb 2 > < ID 7, orb 0 > < ID 8, orb 1 > < ID 9, orb 2 > < ID 19, orb 0 > < ID 20, orb 1 > < ID 21, orb 2 >] -- Weights = [ 2 1 1 4 4 3 2 4 3 2 4 3 ] -- maxWeight = 324

2. Generalized volume constraints

    Objects = [ 0 1 2 3 4 5 6 7 8 9] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 1 2 3 4 5 6 7 8 9 10] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 2 3 4 5 6 7 8 9 10 11] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 3 4 5 6 7 8 9 10 11 12] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 4 5 6 7 8 9 10 11 12 13] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 5 6 7 8 9 10 11 12 13 14] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 6 7 8 9 10 11 12 13 14 15] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 7 8 9 10 11 12 13 14 15 16] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 8 9 10 11 12 13 14 15 16 17] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 9 10 11 12 13 14 15 16 17 18] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 10 11 12 13 14 15 16 17 18 19] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 11 12 13 14 15 16 17 18 19 20] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 12 13 14 15 16 17 18 19 20 21] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 13 14 15 16 17 18 19 20 21 22] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 14 15 16 17 18 19 20 21 22 23] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 15 16 17 18 19 20 21 22 23 24] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 16 17 18 19 20 21 22 23 24 25] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 17 18 19 20 21 22 23 24 25 26] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 18 19 20 21 22 23 24 25 26 27] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 19 20 21 22 23 24 25 26 27 28] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 20 21 22 23 24 25 26 27 28 29] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 21 22 23 24 25 26 27 28 29 30] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 22 23 24 25 26 27 28 29 30 31] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 23 24 25 26 27 28 29 30 31 32] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 24 25 26 27 28 29 30 31 32 33] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 25 26 27 28 29 30 31 32 33 34] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 26 27 28 29 30 31 32 33 34 35] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 27 28 29 30 31 32 33 34 35 36] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 28 29 30 31 32 33 34 35 36 37] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 29 30 31 32 33 34 35 36 37 38] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 30 31 32 33 34 35 36 37 38 39] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 31 32 33 34 35 36 37 38 39 40] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 32 33 34 35 36 37 38 39 40 41] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 33 34 35 36 37 38 39 40 41 42] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 34 35 36 37 38 39 40 41 42 43] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 35 36 37 38 39 40 41 42 43 44] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 36 37 38 39 40 41 42 43 44 45] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 37 38 39 40 41 42 43 44 45 46] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

    Objects = [ 38 39 40 41 42 43 44 45 46 47] -- Weights = [ 1 1 1 1 1 1 1 1 1 1 ] -- maxWeight = 4

3. Common requests constraints

  Common Request: Agent 0 -- Weight 150 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 1 -- Weight 51 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 2 -- Weight 2 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 3 -- Weight 121 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >), Agent 4 -- Weight 143 -> (< ID 4, orb 0 > || < ID 5, orb 1 > || < ID 6, orb 2 >) is a common request.

  Common Request: Agent 0 -- Weight 111 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 1 -- Weight 139 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 2 -- Weight 112 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 3 -- Weight 1 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >), Agent 4 -- Weight 1027848 -> (< ID 7, orb 0 > || < ID 8, orb 1 > || < ID 9, orb 2 >) is a common request.

  Common Request: Agent 0 -- Weight 1366696 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 1 -- Weight 2 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 2 -- Weight 1 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 3 -- Weight 572320 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >), Agent 4 -- Weight 86 -> (< ID 19, orb 0 > || < ID 20, orb 1 > || < ID 21, orb 2 >) is a common request.

4. Images that must be acquired in one orbit

  Agent 2 -- Weight 2 -> (< ID 43, orb 0 > || < ID 44, orb 1 > || < ID 45, orb 2 >) && (< ID 46, orb 0 > || < ID 47, orb 1 > || < ID 48, orb 2 >) (must be acquired in one orbit)

This instance of the Pleiades problem translates into the following instance of our complex model:


--------------------------------------

Randomly generated instance of type Pleiades (seed = 1184596103059) -> 5 agents, 48 objects

---------------------------------------

CONSTRAINTS:

  > Volume Constraint: ( <o4: 4> <o5: 4> <o6: 3> <o7: 2> <o8: 4> <o9: 3> <o16: 1> <o17: 3> <o18: 4> <o19: 2> <o20: 4> <o21: 3> <o22: 1> <o23: 3> <o24: 1> <o40: 2> <o41: 1> <o42: 4> ) < 2

  > Volume Constraint: ( <o4: 4> <o5: 4> <o6: 3> <o7: 2> <o8: 4> <o9: 3> <o10: 3> <o11: 4> <o12: 1> <o19: 2> <o20: 4> <o21: 3> ) < 7

  > Volume Constraint: ( <o4: 4> <o5: 4> <o6: 3> <o7: 2> <o8: 4> <o9: 3> <o13: 3> <o14: 1> <o15: 4> <o19: 2> <o20: 4> <o21: 3> <o25: 3> <o26: 2> <o27: 2> <o28: 4> <o29: 4> <o30: 3> <o31: 2> <o32: 4> <o33: 3> <o34: 4> <o35: 1> <o36: 3> <o37: 2> <o38: 2> <o39: 1> <o43: 3> <o44: 3> <o45: 2> <o46: 3> <o47: 4> <o48: 3> ) < 25

  > Volume Constraint: ( <o4: 4> <o5: 4> <o6: 3> <o7: 2> <o8: 4> <o9: 3> <o19: 2> <o20: 4> <o21: 3> ) < 90

  > Volume Constraint: ( <o1: 2> <o2: 1> <o3: 1> <o4: 4> <o5: 4> <o6: 3> <o7: 2> <o8: 4> <o9: 3> <o19: 2> <o20: 4> <o21: 3> ) < 324

  > Volume Constraint: ( <o1: 1> <o2: 1> <o3: 1> <o4: 1> <o5: 1> <o6: 1> <o7: 1> <o8: 1> <o9: 1> <o10: 1> ) < 4

  > Volume Constraint: ( <o2: 1> <o3: 1> <o4: 1> <o5: 1> <o6: 1> <o7: 1> <o8: 1> <o9: 1> <o10: 1> <o11: 1> ) < 4

  > Volume Constraint: ( <o3: 1> <o4: 1> <o5: 1> <o6: 1> <o7: 1> <o8: 1> <o9: 1> <o10: 1> <o11: 1> <o12: 1> ) < 4

  > Volume Constraint: ( <o4: 1> <o5: 1> <o6: 1> <o7: 1> <o8: 1> <o9: 1> <o10: 1> <o11: 1> <o12: 1> <o13: 1> ) < 4

  > Volume Constraint: ( <o5: 1> <o6: 1> <o7: 1> <o8: 1> <o9: 1> <o10: 1> <o11: 1> <o12: 1> <o13: 1> <o14: 1> ) < 4

  > Volume Constraint: ( <o6: 1> <o7: 1> <o8: 1> <o9: 1> <o10: 1> <o11: 1> <o12: 1> <o13: 1> <o14: 1> <o15: 1> ) < 4

  > Volume Constraint: ( <o7: 1> <o8: 1> <o9: 1> <o10: 1> <o11: 1> <o12: 1> <o13: 1> <o14: 1> <o15: 1> <o16: 1> ) < 4

  > Volume Constraint: ( <o8: 1> <o9: 1> <o10: 1> <o11: 1> <o12: 1> <o13: 1> <o14: 1> <o15: 1> <o16: 1> <o17: 1> ) < 4

  > Volume Constraint: ( <o9: 1> <o10: 1> <o11: 1> <o12: 1> <o13: 1> <o14: 1> <o15: 1> <o16: 1> <o17: 1> <o18: 1> ) < 4

  > Volume Constraint: ( <o10: 1> <o11: 1> <o12: 1> <o13: 1> <o14: 1> <o15: 1> <o16: 1> <o17: 1> <o18: 1> <o19: 1> ) < 4

  > Volume Constraint: ( <o11: 1> <o12: 1> <o13: 1> <o14: 1> <o15: 1> <o16: 1> <o17: 1> <o18: 1> <o19: 1> <o20: 1> ) < 4

  > Volume Constraint: ( <o12: 1> <o13: 1> <o14: 1> <o15: 1> <o16: 1> <o17: 1> <o18: 1> <o19: 1> <o20: 1> <o21: 1> ) < 4

  > Volume Constraint: ( <o13: 1> <o14: 1> <o15: 1> <o16: 1> <o17: 1> <o18: 1> <o19: 1> <o20: 1> <o21: 1> <o22: 1> ) < 4

  > Volume Constraint: ( <o14: 1> <o15: 1> <o16: 1> <o17: 1> <o18: 1> <o19: 1> <o20: 1> <o21: 1> <o22: 1> <o23: 1> ) < 4

  > Volume Constraint: ( <o15: 1> <o16: 1> <o17: 1> <o18: 1> <o19: 1> <o20: 1> <o21: 1> <o22: 1> <o23: 1> <o24: 1> ) < 4

  > Volume Constraint: ( <o16: 1> <o17: 1> <o18: 1> <o19: 1> <o20: 1> <o21: 1> <o22: 1> <o23: 1> <o24: 1> <o25: 1> ) < 4

  > Volume Constraint: ( <o17: 1> <o18: 1> <o19: 1> <o20: 1> <o21: 1> <o22: 1> <o23: 1> <o24: 1> <o25: 1> <o26: 1> ) < 4

  > Volume Constraint: ( <o18: 1> <o19: 1> <o20: 1> <o21: 1> <o22: 1> <o23: 1> <o24: 1> <o25: 1> <o26: 1> <o27: 1> ) < 4

  > Volume Constraint: ( <o19: 1> <o20: 1> <o21: 1> <o22: 1> <o23: 1> <o24: 1> <o25: 1> <o26: 1> <o27: 1> <o28: 1> ) < 4

  > Volume Constraint: ( <o20: 1> <o21: 1> <o22: 1> <o23: 1> <o24: 1> <o25: 1> <o26: 1> <o27: 1> <o28: 1> <o29: 1> ) < 4

  > Volume Constraint: ( <o21: 1> <o22: 1> <o23: 1> <o24: 1> <o25: 1> <o26: 1> <o27: 1> <o28: 1> <o29: 1> <o30: 1> ) < 4

  > Volume Constraint: ( <o22: 1> <o23: 1> <o24: 1> <o25: 1> <o26: 1> <o27: 1> <o28: 1> <o29: 1> <o30: 1> <o31: 1> ) < 4

  > Volume Constraint: ( <o23: 1> <o24: 1> <o25: 1> <o26: 1> <o27: 1> <o28: 1> <o29: 1> <o30: 1> <o31: 1> <o32: 1> ) < 4

  > Volume Constraint: ( <o24: 1> <o25: 1> <o26: 1> <o27: 1> <o28: 1> <o29: 1> <o30: 1> <o31: 1> <o32: 1> <o33: 1> ) < 4

  > Volume Constraint: ( <o25: 1> <o26: 1> <o27: 1> <o28: 1> <o29: 1> <o30: 1> <o31: 1> <o32: 1> <o33: 1> <o34: 1> ) < 4

  > Volume Constraint: ( <o26: 1> <o27: 1> <o28: 1> <o29: 1> <o30: 1> <o31: 1> <o32: 1> <o33: 1> <o34: 1> <o35: 1> ) < 4

  > Volume Constraint: ( <o27: 1> <o28: 1> <o29: 1> <o30: 1> <o31: 1> <o32: 1> <o33: 1> <o34: 1> <o35: 1> <o36: 1> ) < 4

  > Volume Constraint: ( <o28: 1> <o29: 1> <o30: 1> <o31: 1> <o32: 1> <o33: 1> <o34: 1> <o35: 1> <o36: 1> <o37: 1> ) < 4

  > Volume Constraint: ( <o29: 1> <o30: 1> <o31: 1> <o32: 1> <o33: 1> <o34: 1> <o35: 1> <o36: 1> <o37: 1> <o38: 1> ) < 4

  > Volume Constraint: ( <o30: 1> <o31: 1> <o32: 1> <o33: 1> <o34: 1> <o35: 1> <o36: 1> <o37: 1> <o38: 1> <o39: 1> ) < 4

  > Volume Constraint: ( <o31: 1> <o32: 1> <o33: 1> <o34: 1> <o35: 1> <o36: 1> <o37: 1> <o38: 1> <o39: 1> <o40: 1> ) < 4

  > Volume Constraint: ( <o32: 1> <o33: 1> <o34: 1> <o35: 1> <o36: 1> <o37: 1> <o38: 1> <o39: 1> <o40: 1> <o41: 1> ) < 4

  > Volume Constraint: ( <o33: 1> <o34: 1> <o35: 1> <o36: 1> <o37: 1> <o38: 1> <o39: 1> <o40: 1> <o41: 1> <o42: 1> ) < 4

  > Volume Constraint: ( <o34: 1> <o35: 1> <o36: 1> <o37: 1> <o38: 1> <o39: 1> <o40: 1> <o41: 1> <o42: 1> <o43: 1> ) < 4

  > Volume Constraint: ( <o35: 1> <o36: 1> <o37: 1> <o38: 1> <o39: 1> <o40: 1> <o41: 1> <o42: 1> <o43: 1> <o44: 1> ) < 4

  > Volume Constraint: ( <o36: 1> <o37: 1> <o38: 1> <o39: 1> <o40: 1> <o41: 1> <o42: 1> <o43: 1> <o44: 1> <o45: 1> ) < 4

  > Volume Constraint: ( <o37: 1> <o38: 1> <o39: 1> <o40: 1> <o41: 1> <o42: 1> <o43: 1> <o44: 1> <o45: 1> <o46: 1> ) < 4

  > Volume Constraint: ( <o38: 1> <o39: 1> <o40: 1> <o41: 1> <o42: 1> <o43: 1> <o44: 1> <o45: 1> <o46: 1> <o47: 1> ) < 4

  > Volume Constraint: ( <o39: 1> <o40: 1> <o41: 1> <o42: 1> <o43: 1> <o44: 1> <o45: 1> <o46: 1> <o47: 1> <o48: 1> ) < 4

  > Logical Constraint: ((¬alloc(4,1) /\ ¬alloc(4,2) /\ ¬alloc(4,3) /\ ¬alloc(4,4) /\ ¬alloc(4,5)) \/ (alloc(4,1) /\ alloc(4,2) /\ alloc(4,3) /\ alloc(4,4) /\ alloc(4,5)))

  > Logical Constraint: ((¬alloc(5,1) /\ ¬alloc(5,2) /\ ¬alloc(5,3) /\ ¬alloc(5,4) /\ ¬alloc(5,5)) \/ (alloc(5,1) /\ alloc(5,2) /\ alloc(5,3) /\ alloc(5,4) /\ alloc(5,5)))

  > Logical Constraint: ((¬alloc(6,1) /\ ¬alloc(6,2) /\ ¬alloc(6,3) /\ ¬alloc(6,4) /\ ¬alloc(6,5)) \/ (alloc(6,1) /\ alloc(6,2) /\ alloc(6,3) /\ alloc(6,4) /\ alloc(6,5)))

  > Logical Constraint: ((¬alloc(7,1) /\ ¬alloc(7,2) /\ ¬alloc(7,3) /\ ¬alloc(7,4) /\ ¬alloc(7,5)) \/ (alloc(7,1) /\ alloc(7,2) /\ alloc(7,3) /\ alloc(7,4) /\ alloc(7,5)))

  > Logical Constraint: ((¬alloc(8,1) /\ ¬alloc(8,2) /\ ¬alloc(8,3) /\ ¬alloc(8,4) /\ ¬alloc(8,5)) \/ (alloc(8,1) /\ alloc(8,2) /\ alloc(8,3) /\ alloc(8,4) /\ alloc(8,5)))

  > Logical Constraint: ((¬alloc(9,1) /\ ¬alloc(9,2) /\ ¬alloc(9,3) /\ ¬alloc(9,4) /\ ¬alloc(9,5)) \/ (alloc(9,1) /\ alloc(9,2) /\ alloc(9,3) /\ alloc(9,4) /\ alloc(9,5)))

  > Logical Constraint: ((¬alloc(19,1) /\ ¬alloc(19,2) /\ ¬alloc(19,3) /\ ¬alloc(19,4) /\ ¬alloc(19,5)) \/ (alloc(19,1) /\ alloc(19,2) /\ alloc(19,3) /\ alloc(19,4) /\ alloc(19,5)))

  > Logical Constraint: ((¬alloc(20,1) /\ ¬alloc(20,2) /\ ¬alloc(20,3) /\ ¬alloc(20,4) /\ ¬alloc(20,5)) \/ (alloc(20,1) /\ alloc(20,2) /\ alloc(20,3) /\ alloc(20,4) /\ alloc(20,5)))

  > Logical Constraint: ((¬alloc(21,1) /\ ¬alloc(21,2) /\ ¬alloc(21,3) /\ ¬alloc(21,4) /\ ¬alloc(21,5)) \/ (alloc(21,1) /\ alloc(21,2) /\ alloc(21,3) /\ alloc(21,4) /\ alloc(21,5)))

  > Logical Constraint: ((¬alloc(43,3) /\ ¬alloc(44,3) /\ ¬alloc(45,3) /\ ¬alloc(46,3) /\ ¬alloc(47,3) /\ ¬alloc(48,3)) \/ (alloc(43,3) /\ ¬alloc(44,3) /\ ¬alloc(45,3) /\ alloc(46,3) /\ ¬alloc(47,3) /\ ¬alloc(48,3)) \/ (¬alloc(43,3) /\ alloc(44,3) /\ ¬alloc(45,3) /\ ¬alloc(46,3) /\ alloc(47,3) /\ ¬alloc(48,3)) \/ (¬alloc(43,3) /\ ¬alloc(44,3) /\ alloc(45,3) /\ ¬alloc(46,3) /\ ¬alloc(47,3) /\ alloc(48,3)))

PREFERENCES:

  Agent 1:

    * < ((o4 \/ o5 \/ o6)), 150 >

    * < ((o7 \/ o8 \/ o9)), 111 >

    * < ((o16 \/ o17 \/ o18)), 1 >

    * < ((o19 \/ o20 \/ o21)), 1366696 >

    * < ((o22 \/ o23 \/ o24)), 2 >

    * < ((o40 \/ o41 \/ o42)), 2 >

  Agent 2:

    * < ((o4 \/ o5 \/ o6)), 51 >

    * < ((o7 \/ o8 \/ o9)), 139 >

    * < ((o10 \/ o11 \/ o12)), 2 >

    * < ((o19 \/ o20 \/ o21)), 2 >

  Agent 3:

    * < ((o4 \/ o5 \/ o6)), 2 >

    * < ((o7 \/ o8 \/ o9)), 112 >

    * < ((o13 \/ o14 \/ o15)), 142 >

    * < ((o19 \/ o20 \/ o21)), 1 >

    * < ((o25 \/ o26 \/ o27) /\ (o28 \/ o29 \/ o30) /\ (o31 \/ o32 \/ o33) /\ (o34 \/ o35 \/ o36) /\ (o37 \/ o38 \/ o39)), 1405055 >

    * < ((o43 \/ o44 \/ o45) /\ (o46 \/ o47 \/ o48)), 2 >

  Agent 4:

    * < ((o4 \/ o5 \/ o6)), 121 >

    * < ((o7 \/ o8 \/ o9)), 1 >

    * < ((o19 \/ o20 \/ o21)), 572320 >

  Agent 5:

    * < ((o1 \/ o2 \/ o3)), 58 >

    * < ((o4 \/ o5 \/ o6)), 143 >

    * < ((o7 \/ o8 \/ o9)), 1027848 >

    * < ((o19 \/ o20 \/ o21)), 86 >

---------------------------------------

The Spot instance generator

The second specific instance generator we created is inspired by a real-world application close to the previous one. Spot is a constellation of Earth Observation Satellites, but these satellites are not agile, that is, the acquisition have fixed start time and end time (in the Pleiades problem, each acquisition had a time window). It simplifies the model, and thus allows for a more realistic modeling of the incompatibility constraints.
This generator works basically in the same way the Pleiades generator did. It is based on the following elements:

The constellation is only made of several satellites, and the problem considers a number of orbital rotation nbOrbits of the satellites.
The agents post a set of observation requests.
An observation request is made of one (simple request) or several (stereo or wide areas requests) acquisitions, that must be all satisfied to satisfy the observation request. The requests concerning wide areas generate several acquisitions (objects), that have close starting times. The requests concerning stereographic areas generate only one object, but virtually two objects corresponding to the acquisition of two photographies separated by a fixed amount of time (just retain that a stereo request generates one object, but the incompatibility constraints generated are as if at it was two objects). A weight is also associated to an observation request, characterizing the importance of the request for the agent concerned.
An acquisition is made of several opportunities: one per orbital rotation, because one photography can be acquired from any possible rotation and any satellite. The acquisition is satisfied if and only if at least one of the acquisition opportunities is satisfied.
Each acquisition opportunity has a start time and an end time. The start times are choosen in the following way:
- The start time of the first acquisition opportunity is randomly choosen between 0 and PERIOD_TIME. It can be randomly choosen according to a uniform law over the interval, or randomly choosen around a few « hot areas » (corresponding to the areas of the earth surface where a lot of requests concentrate) randomly choosen at the begining.
- The start times of the other acquisition opportunities of the acquisition are deduced from the start time of the first acquisition opportunity, given the distance between the satellites, and given the duration of an orbital rotation.
The end times are choosen according to the start times and the time an acquisition lasts (randomly choosen). Each acquisition opportunity is also characterized by a deviation angle, corresponding to the self-rotation of the acquisition instrument necessary to take the photo (an angle of 0 means that the area to acquire is just under the satellite). This angle is used to compute the transition times between acquisiton opportunities.
A volume constraint, corresponding to the onboard memory consumption. Each acquisition opportunity consumes a given amount of memory (approximately proportional to the duration of the acquisition), and the satellite has a limited amount of memory.
A set of exclusion constraints, just meaning that two given acquisition opportunities cannot be both choosen, either due to the fact that they overlap, or due to the transition times.

Like for the Pleiades problem generator, from this random instance of the Spot problem, the generator creates an instance of the combinatorial resource allocation problem, that represents this instance. The objects are the acquisition opportunities, the preferences of the agents are their observation requests, and the constraints are exclusion constraints and a set of volume constraints.
This random generator is also highly customizable; the parameters can be set by using the nested classes described in the API specifications. One can also use the default parameters (also described in the API specifications). Notice that if one specifies the number of agents nA and the number of objects nO, the instance created by the generator has only approximately nO objects (but not more). If one wants exactly nO objects, one will have to add some objects manually.

Here is an example of how to generate a random instance with 10 agents and approximately 50 objects by using the default parameters, except that we want less hot areas than the default number (which is 4).


    PleiadesComplexInstanceGenerator generator = new PleiadesComplexInstanceGenerator(5, 50);

    generator.requests.numberOfHotAreas = 2;
    
    ComplexInstance inst = generator.generate();

Here is the example of an instance of the Pleiades problem created by the previous code:


List of Hot Areas: [ 4441 1849 ]

Request 1: Agent 2 -- Weight 1 -> < ID1, orb0, sat0, [4407,4422], -25° > || < ID2, orb1, sat0, [10407,10422], -25° > || < ID3, orb2, sat0, [16407,16422], -25° > || < ID4, orb0, sat1, [6407,6422], -25° > || < ID5, orb1, sat1, [12407,12422], -25° > || < ID6, orb2, sat1, [407,422], -25° > || < ID7, orb0, sat2, [8407,8422], -25° > || < ID8, orb1, sat2, [14407,14422], -25° > || < ID9, orb2, sat2, [2407,2422], -25° >

Request 2: Agent 5 -- Weight 14 -> < ID10, orb0, sat0, [442,473], -21° > || < ID11, orb1, sat0, [6442,6473], -21° > || < ID12, orb2, sat0, [12442,12473], -21° > || < ID13, orb0, sat1, [2442,2473], -21° > || < ID14, orb1, sat1, [8442,8473], -21° > || < ID15, orb2, sat1, [14442,14473], -21° > || < ID16, orb0, sat2, [4442,4473], -21° > || < ID17, orb1, sat2, [10442,10473], -21° > || < ID18, orb2, sat2, [16442,16473], -21° >

Request 3: Agent 4 -- Weight 16 -> < ID19, orb0, sat0, [4419,4472], -3° > || < ID20, orb1, sat0, [10419,10472], -3° > || < ID21, orb2, sat0, [16419,16472], -3° > || < ID22, orb0, sat1, [6419,6472], -3° > || < ID23, orb1, sat1, [12419,12472], -3° > || < ID24, orb2, sat1, [419,472], -3° > || < ID25, orb0, sat2, [8419,8472], -3° > || < ID26, orb1, sat2, [14419,14472], -3° > || < ID27, orb2, sat2, [2419,2472], -3° >

Request 4: Agent 5 -- Weight 17 -> < ID28, orb0, sat0, [3586,3631], 22° > || < ID29, orb1, sat0, [9586,9631], 22° > || < ID30, orb2, sat0, [15586,15631], 22° > || < ID31, orb0, sat1, [5586,5631], 22° > || < ID32, orb1, sat1, [11586,11631], 22° > || < ID33, orb2, sat1, [17586,17631], 22° > || < ID34, orb0, sat2, [7586,7631], 22° > || < ID35, orb1, sat2, [13586,13631], 22° > || < ID36, orb2, sat2, [1586,1631], 22° >

Request 5: Agent 1 -- Weight 14 -> < ID37, orb0, sat0, [1859,1890], 22° > || < ID38, orb1, sat0, [7859,7890], 22° > || < ID39, orb2, sat0, [13859,13890], 22° > || < ID40, orb0, sat1, [3859,3890], 22° > || < ID41, orb1, sat1, [9859,9890], 22° > || < ID42, orb2, sat1, [15859,15890], 22° > || < ID43, orb0, sat2, [5859,5890], 22° > || < ID44, orb1, sat2, [11859,11890], 22° > || < ID45, orb2, sat2, [17859,17890], 22° >

Consumption of objects: [ 12 12 12 12 12 12 12 12 12 25 25 25 25 25 25 25 25 25 44 44 44 44 44 44 44 44 44 37 37 37 37 37 37 37 37 37 25 25 25 25 25 25 25 25 25 ]

Maximal amount of resource available (per satellite): 600

List of constraints:

1. Exclusion constraints:

  Objects < ID1, orb0, sat0, [4407,4422], -25° > and < ID19, orb0, sat0, [4419,4472], -3° > are incompatible.

  Objects < ID2, orb1, sat0, [10407,10422], -25° > and < ID20, orb1, sat0, [10419,10472], -3° > are incompatible.

  Objects < ID3, orb2, sat0, [16407,16422], -25° > and < ID21, orb2, sat0, [16419,16472], -3° > are incompatible.

  Objects < ID4, orb0, sat1, [6407,6422], -25° > and < ID22, orb0, sat1, [6419,6472], -3° > are incompatible.

  Objects < ID5, orb1, sat1, [12407,12422], -25° > and < ID23, orb1, sat1, [12419,12472], -3° > are incompatible.

  Objects < ID6, orb2, sat1, [407,422], -25° > and < ID24, orb2, sat1, [419,472], -3° > are incompatible.

  Objects < ID7, orb0, sat2, [8407,8422], -25° > and < ID25, orb0, sat2, [8419,8472], -3° > are incompatible.

  Objects < ID8, orb1, sat2, [14407,14422], -25° > and < ID26, orb1, sat2, [14419,14472], -3° > are incompatible.

  Objects < ID9, orb2, sat2, [2407,2422], -25° > and < ID27, orb2, sat2, [2419,2472], -3° > are incompatible.

2. Memory constraints:

  Objects -> [ < ID1, orb0, sat0, [4407,4422], -25° > < ID2, orb1, sat0, [10407,10422], -25° > < ID3, orb2, sat0, [16407,16422], -25° > < ID10, orb0, sat0, [442,473], -21° > < ID11, orb1, sat0, [6442,6473], -21° > < ID12, orb2, sat0, [12442,12473], -21° > < ID19, orb0, sat0, [4419,4472], -3° > < ID20, orb1, sat0, [10419,10472], -3° > < ID21, orb2, sat0, [16419,16472], -3° > < ID28, orb0, sat0, [3586,3631], 22° > < ID29, orb1, sat0, [9586,9631], 22° > < ID30, orb2, sat0, [15586,15631], 22° > < ID37, orb0, sat0, [1859,1890], 22° > < ID38, orb1, sat0, [7859,7890], 22° > < ID39, orb2, sat0, [13859,13890], 22° > ], weights -> [ 12 12 12 25 25 25 44 44 44 37 37 37 25 25 25 ], maxWeight = 600

  Objects -> [ < ID4, orb0, sat1, [6407,6422], -25° > < ID5, orb1, sat1, [12407,12422], -25° > < ID6, orb2, sat1, [407,422], -25° > < ID13, orb0, sat1, [2442,2473], -21° > < ID14, orb1, sat1, [8442,8473], -21° > < ID15, orb2, sat1, [14442,14473], -21° > < ID22, orb0, sat1, [6419,6472], -3° > < ID23, orb1, sat1, [12419,12472], -3° > < ID24, orb2, sat1, [419,472], -3° > < ID31, orb0, sat1, [5586,5631], 22° > < ID32, orb1, sat1, [11586,11631], 22° > < ID33, orb2, sat1, [17586,17631], 22° > < ID40, orb0, sat1, [3859,3890], 22° > < ID41, orb1, sat1, [9859,9890], 22° > < ID42, orb2, sat1, [15859,15890], 22° > ], weights -> [ 12 12 12 25 25 25 44 44 44 37 37 37 25 25 25 ], maxWeight = 600

  Objects -> [ < ID7, orb0, sat2, [8407,8422], -25° > < ID8, orb1, sat2, [14407,14422], -25° > < ID9, orb2, sat2, [2407,2422], -25° > < ID16, orb0, sat2, [4442,4473], -21° > < ID17, orb1, sat2, [10442,10473], -21° > < ID18, orb2, sat2, [16442,16473], -21° > < ID25, orb0, sat2, [8419,8472], -3° > < ID26, orb1, sat2, [14419,14472], -3° > < ID27, orb2, sat2, [2419,2472], -3° > < ID34, orb0, sat2, [7586,7631], 22° > < ID35, orb1, sat2, [13586,13631], 22° > < ID36, orb2, sat2, [1586,1631], 22° > < ID43, orb0, sat2, [5859,5890], 22° > < ID44, orb1, sat2, [11859,11890], 22° > < ID45, orb2, sat2, [17859,17890], 22° > ], weights -> [ 12 12 12 25 25 25 44 44 44 37 37 37 25 25 25 ], maxWeight = 600

This instance of the Pleiades problem translates into the following instance of our complex model:


---------------------------------------

Randomly generated instance of type Spot (seed = 1184658538919) -> 5 agents, 45 objects

---------------------------------------

CONSTRAINTS:

  > Logical Constraint: ((¬alloc(1,1) /\ ¬alloc(1,2) /\ ¬alloc(1,3) /\ ¬alloc(1,4) /\ ¬alloc(1,5)) \/ (¬alloc(19,1) /\ ¬alloc(19,2) /\ ¬alloc(19,3) /\ ¬alloc(19,4) /\ ¬alloc(19,5)))

  > Logical Constraint: ((¬alloc(2,1) /\ ¬alloc(2,2) /\ ¬alloc(2,3) /\ ¬alloc(2,4) /\ ¬alloc(2,5)) \/ (¬alloc(20,1) /\ ¬alloc(20,2) /\ ¬alloc(20,3) /\ ¬alloc(20,4) /\ ¬alloc(20,5)))

  > Logical Constraint: ((¬alloc(3,1) /\ ¬alloc(3,2) /\ ¬alloc(3,3) /\ ¬alloc(3,4) /\ ¬alloc(3,5)) \/ (¬alloc(21,1) /\ ¬alloc(21,2) /\ ¬alloc(21,3) /\ ¬alloc(21,4) /\ ¬alloc(21,5)))

  > Logical Constraint: ((¬alloc(4,1) /\ ¬alloc(4,2) /\ ¬alloc(4,3) /\ ¬alloc(4,4) /\ ¬alloc(4,5)) \/ (¬alloc(22,1) /\ ¬alloc(22,2) /\ ¬alloc(22,3) /\ ¬alloc(22,4) /\ ¬alloc(22,5)))

  > Logical Constraint: ((¬alloc(5,1) /\ ¬alloc(5,2) /\ ¬alloc(5,3) /\ ¬alloc(5,4) /\ ¬alloc(5,5)) \/ (¬alloc(23,1) /\ ¬alloc(23,2) /\ ¬alloc(23,3) /\ ¬alloc(23,4) /\ ¬alloc(23,5)))

  > Logical Constraint: ((¬alloc(6,1) /\ ¬alloc(6,2) /\ ¬alloc(6,3) /\ ¬alloc(6,4) /\ ¬alloc(6,5)) \/ (¬alloc(24,1) /\ ¬alloc(24,2) /\ ¬alloc(24,3) /\ ¬alloc(24,4) /\ ¬alloc(24,5)))

  > Logical Constraint: ((¬alloc(7,1) /\ ¬alloc(7,2) /\ ¬alloc(7,3) /\ ¬alloc(7,4) /\ ¬alloc(7,5)) \/ (¬alloc(25,1) /\ ¬alloc(25,2) /\ ¬alloc(25,3) /\ ¬alloc(25,4) /\ ¬alloc(25,5)))

  > Logical Constraint: ((¬alloc(8,1) /\ ¬alloc(8,2) /\ ¬alloc(8,3) /\ ¬alloc(8,4) /\ ¬alloc(8,5)) \/ (¬alloc(26,1) /\ ¬alloc(26,2) /\ ¬alloc(26,3) /\ ¬alloc(26,4) /\ ¬alloc(26,5)))

  > Logical Constraint: ((¬alloc(9,1) /\ ¬alloc(9,2) /\ ¬alloc(9,3) /\ ¬alloc(9,4) /\ ¬alloc(9,5)) \/ (¬alloc(27,1) /\ ¬alloc(27,2) /\ ¬alloc(27,3) /\ ¬alloc(27,4) /\ ¬alloc(27,5)))

  > Volume Constraint: ( <o1: 12> <o2: 12> <o3: 12> <o10: 25> <o11: 25> <o12: 25> <o19: 44> <o20: 44> <o21: 44> <o28: 37> <o29: 37> <o30: 37> <o37: 25> <o38: 25> <o39: 25> ) < 600

  > Volume Constraint: ( <o4: 12> <o5: 12> <o6: 12> <o13: 25> <o14: 25> <o15: 25> <o22: 44> <o23: 44> <o24: 44> <o31: 37> <o32: 37> <o33: 37> <o40: 25> <o41: 25> <o42: 25> ) < 600

  > Volume Constraint: ( <o7: 12> <o8: 12> <o9: 12> <o16: 25> <o17: 25> <o18: 25> <o25: 44> <o26: 44> <o27: 44> <o34: 37> <o35: 37> <o36: 37> <o43: 25> <o44: 25> <o45: 25> ) < 600

PREFERENCES:

  Agent 1:

    * < ((o37 \/ o38 \/ o39 \/ o40 \/ o41 \/ o42 \/ o43 \/ o44 \/ o45)), 14 >

  Agent 2:

    * < ((o1 \/ o2 \/ o3 \/ o4 \/ o5 \/ o6 \/ o7 \/ o8 \/ o9)), 1 >

  Agent 3:

  Agent 4:

    * < ((o19 \/ o20 \/ o21 \/ o22 \/ o23 \/ o24 \/ o25 \/ o26 \/ o27)), 16 >

  Agent 5:

    * < ((o10 \/ o11 \/ o12 \/ o13 \/ o14 \/ o15 \/ o16 \/ o17 \/ o18)), 14 >

    * < ((o28 \/ o29 \/ o30 \/ o31 \/ o32 \/ o33 \/ o34 \/ o35 \/ o36)), 17 >

---------------------------------------

Download

The source code can be downloaded here: partage.tar.gz.

Last modified: Wed May 14 11:18:04 CEST 2014