<jupyter_start><jupyter_text><jupyter_code>!pip install ortools
"""Simple travelling salesman problem on a circuit board."""

from __future__ import print_function
import math
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp


def create_data_model():
    """Stores the data for the problem."""
    data = {}
    # Locations in block units
    data['locations'] = [
        (288, 149), (288, 129), (270, 133), (256, 141), (256, 157), (246, 157),
        (236, 169), (228, 169), (228, 161), (220, 169), (212, 169), (204, 169),
        (196, 169), (188, 169), (196, 161), (188, 145), (172, 145), (164, 145),
        (156, 145), (148, 145), (140, 145), (148, 169), (164, 169), (172, 169),
        (156, 169), (140, 169), (132, 169), (124, 169), (116, 161), (104, 153),
        (104, 161), (104, 169), (90, 165), (80, 157), (64, 157), (64, 165),
        (56, 169), (56, 161), (56, 153), (56, 145), (56, 137), (56, 129),
        (56, 121), (40, 121), (40, 129), (40, 137), (40, 145), (40, 153),
        (40, 161), (40, 169), (32, 169), (32, 161), (32, 153), (32, 145),
        (32, 137), (32, 129), (32, 121), (32, 113), (40, 113), (56, 113),
        (56, 105), (48, 99), (40, 99), (32, 97), (32, 89), (24, 89),
        (16, 97), (16, 109), (8, 109), (8, 97), (8, 89), (8, 81),
        (8, 73), (8, 65), (8, 57), (16, 57), (8, 49), (8, 41),
        (24, 45), (32, 41), (32, 49), (32, 57), (32, 65), (32, 73),
        (32, 81), (40, 83), (40, 73), (40, 63), (40, 51), (44, 43),
        (44, 35), (44, 27), (32, 25), (24, 25), (16, 25), (16, 17),
        (24, 17), (32, 17), (44, 11), (56, 9), (56, 17), (56, 25),
        (56, 33), (56, 41), (64, 41), (72, 41), (72, 49), (56, 49),
        (48, 51), (56, 57), (56, 65), (48, 63), (48, 73), (56, 73),
        (56, 81), (48, 83), (56, 89), (56, 97), (104, 97), (104, 105),
        (104, 113), (104, 121), (104, 129), (104, 137), (104, 145), (116, 145),
        (124, 145), (132, 145), (132, 137), (140, 137), (148, 137), (156, 137),
        (164, 137), (172, 125), (172, 117), (172, 109), (172, 101), (172, 93),
        (172, 85), (180, 85), (180, 77), (180, 69), (180, 61), (180, 53),
        (172, 53), (172, 61), (172, 69), (172, 77), (164, 81), (148, 85),
        (124, 85), (124, 93), (124, 109), (124, 125), (124, 117), (124, 101),
        (104, 89), (104, 81), (104, 73), (104, 65), (104, 49), (104, 41),
        (104, 33), (104, 25), (104, 17), (92, 9), (80, 9), (72, 9),
        (64, 21), (72, 25), (80, 25), (80, 25), (80, 41), (88, 49),
        (104, 57), (124, 69), (124, 77), (132, 81), (140, 65), (132, 61),
        (124, 61), (124, 53), (124, 45), (124, 37), (124, 29), (132, 21),
        (124, 21), (120, 9), (128, 9), (136, 9), (148, 9), (162, 9),
        (156, 25), (172, 21), (180, 21), (180, 29), (172, 29), (172, 37),
        (172, 45), (180, 45), (180, 37), (188, 41), (196, 49), (204, 57),
        (212, 65), (220, 73), (228, 69), (228, 77), (236, 77), (236, 69),
        (236, 61), (228, 61), (228, 53), (236, 53), (236, 45), (228, 45),
        (228, 37), (236, 37), (236, 29), (228, 29), (228, 21), (236, 21),
        (252, 21), (260, 29), (260, 37), (260, 45), (260, 53), (260, 61),
        (260, 69), (260, 77), (276, 77), (276, 69), (276, 61), (276, 53),
        (284, 53), (284, 61), (284, 69), (284, 77), (284, 85), (284, 93),
        (284, 101), (288, 109), (280, 109), (276, 101), (276, 93), (276, 85),
        (268, 97), (260, 109), (252, 101), (260, 93), (260, 85), (236, 85),
        (228, 85), (228, 93), (236, 93), (236, 101), (228, 101), (228, 109),
        (228, 117), (228, 125), (220, 125), (212, 117), (204, 109), (196, 101),
        (188, 93), (180, 93), (180, 101), (180, 109), (180, 117), (180, 125),
        (196, 145), (204, 145), (212, 145), (220, 145), (228, 145), (236, 145),
        (246, 141), (252, 125), (260, 129), (280, 133)
    ]  # yapf: disable
    data['num_vehicles'] = 1
    data['depot'] = 0
    return data


def compute_euclidean_distance_matrix(locations):
    """Creates callback to return distance between points."""
    distances = {}
    for from_counter, from_node in enumerate(locations):
        distances[from_counter] = {}
        for to_counter, to_node in enumerate(locations):
            if from_counter == to_counter:
                distances[from_counter][to_counter] = 0
            else:
                # Euclidean distance
                distances[from_counter][to_counter] = (int(
                    math.hypot((from_node[0] - to_node[0]),
                               (from_node[1] - to_node[1]))))
    return distances


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print('Objective: {}'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Objective: {}m\n'.format(route_distance)


def main():
    """Entry point of the program."""
    # Instantiate the data problem.
    data = create_data_model()

    # Create the routing index manager.
    manager = pywrapcp.RoutingIndexManager(len(data['locations']),
                                           data['num_vehicles'], data['depot'])

    # Create Routing Model.
    routing = pywrapcp.RoutingModel(manager)

    distance_matrix = compute_euclidean_distance_matrix(data['locations'])

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return distance_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    # Setting first solution heuristic.
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = (
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    # Solve the problem.
    solution = routing.SolveWithParameters(search_parameters)

    # Print solution on console.
    if solution:
        print_solution(manager, routing, solution)


if __name__ == '__main__':
    main()
#finding shortest path in a graph

import numpy as np
from __future__ import print_function
import math, sys
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
np.set_printoptions(suppress=True,linewidth=sys.maxsize,threshold=sys.maxsize)


inf=-1
distances=np.array([
# [ "CH", "CL", "HB", "SL", "IN", "CO", "MT", "WA", "CI", "CN", "RI", "LV", "LX", "NV", "KV", "GR" ]
  [ 000,  362,  inf,  300,  201,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf  ], #CH
  [ inf,  000,  332,  inf,  inf,  142,  201,  inf,  inf,  251,  inf,  inf,  inf,  inf,  inf,  inf  ], #CL
  [ inf,  inf,  000,  inf,  inf,  inf,  213,  120,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf  ], #HB
  [ inf,  inf,  inf,  000,  245,  inf,  inf,  inf,  inf,  inf,  inf,  263,  inf,  312,  inf,  inf  ], #SL
  [ inf,  inf,  inf,  inf,  000,  176,  inf,  inf,  112,  inf,  inf,  114,  inf,  inf,  inf,  inf  ], #IN
  [ inf,  inf,  inf,  inf,  inf,  000,  inf,  inf,  105,  inf,  inf,  inf,  inf,  inf,  inf,  inf  ], #CO
  [ inf,  inf,  inf,  inf,  inf,  inf,  000,  209,  inf,  157,  inf,  inf,  inf,  inf,  inf,  inf  ], #MT
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  inf,  inf,  111,  inf,  inf,  inf,  inf,  inf  ], #WA
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  204,  inf,  inf,   95,  inf,  inf,  inf  ], #CI
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  318,  inf,  177,  inf,  inf,  244  ], #CN
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  inf,  inf,  inf,  inf,  205  ], #RI
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,   86,  175,  inf,  inf  ], #LV
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  inf,  170,  inf  ], #LX
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  180,  inf  ], #NV
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000,  299  ], #KV
  [ inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  inf,  000  ]  #GR
])

triinf=np.tril_indices(distances.shape[0], -1)
distances[triinf] = distances.T[triinf] #https://stackoverflow.com/questions/16444930/copy-upper-triangle-to-lower-triangle-in-a-python-matrix
print(distances)


def print_solution(manager, routing, solution):
    """Prints solution on console."""
    print('Objective: {}'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    plan_output = 'Route:\n'
    route_distance = 0
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    print(plan_output)
    plan_output += 'Objective: {}m\n'.format(route_distance)


# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(distances.shape[0],
                                        1, 1)

# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)

def distance_callback(from_index, to_index):
    """Returns the distance between the two nodes."""
    # Convert from routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return distances[from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
#results with AUTOMATIC, LOCAL_CHEAPEST_ARC, PATH_CHEAPEST_ARC, PATH_MOST_CONSTRAINED_ARC, UNSET
#best result with AUTOMATIC, GLOBAL_CHEAPEST_ARC, PATH_CHEAPEST_ARC, PATH_MOST_CONSTRAINED_ARC, UNSET
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC)

# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)

# Print solution on console.
if solution:
    print_solution(manager, routing, solution)

#Christos's Greek Yogurt
#https://learning.edx.org/course/course-v1:MITx+CTL.SC0x+2T2020/block-v1:MITx+CTL.SC0x+2T2020+type@sequential+block@7e84b52028df41cd95b7ffef2872d379/block-v1:MITx+CTL.SC0x+2T2020+type@vertical+block@10256a90e6594e3284d9086fcdb0dd14
from ortools.linear_solver import pywraplp
import numpy as np

def create_data_model():
  """Stores the data for the problem."""
  data = {}
  #                Boston	Seattle	Tampa
  # Chicago       
  # Atlanta
  # Denver
  data['obj_coeffs'] = [
   [1.04, 1.27, 1.22],
   [1.23, 1.93, 0.60],
   [1.92, 0.94, 1.03]]

  data['constraint_coeffs_min_max'] = [  
     #quantités livrées
      ([[1, 0, 0],
        [1, 0, 0],
        [1, 0, 0]], 11000, 11000),
      ([[0, 1, 0],
        [0, 1, 0],
        [0, 1, 0]], 6300, 6300),        
      ([[0, 0, 1],
        [0, 0, 1],
        [0, 0, 1]], 7400, 7400),
      
     #quantités expédiées

      ([[1, 1, 1],
        [0, 0, 0],
        [0, 0, 0]], 0, 10000),
      ([[0, 0, 0],
        [1, 1, 1],
        [0, 0, 0]], 0, 10000),
      ([[0, 0, 0],
        [0, 0, 0],
        [1, 1, 1]], 0, 10000)  ]

  return data


data = create_data_model()
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver('CBC')
infinity = solver.infinity()

x=[[solver.IntVar(0, infinity, f'x[{j},{i}]') for i in range(len(data['obj_coeffs'][j]))] for j in range(len(data['obj_coeffs']))] 

for c in data['constraint_coeffs_min_max']:
  constraint = solver.RowConstraint(c[1], c[2], '')
  for ji,v in np.ndenumerate(c[0]):
    constraint.SetCoefficient(x[ji[0]][ji[1]], v*1.0)
print('Number of constraints =', solver.NumConstraints())
# In Python, you can also set the constraints as follows.
# for i in range(data['num_constraints']):
#  constraint_expr = \
# [data['constraint_coeffs'][i][j] * x[j] for j in range(data['num_vars'])]
#  solver.Add(sum(constraint_expr) <= data['bounds'][i])

objective = solver.Objective()
for ji,v in np.ndenumerate(data['obj_coeffs']):
  objective.SetCoefficient(x[ji[0]][ji[1]], v*1.0)
objective.SetMinimization()
# In Python, you can also set the objective as follows.
# obj_expr = [data['obj_coeffs'][j] * x[j] for j in range(data['num_vars'])]
# solver.Maximize(solver.Sum(obj_expr))

status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
  print('Objective value =', solver.Objective().Value())
  for j in x:
    for i in j:
      print(i.name(), ' = ', i.solution_value())
  print()
  print('Problem solved in %f milliseconds' % solver.wall_time())
  print('Problem solved in %d iterations' % solver.iterations())
  print('Problem solved in %d branch-and-bound nodes' % solver.nodes())
else:
  print('The problem does not have an optimal solution.')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.18535335042109116, 'fraction_numerical': 0.129476382277554, 'mean_word_length': 3.12070006035003, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 7, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '176414', 'license': 'MIT', 'n_tokens_mistral': 6588, 'n_tokens_neox': 5127, 'n_words': 1457, 'path': 'SC0X_Python_Samples.ipynb', 'repo_name': 'remisoulignac/scx_scream', 'size': '13655'}