Backgroud. I'm reading papers about cutting stock problem (CSP).

  1. Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse (2008)
    Characterization and modelling of guillotine constraints.
    European Journal of Operational Research 191 (2008) 112–126.
  2. D.A. Wuttke, H.S. Heese (2017) Two-dimensional cutting stock problem with sequence dependent setup times, European Journal of Operational Research


There is a square canvas, the side of the canvas is $n\times a$.

It is required to cut this canvas into $n^2$ equivalent squares with the side, $a$.

For $n = 3$, we can easily get the solution: $9$ squares with the side $a_1=a_2=...=a_9=a$, where $a_i$ the side of $i$-th square, $i \in I = \{1,2,\ldots, n^2\}$. If we remove any square, we will have a classic $8$-puzzle (left figure below, $n=3$).

enter image description here

At first, let us now omit the constraint on squares' side size, they can be different: $$a_1 <a_2 <... <a_i <... <a_{n ^ 2}. \tag{1}$$

At second, let us add the following constraints on squares' sides (right figure above, $n=3$):

  1. The sum of any two consecutive elements of the set $(1)$ must be greater the following element.

  2. Any element of the set $(1)$ must be less than half of the canvas, $n\times a$.

  3. The first element of the set $(1)$ must be greater than the half of equivalent solution, $a$.

The task is to prove:

a) the problem will have a solution (integer or real),

b) the solution is $(n^2-1)$-puzzle.

Question. How to setup a model for an optimization problem?

My attempt is:

I think I have a case of guillotine cutting stock problem.

I have tried to write the constrains (C1)-(C3):

$$ s.t. \left\{% \begin{array}{ll} a_ {i + 2} < a_i + a_ {i + 1} ,& i = 1,2, ..., n ^ 2-2; \\ a_i <\frac{n\times a}{2}, & \forall i \in I; \\ 0 < a/2 < a_1. \\ \end{array}% \right.$$


Here is the list of software (see at bottom of page) to design, test, and solve your own original sliding block puzzles.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.