Sunday, March 6, 2016

A CP Model for the Weight Problem of Bachet de Meziriac

Fellow OR blogger Erwin Kalvelagen just posted a MINLP model for a puzzle apparently posed by French mathematician Claude Gaspard Bachet de Méziriac. You can read the puzzle statement on Erwin's blog; a brief synopsis is that you are looking to find four integer weights that sum to 40, such that any object with integer weight from 1 to 40 can be weighed using them. I assume (and Erwin apparently agrees) that means weight on a balance scale, where weights can be placed either in the same pan as the object being weighed or in the opposite pan.

Just for amusement, here's a MiniZinc constraint programming model for the problem. It yields (unsurprisingly) the same unique solution that Erwin's MINLP model produces.

% Bachet de Meziriac problem

include "globals.mzn";

% sizes of the pieces
array[1..4] of var 1..40: x;

% pieces used in subtotals
array[1..40, 1..4] of var -1..1: y;

% order constraints
constraint increasing(x);

% overall sum
constraint sum(x) = 40;

% partial sums
constraint forall (i in 1..40) (sum([ x[j]*y[i,j] | j in 1..4 ]) = i);

% search
solve::int_search(x, largest, indomain_max, complete) satisfy;

2 comments:

  1. I have added a photo of an old fashioned balance scale. Indeed with a left and right pan to put weights in. I imagine they used something like that.

    ReplyDelete

Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.