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? 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.

## No comments:

## Post a Comment