Ornament placement in MiniZinc

ornaments.dzn

% Generated .dzn file as input for .mzn file
num_ornaments = 10;
num_sections = 3;
weight = [5, 3, 4, 4, 2, 2, 5, 3, 5, 3];
aesthetic = [8, 5, 7, 10, 4, 4, 8, 6, 7, 7];
maxWeight = [7, 12, 14];
blocks = [4, 4, 4];
color = [1, 3, 3, 4, 5, 3, 4, 3, 4, 5];
shape = [5, 2, 2, 4, 2, 5, 2, 3, 2, 4];

ornaments.mzn

% Parameters
int: num_ornaments;
int: num_sections;
set of int: ORNAMENTS = 1..num_ornaments;
set of int: SECTIONS = 1..num_sections;
array[ORNAMENTS] of int: weight;  % Weights of ornaments
array[ORNAMENTS] of int: aesthetic;  % Aesthetic values of ornaments
array[SECTIONS] of int: maxWeight;  % Max weight per section
array[SECTIONS] of int: blocks;  % Number of blocks per section

% Attributes for each ornament
array[ORNAMENTS] of int: color;  % Color attribute of ornaments
array[ORNAMENTS] of int: shape;  % Shape attribute of ornaments

% Decision variables (1 if ornament o is placed in section s, block b)
array[ORNAMENTS, SECTIONS, 1..max(blocks)] of var 0..1: placed;

% Placement constraints - each ornament is placed exactly once
constraint forall(s in SECTIONS)(
    forall(b in 1..blocks[s])(
        sum(o in ORNAMENTS)(placed[o, s, b]) <= 1
    ) /\
    forall(b in blocks[s]+1..max(blocks))(
        sum(o in ORNAMENTS)(placed[o, s, b]) = 0
    )
);

% Weight constraints - total weight does not exceed capacity
constraint forall(s in SECTIONS)(
    sum(o in ORNAMENTS, b in 1..blocks[s])(weight[o] * placed[o, s, b]) <= maxWeight[s]
);

% Block constraints - at most one ornament per block in each section
constraint forall(s in SECTIONS, b in 1..blocks[s])(
    sum(o in ORNAMENTS)(placed[o, s, b]) <= 1
);

% Ornaments with the same color or shape should not be placed in consecutive blocks
constraint forall(s in SECTIONS)(
    forall(b in 1..blocks[s]-1, o1, o2 in ORNAMENTS)(
        (color[o1] = color[o2] -> (placed[o1, s, b] + placed[o2, s, b+1] <= 1)) /\
        (shape[o1] = shape[o2] -> (placed[o1, s, b] + placed[o2, s, b+1] <= 1))
    )
    /\
    forall(o1, o2 in ORNAMENTS)(
        % Checking the last block with the first block for wraparound
        (color[o1] = color[o2] -> (placed[o1, s, blocks[s]] + placed[o2, s, 1] <= 1)) /\
        (shape[o1] = shape[o2] -> (placed[o1, s, blocks[s]] + placed[o2, s, 1] <= 1))
    )
);

% Objective function
var int: total_aesthetic = sum(o in ORNAMENTS, s in SECTIONS, b in 1..blocks[s])(aesthetic[o] * placed[o, s, b]);

solve maximize total_aesthetic;

Constraint Programming for Optimizing X-Mas Tree Decoration

Problem Description

This project demonstrates the application of constraint programming to optimize the decoration of a Christmas tree. The goal is to determine the optimal placement of ornaments on the tree, ensuring maximum visibility and aesthetic appeal while maintaining balance across the branches. The problem was first described by Mansour Zarrin ( https://www.linkedin.com/posts/m-zarrin_optimization-constraintprogramming-techmeetstradition-activity-7144368719631183873-KMxC )

How to Run

Option 1: Using MiniZinc IDE

1. Download and Install MiniZinc IDE: First, download the MiniZinc IDE from the official MiniZinc website.
2. Choose a Solver: The IDE allows you to pick from a variety of solvers. You can choose Google's OR-Tools or any other solver that you prefer.
3. Load the Model and Data Files: Open ornaments.mzn (the model file) and ornaments.dzn (the data file) in the MiniZinc IDE.
4. Run the Model: Execute the model in the IDE to see the results.

Option 2: Command Line Interface

If you prefer using the command line, follow these steps:

1. Install MiniZinc: Ensure that MiniZinc is installed on your system. Installation instructions can be found on the MiniZinc website.

2. Run the Model: Use the following command to run the model with the OR-Tools solver:

   minizinc --solver com.google.ortools.sat ornaments.mzn ornaments.dzn
   

This command executes the ornaments.mzn model file with the data from ornaments.dzn, using Google's OR-Tools SAT solver.

Feel free to experiment with different solvers and parameters to explore various optimization outcomes.

---

Feedback and Contributions

Your feedback and contributions are welcome! If you have suggestions or modifications, feel free to leave comments.