Created
December 28, 2023 11:51
-
-
Save ah-saleh/aaa68922e442bbb803c3442909d1372f to your computer and use it in GitHub Desktop.
Ornament placement in MiniZinc
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% 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]; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
% 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; | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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
ornaments.mzn
(the model file) andornaments.dzn
(the data file) in the MiniZinc IDE.Option 2: Command Line Interface
If you prefer using the command line, follow these steps:
Install MiniZinc: Ensure that MiniZinc is installed on your system. Installation instructions can be found on the MiniZinc website.
Run the Model: Use the following command to run the model with the OR-Tools solver:
This command executes the
ornaments.mzn
model file with the data fromornaments.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.