Solutionneur CP d'origine

Cette section décrit le résolveur de programmation de contraintes d'origine, qui a été remplacé par le solution CP-SAT supérieure.

Les sections suivantes décrivent comment résoudre l'exemple décrit dans la section CP-SAT, cette fois en utilisant le composant CP d'origine. Si vous tenez à utiliser le résolveur de CP d'origine, vous pouvez parcourir la documentation de référence de l'API. Notez que le résolveur de CP d'origine constitue la base de la bibliothèque de routage et que son API peut être nécessaire pour personnaliser un modèle de routage.

Importer les bibliothèques

Le code suivant importe la bibliothèque requise.

Python

from ortools.constraint_solver import pywrapcp

C++

#include <ostream>
#include <string>

#include "ortools/constraint_solver/constraint_solver.h"

Java

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;

C#

using System;
using Google.OrTools.ConstraintSolver;

Déclarer le résolveur

Le code suivant déclare le résolveur.

Python

solver = pywrapcp.Solver("CPSimple")

C++

Solver solver("CpSimple");

Java

Solver solver = new Solver("CpSimple");

C#

Solver solver = new Solver("CpSimple");

Créer les variables

Le code suivant crée les variables correspondant au problème.

Le résolveur crée trois variables, x, y et z, chacune pouvant prendre les valeurs 0, 1 ou 2.

Python

num_vals = 3
x = solver.IntVar(0, num_vals - 1, "x")
y = solver.IntVar(0, num_vals - 1, "y")
z = solver.IntVar(0, num_vals - 1, "z")

C++

const int64_t num_vals = 3;
IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");

Java

final long numVals = 3;
final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
final IntVar z = solver.makeIntVar(0, numVals - 1, "z");

C#

const long numVals = 3;
IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

Créer la contrainte

Le code suivant crée la contrainte x &ne; y.

Python

solver.Add(x != y)
print("Number of constraints: ", solver.Constraints())

C++

solver.AddConstraint(solver.MakeAllDifferent({x, y}));
LOG(INFO) << "Number of constraints: "
          << std::to_string(solver.constraints());

Java

solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
logger.info("Number of constraints: " + solver.constraints());

C#

solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
Console.WriteLine($"Number of constraints: {solver.Constraints()}");

Appeler le résolveur

Le code suivant appelle le résolveur.

Le générateur de décisions est l'entrée principale du résolveur de CP d'origine. Il contient les éléments suivants:

  • vars : tableau contenant les variables du problème.
  • Règle permettant de choisir la variable suivante à laquelle attribuer une valeur.
  • Une règle pour choisir la prochaine valeur à attribuer à cette variable.

Pour en savoir plus, consultez Outil de création de décision.

Python

decision_builder = solver.Phase(
    [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
)

C++

DecisionBuilder* const db = solver.MakePhase(
    {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

Java

final DecisionBuilder db = solver.makePhase(
    new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

C#

DecisionBuilder db =
    solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

Le code de l'imprimante de solution, qui affiche chaque solution au fur et à mesure que le résolveur la trouve, est présenté dans la section suivante.

Comme il existe plusieurs solutions à notre problème, il est possible d'itérer les solutions avec une boucle while solver.NextSolution(). (Notez que cela fonctionne différemment de l'imprimante de solution du résolveur CP-SAT.)

Python

count = 0
solver.NewSearch(decision_builder)
while solver.NextSolution():
    count += 1
    solution = f"Solution {count}:\n"
    for var in [x, y, z]:
        solution += f" {var.Name()} = {var.Value()}"
    print(solution)
solver.EndSearch()
print(f"Number of solutions found: {count}")

C++

int count = 0;
solver.NewSearch(db);
while (solver.NextSolution()) {
  ++count;
  LOG(INFO) << "Solution " << count << ":" << std::endl
            << " x=" << x->Value() << " y=" << y->Value()
            << " z=" << z->Value();
}
solver.EndSearch();
LOG(INFO) << "Number of solutions found: " << solver.solutions();

Java

int count = 0;
solver.newSearch(db);
while (solver.nextSolution()) {
  ++count;
  logger.info(
      String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
}
solver.endSearch();
logger.info("Number of solutions found: " + solver.solutions());

C#

int count = 0;
solver.NewSearch(db);
while (solver.NextSolution())
{
    ++count;
    Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
}
solver.EndSearch();
Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

Résultats renvoyés par le résolveur

Voici les 18 solutions trouvées par cet outil:

Number of constraints:  1
Solution 1:
 x = 0 y = 1 z = 0
Solution 2:
 x = 0 y = 1 z = 1
Solution 3:
 x = 0 y = 1 z = 2
Solution 4:
 x = 0 y = 2 z = 0
Solution 5:
 x = 0 y = 2 z = 1
Solution 6:
 x = 0 y = 2 z = 2
Solution 7:
 x = 1 y = 0 z = 0
Solution 8:
 x = 1 y = 0 z = 1
Solution 9:
 x = 1 y = 0 z = 2
Solution 10:
 x = 1 y = 2 z = 0
Solution 11:
 x = 1 y = 2 z = 1
Solution 12:
 x = 1 y = 2 z = 2
Solution 13:
 x = 2 y = 0 z = 0
Solution 14:
 x = 2 y = 0 z = 1
Solution 15:
 x = 2 y = 0 z = 2
Solution 16:
 x = 2 y = 1 z = 0
Solution 17:
 x = 2 y = 1 z = 1
Solution 18:
 x = 2 y = 1 z = 2
Number of solutions found:  18
Advanced usage:
Problem solved in  2 ms
Memory usage:  13918208 bytes

Terminer le programme

Voici les programmes complets de l'exemple utilisant le composant CP d'origine.

Python

"""Simple Constraint optimization example."""

from ortools.constraint_solver import pywrapcp


def main():
    """Entry point of the program."""
    # Instantiate the solver.
    solver = pywrapcp.Solver("CPSimple")

    # Create the variables.
    num_vals = 3
    x = solver.IntVar(0, num_vals - 1, "x")
    y = solver.IntVar(0, num_vals - 1, "y")
    z = solver.IntVar(0, num_vals - 1, "z")

    # Constraint 0: x != y.
    solver.Add(x != y)
    print("Number of constraints: ", solver.Constraints())

    # Solve the problem.
    decision_builder = solver.Phase(
        [x, y, z], solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE
    )

    # Print solution on console.
    count = 0
    solver.NewSearch(decision_builder)
    while solver.NextSolution():
        count += 1
        solution = f"Solution {count}:\n"
        for var in [x, y, z]:
            solution += f" {var.Name()} = {var.Value()}"
        print(solution)
    solver.EndSearch()
    print(f"Number of solutions found: {count}")

    print("Advanced usage:")
    print(f"Problem solved in {solver.WallTime()}ms")
    print(f"Memory usage: {pywrapcp.Solver.MemoryUsage()}bytes")


if __name__ == "__main__":
    main()

C++

#include <ostream>
#include <string>

#include "ortools/constraint_solver/constraint_solver.h"

namespace operations_research {

void SimpleCpProgram() {
  // Instantiate the solver.
  Solver solver("CpSimple");

  // Create the variables.
  const int64_t num_vals = 3;
  IntVar* const x = solver.MakeIntVar(0, num_vals - 1, "x");
  IntVar* const y = solver.MakeIntVar(0, num_vals - 1, "y");
  IntVar* const z = solver.MakeIntVar(0, num_vals - 1, "z");

  // Constraint 0: x != y..
  solver.AddConstraint(solver.MakeAllDifferent({x, y}));
  LOG(INFO) << "Number of constraints: "
            << std::to_string(solver.constraints());

  // Solve the problem.
  DecisionBuilder* const db = solver.MakePhase(
      {x, y, z}, Solver::CHOOSE_FIRST_UNBOUND, Solver::ASSIGN_MIN_VALUE);

  // Print solution on console.
  int count = 0;
  solver.NewSearch(db);
  while (solver.NextSolution()) {
    ++count;
    LOG(INFO) << "Solution " << count << ":" << std::endl
              << " x=" << x->Value() << " y=" << y->Value()
              << " z=" << z->Value();
  }
  solver.EndSearch();
  LOG(INFO) << "Number of solutions found: " << solver.solutions();

  LOG(INFO) << "Advanced usage:" << std::endl
            << "Problem solved in " << std::to_string(solver.wall_time())
            << "ms" << std::endl
            << "Memory usage: " << std::to_string(Solver::MemoryUsage())
            << "bytes";
}

}  // namespace operations_research

int main(int /*argc*/, char* /*argv*/[]) {
  operations_research::SimpleCpProgram();
  return EXIT_SUCCESS;
}

Java

package com.google.ortools.constraintsolver.samples;
import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.DecisionBuilder;
import com.google.ortools.constraintsolver.IntVar;
import com.google.ortools.constraintsolver.Solver;
import java.util.logging.Logger;

/** Simple CP Program.*/
public class SimpleCpProgram {
  private SimpleCpProgram() {}

  private static final Logger logger = Logger.getLogger(SimpleCpProgram.class.getName());

  public static void main(String[] args) throws Exception {
    Loader.loadNativeLibraries();
    // Instantiate the solver.
    Solver solver = new Solver("CpSimple");

    // Create the variables.
    final long numVals = 3;
    final IntVar x = solver.makeIntVar(0, numVals - 1, "x");
    final IntVar y = solver.makeIntVar(0, numVals - 1, "y");
    final IntVar z = solver.makeIntVar(0, numVals - 1, "z");

    // Constraint 0: x != y..
    solver.addConstraint(solver.makeAllDifferent(new IntVar[] {x, y}));
    logger.info("Number of constraints: " + solver.constraints());

    // Solve the problem.
    final DecisionBuilder db = solver.makePhase(
        new IntVar[] {x, y, z}, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

    // Print solution on console.
    int count = 0;
    solver.newSearch(db);
    while (solver.nextSolution()) {
      ++count;
      logger.info(
          String.format("Solution: %d\n x=%d y=%d z=%d", count, x.value(), y.value(), z.value()));
    }
    solver.endSearch();
    logger.info("Number of solutions found: " + solver.solutions());

    logger.info(String.format("Advanced usage:\nProblem solved in %d ms\nMemory usage: %d bytes",
        solver.wallTime(), Solver.memoryUsage()));
  }
}

C#

using System;
using Google.OrTools.ConstraintSolver;

/// <summary>
///   This is a simple CP program.
/// </summary>
public class SimpleCpProgram
{
    public static void Main(String[] args)
    {
        // Instantiate the solver.
        Solver solver = new Solver("CpSimple");

        // Create the variables.
        const long numVals = 3;
        IntVar x = solver.MakeIntVar(0, numVals - 1, "x");
        IntVar y = solver.MakeIntVar(0, numVals - 1, "y");
        IntVar z = solver.MakeIntVar(0, numVals - 1, "z");

        // Constraint 0: x != y..
        solver.Add(solver.MakeAllDifferent(new IntVar[] { x, y }));
        Console.WriteLine($"Number of constraints: {solver.Constraints()}");

        // Solve the problem.
        DecisionBuilder db =
            solver.MakePhase(new IntVar[] { x, y, z }, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        // Print solution on console.
        int count = 0;
        solver.NewSearch(db);
        while (solver.NextSolution())
        {
            ++count;
            Console.WriteLine($"Solution: {count}\n x={x.Value()} y={y.Value()} z={z.Value()}");
        }
        solver.EndSearch();
        Console.WriteLine($"Number of solutions found: {solver.Solutions()}");

        Console.WriteLine("Advanced usage:");
        Console.WriteLine($"Problem solved in {solver.WallTime()}ms");
        Console.WriteLine($"Memory usage: {Solver.MemoryUsage()}bytes");
    }
}

Prestataires de décision

L'entrée principale du résolveur de CP d'origine est le compilateur de décision, qui contient les variables du problème et définit les options du résolveur.

L'exemple de code de la section précédente crée un constructeur de décision à l'aide de la méthode Phase (correspondant à la méthode C++ MakePhase).

Le terme Phase fait référence à une phase de la recherche. Dans cet exemple simple, il n'y a qu'une seule phase, mais pour des problèmes plus complexes, l'outil de création de décision peut comporter plusieurs phases, afin que le résolveur puisse appliquer différentes stratégies de recherche d'une phase à l'autre.

La méthode Phase comporte trois paramètres d'entrée:

  • vars : tableau contenant les variables du problème, qui, dans ce cas, est [x, y, z].
  • IntVarStrategy : règle permettant de choisir la prochaine variable non liée à laquelle attribuer une valeur. Ici, le code utilise la valeur par défaut CHOOSE_FIRST_UNBOUND, ce qui signifie qu'à chaque étape, le résolveur sélectionne la première variable non liée dans l'ordre dans lequel elle apparaît dans le tableau de variables transmis à la méthode Phase.
  • IntValueStrategy : règle permettant de choisir la prochaine valeur à attribuer à une variable. Ici, le code utilise la valeur par défaut ASSIGN_MIN_VALUE, qui sélectionne la plus petite valeur qui n'a pas encore été testée pour la variable. Les valeurs sont ainsi attribuées par ordre croissant. Une autre option est ASSIGN_MAX_VALUE, auquel cas le résolveur attribue les valeurs par ordre décroissant.