Need help with building constraints

Specific Domains Optimization (Mathematical)
1

I am trying to fit images to A4 piece of paper, I am getting infeasible solution but I don’t understand why.

  params = Dict()
  params["ROWS"] = 1:297
  params["COLS"] = 1:210
  params["TOTAL"] = 210 * 297

  params["IMAGES"] = Dict{String,Dict{String,Any}}([
    "1" => Dict(["w"=>50, "h" => 70, "rotate" => 0]),
    "2" => Dict(["w"=>30, "h" => 20, "rotate" => 0]),
    "3" => Dict(["w"=>100, "h" => 50, "rotate" => 0]),
    "4" => Dict(["w"=>90, "h" => 60, "rotate" => 0]),
    "5" => Dict(["w"=>20, "h" => 90, "rotate" => 0]),
    "6" => Dict(["w"=>100, "h" => 120, "rotate" => 0]),
    "7" => Dict(["w"=>40, "h" => 70, "rotate" => 0])
  ])


  premex = Model()

  _ROWS = params["ROWS"]
  _COLS = params["COLS"]
  _IMAGES = params["IMAGES"]
  _TOTAL = params["TOTAL"]

        @variable(premex, ASSIGNed[R in _ROWS, C in _COLS, i_k in keys(_IMAGES)], Bin)

    @objective(
      premex,
      Min,
      _TOTAL - sum((ASSIGNed[R, C, i_k]) 
          for R in _ROWS, C in _COLS, (i_k, i) in _IMAGES)
    )
      @constraint(
        premex,
        [R in _ROWS, C in _COLS],
        [ASSIGNed[R, C, i_k] for (i_k, i) in _IMAGES] in SOS1()
      )

      **@constraint(**
**        premex,**
**        [i_k in keys(_IMAGES), R in _ROWS],**
**        sum(ASSIGNed[R, C, i_k] for C in _COLS) == _IMAGES[i_k]["w"]**
**      )**

**      @constraint(**
**        premex,**
**        [i_k in keys(_IMAGES), C in _COLS],**
**        sum(ASSIGNed[R, C, i_k] for R in _ROWS) == _IMAGES[i_k]["h"]**
**      )**

bolded ones are problematic, I wanted to make some constraints that will say: the sum of all width that are chosen must match with the actual images sizes

2

This is exactly in my area, as I work with MIP models for packing 2D objects inside of other 2D objects.

It would help if your code was reproducible, for example, the _ROWS, _COLS, _TOTAL and the like are not defined. The person that is trying to help you should not have to edit them to refer to the correct syntax to accessing the Dict elements. Also, the bold does not work inside a code area (the triple backticks) so comment the constraints and refer to them as the commented constraints instead of using asterisks.

Are you trying to use some model of the literature? I do not recognize the formulation at first.

Are you sure the problematic constraints are correct? Should you not be checking if the sum of the width (length) of the images chosen is smaller than or equal to the width (length) of the sheet you are trying to put they inside?

5 Likes
3

I’ve added missing variables to the problem above just now.

I don’t use any formulation from literature, I am trying to figure it out by myself with help from you :smile:

I would start by defining the decision variable ROWS (note: this is NOT the above problem, this is a new approach) because that is a continuous sheet of paper that will be cut when we pack all the images too.

Next, I would define an ASSIGNed variable, that would have ROWS, COLS, and image key dimensions.

But now I face a difficulty: how to define ASSIGNed decision variable that depends on another decision variable ROWS?

4

I suppose this is a learning exercise then?

How the cuts will happen? They need to go from one side of the side to the other (i.e., like you were using a ruler or guillotine), or will you cut their borders exactly with a blade (i.e., without affecting anything but the border of the image)?

You say to me that ROWS will not be only a param but also a variable (please, use distinct names for parameters and variables) and how it will interact with already existing variable ASSIGNed, well to answer that I need to know what ROWS will mean. ROWS (variable) will be indexes by which sets? Will it be binary? What will mean if it has value zero, or if has value one?

Outside of that, I can only comment in the formulation that is in the original post. There is many strange details in it:

  1. It seems the objective function tries to minimize the unused area (as _TOTAL is a constant representing the area of a sheet), but you are not subtracting area values from it but instead how many assignments were made. The result is that you are trying to maximize the number of assigned images (what is similar, but not the same, unless all images share the same area).
  2. The first constraint makes some sense, you want that no two images share the same assigned position. This is good and correct, but unless the images have size 1x1 they should be blocking other adjacent positions, not only a single 1x1 square.
  3. In the “bolded” constraints, you a sum of booleans in the left side (the assigned binary variables), and a length in the right side (the image width or length). So it is not clear what you wanted there. Also, this seems to expect that each image is in all rows and all columns which does not make much sense.
1 Like
5

Thanks for your reply.

Cuts will do later, sure there will have to be some space between images.

Rolls of paper/canvas will have fixed with, but the length will be infinitive with a restriction of some length per roll. As we can have unlimited images and we have to place them all. I hope you can understand this :grinning:

Imagine paper/canvas as grid of millimeters. So every millimeter will have one image assigned to it thus why assigned[row, col, image] = 0 or 1

I dealt with only one image assigned to one cell with SOS1()

Now for me is logical that sum(assigned) == width * length of all images, but it doesn’t work - I am getting infeasible solution. But maybe it is not enough for solver to make a decision.

I will have to make constraint with neighboring cells to hold the same image until it fit completely on canvas.

Do you have any example that can help me with this?

Thanks again for your help!

6

Most formulations, in fact, do consider no space between packed items. It is not the best solution (but maybe the easiest one): start with a formulation that expects no space and then slightly increase all items to account for the borders.

the length will be infinitive with a restriction of some length per roll

Do you mean there are unlimited rolls of a finite length? Because a infinite finite length does not make much sense. The unlimited images is also not very clear. You can have an arbitrary amount of images, but not an infinite one, otherwise you will never stop packing, unless you are describing an “online variant” that will continuously receive images and output packings in rolls (so the input will never stop, but the output does not need to stop all the input).

Ok. This is very similar to one model of the literature. The problem here is that I see no way other constraint in your code to force these 1x1 millimeter squares to contiguously pack the image. Unless you are making a jigsaw puzzle and bits of the image of them may be scattered over all the sheet then you are not really packing them. Maybe this is what you mean by “I will have to make constraint with neighboring cells to hold the same image until it fit completely on canvas.”

This is actually correct, if the sheet is large enough to contain all images. However, this is not what your constraints try to do. You can do this in a single constraint but you have two sets of “bold” constraints, one for rows and other for columns, each set with a different constraint for each combination of image and position (in row or col). It would be something like:

@constraint(premex,
    params["TOTAL"] ==
    sum(ASSIGNed[R in _ROWS, C in _COLS, i_k in keys(_IMAGES))
)

Again this only guarantees the area makes sense, but does nothing in relation to avoiding the images to be partitioned like a jigsaw puzzle.

1 Like
7

Do you mean there are unlimited rolls of a finite length? Because a infinite finite length does not make much sense. The unlimited images is also not very clear. You can have an arbitrary amount of images, but not an infinite one, otherwise you will never stop packing, unless you are describing an “online variant” that will continuously receive images and output packings in rolls (so the input will never stop, but the output does not need to stop all the input).

Well, you are right - all values have finite values, but the length should be calculated by the system. For example, if we have 100 orders during last night then those 100 images should be fitted on 1 (or more) canvases the best way possible. From that point, I don’t have a finite length so the system has to be built without it. The only thing that will constraint this is the actual length of the canvas itself.

The problem here is that I see no way other constraint in your code to force these 1x1 millimeter squares to contiguously pack the image.

This should be similar to simulation, somehow I have to force the model to value the most first rows and less the last, also when the model decides to assign the first grid to an image it has to automatically assign all other adjusted grids to the image size.

Do you know any similar model so you can share it with me?

8

I am not sure if you want a Bin Packing formulation, so you have an unlimited amount of canvas, and you want to discover a packing that minimizes the number of canvas you use. Or you want a Strip Packing formulation, in which you have a single canvas/roll that is surely lengthier than all images one after the other, but you want to minimize the length of this roll that is used to pack the images.

Define this mathematically, I cannot suggest you a model if I do not know what is a better and what is a worst way.

I am almost sure I have already seen a model like you are trying to do in the literature, but I am not finding it. The main difference from your model is that each variable indicates if the left-bottom corner of a image was positioned in that coordinate, and there are constraints that prohibit all other variables up to y positions up and x positions left to assume a non-zero value (where x and y are the size of that image). I think maybe it was a 3D model, because of this I am not finding it in my last bibliographical revision.

If you wanna give a look to state-of-the-art models for similar problems I suggest looking at the Section 6 (page 16) of this very recent and very good survey. Section 2 describes all kind of problems in the literature and their names, so maybe them help you to find the name for what you want.

9

left-bottom corner

this is also nice, if I could work with bottom corners left or right…

very recent and very good survey.

this is the survey I stubble upon today too!

I will have to learn more about what I can do with Julia also, because knowing the tool can mean a lot when dealing with this kind of tasks.

Thank you and have a good night

10

Thank you. Any further questions just ask.