Written by: Paul Rubin
Primary Source: OR in an OB World
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.
% 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;