2
$\begingroup$

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

Problem

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

Update.

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

$\endgroup$

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.