## Sunday, March 6, 2016

### The Weight Problem of Bachet de Meziriac

In a comment in this post there was a question about the Weight Problem of Bachet de Meziriac.

 From this description: A merchant had a forty pound weight that broke into four pieces as a result of a fall. When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integer weight between 1 and 40 pounds. What were the weights of the pieces? This problem comes from the French mathematician Claude Gaspard Bachet de Méziriac (1581-1638) who solved it in his famous book Problèmes plaisants et délectables qui se font par les nombres, published in 1624. We assume a balance scale where we can place weights in the  left or right pan like: Photo by Nikodem Nijaki (Own work) [CC BY-SA 3.0], via Wikimedia Commons
##### MINLP formulation

A first simple MINLP formulation can look like:

The variable $$\delta_{i,k} \in \{-1,0,+1\}$$ indicates whether we place the weight $$i$$ on the left or the right scale during trial $$k$$. Of course the equation Check is non-linear, so we need to solve this with a MINLP solver. The non-convexity we introduced requires a global MINLP solver such as Baron or Couenne. This formulation is probably similar to how one would formulate things for use with a Constraint Programming solver.

##### CP (Constraint Programming) formulation

Indeed a CP formulation in Minizinc can be found on Paul Rubins blog. CP solvers typically have no problem with many types of non-linearities as long everything stays integer-valued (CP solvers have limited support for continuous variables).

##### MIP formulation

It is not too difficult to make a MIP model from this. The linearization of the multiplication of a binary variable times a continuous variable is well known:

 \boxed{\begin{align}&y= \delta \cdot x\\ &\delta\in\{0,1\}, x\ge 0 \end{align}} $\>\>\Longleftrightarrow\>\>$ \boxed{\begin{align} & y\le \delta M\\ & y\le x\\ & y\ge x-M(1-\delta)\\ & \delta \in\{0,1\},x,y \ge 0 \end{align}}

Here $$M$$ is a tight upper-bound on $$x$$.

Instead of $$\delta_{i,k} \in \{-1,0,+1\}$$ we now use $$\delta_{i,k,lr} \in \{0,1\}$$ where $$lr=\{left,right\}$$. We don’t want to place the same weight on the left and right scale, so we add the constraint $$\delta_{i,k,’left’}+\delta_{i,k,’right’}\le 1$$. Note that this constraint is not really needed: the final result would not change if we left this constraint out.  Here are the changes to the model:

We also added the Order constraint: $$x_{i+1}\le x_i$$. This gives a nicer display of the results but also reduces symmetry. This can make large models (much) easier to solve.

##### Results

The final result is:

 ----     40 VARIABLE x.L  the four weights w1 27,    w2  9,    w3  3,    w4  1

The MINLP solvers Baron and Couenne do actually pretty good on the MINLP version of this model.