Edit on GitHub

GuillotineModels.jl

The main utility of this package is to enable researchers to reproduce results for the FMT formulation from 10.1287/ijoc.2016.0710, and the enhanced formulation from https://arxiv.org/abs/2111.06348 (final link to be updated). This can be done without knowledge of julia programming by means of the script gmodels which is explained in the README.md. However, the package also makes available a trove of utility functions related to the solving of the G2KP and related problems (G2MKP, G2CSP, G2OPP). Here we give a short code walkthrough from someone interested in writing Julia code that makes use of the package functions directly.

The code is divided into the following modules:

  • GuillotineModels – The main module. The most important types and functions pertain to this module, and are fully described at the end of this page.
  • GuillotineModels.CommandLine – The module used to implement the gmodels script, which is basically just a call to run. Most of the other functions in the module are only relevant to someone extending the run command. The only exception is round_instance which may be used to divide all values from a problem instance by some factor.
  • GuillotineModels.CommandLine.SolversArgs – The module responsible for the interface between the rest of the code and GLPK.jl, CPLEX.jl, Gurobi.jl, and Cbc.jl. It only interests someone trying to extend the set of supported solvers.
  • GuillotineModels.Utilities – The module aggregates the functions that are needed by one or more of other submodules but that do not are directly related to the package purpose. For example, relax! and restore! which help to change variables from binary/integer to continuous and back, or optimize_within_time_limit! which calls JuMP.optimize! but first checks for timeout and also changes the model object to respect the remaining time before timeout. The user may need to import the SortedLinkedLW if they want to work directly with GuillotineModels.PPG2KP.Enumeration.gen_cuts.
  • GuillotineModels.Utilities.Args – The module implements the type Arg widely used in GuillotineModels.CommandLine to represent command-line options/flags. Necessary only for understanding how to extend GuillotineModels.CommandLine with more options.
  • GuillotineModels.Data – Module responsible for all functions related to instance-reading. Useful for any user that intends to read the instances themselves, instead of relying on GuillotineModels.CommandLine.run. The multiple methods of function read_from_string are the most relevant contribution of the module. The read_from_file function is a convenience that just reads the whole content of a file and calls read_from_string over it. It also provides some limited instance writing capabilities.
  • GuillotineModels.SaveModel – The module provides a function write_to_file that saves JuMP models to some file format. The module was developed because the MathOptInterface.write_to_file was inneficient when saving large models to MPS files. The GuillotineModels.SaveModel.write_to_file tries to call the annexed solver internal machinery to save the model to the desired format and, if this is not possible, it fallbacks to using the MathOptInterface method (which does not rely on the solver, but instead inspects the JuMP.model object and create the formatted output itself).
  • GuillotineModels.PPG2KP – The module that implements the two formulations previously mentioned. For most users, the only interesting methods are the implementations of GuillotineModels.build_model for the formulations mentioned.
  • GuillotineModels.PPG2KP.Heuristic – The module implements the 2-stage guillotine heuristic used in the pricing of 10.1287/ijoc.2016.0710 (the heuristic is first presented in 10.1016/j.cor.2010.12.018). The module can, therefore, be useful to an user interested in a simple heuristic for the G2KP for MIP-start, adding lower bound constraints, or gauging the quality of a model solution.
  • GuillotineModels.PPG2KP.Enumeration – The module implements the plate enumeration needed by both mainly supported formulations. The module is of little interest for the average user, but gen_cuts may be used to directly generate the list of all plates, cuts, and piece extractions without needing to build the model itself.
  • GuillotineModels.Flow{.Format,.Enumeration} – The submodule Flow and its submodules implement an unpublished formulation of little success. The module is kept for historical reasons. The only supported problem is G2KP and each component of an instance (lengths, widths, ...) needs to be given separatedely.

To complement the walkthrough above, we also point out the small collection of code examples in the /examples folder of the GuillotineModels.jl package.

  • create_and_solve_PPG2KP_model.jl – Create an FMT model (10.1287/ijoc.2016.0710) for a small instance and solve it, without using GuillotineModels.CommandLine.run.
  • instance_converter.jl – Example on how to extend GuillotineModels.Data.write_to_file. Reads a Classic_G2KP instance file and save it in the CPG_SLOPP format.
  • run_discretization.jl – Calls GuillotineModels.PPG2KP.Enumeration.gen_cuts directly and print some info about the descretization of a small instance.
  • run_heuristic.jl – Takes an instance in the Classic_G2KP format and run both the unoptimized and the optimized versions of the Guillotine 2-stage heuristic from GuillotineModels.PPG2KP.Heuristic over it. Shows the solution and the timings.

For a better understanding on how to deal with already built models we suggest reviewing the JuMP documentation for version 0.21.5.

The code heavily relies on parametric types, both for templated type and method signatures. Most of the cases, the type parameters are named D, S , P. The three are expected to be concrete subtypes of Integer. The D represents the type used to store piece demand (should be large enough to store the sum of all pieces demand). The S represents the type used to store the pieces size (should be enough to store the sum of all pieces length or width). The P represents the type used to store profit (or area, should be large enough to store the original plate area or the sum of all piece profits, whichever is the largest).

GuillotineModels.GuillotineModels — Module

GuillotineModels is a collection of mathematical models for 2D Guillotine Cutting problems, all implemented using Julia+JuMP.

It was developed as part of the PhD thesis of Henrique Becker.

The main features are:

  1. The implementation of distinct models using the same technology (Julia+JuMP) which is solver-agnostic.
  2. The implementation of a CommandLine interface that make it easy to call the implemented models from the command-line to be solved by an specified solver, and also is extendable for new models and solvers.
source
GuillotineModels.CutPattern — Type

A guillotine stage-unlimited unrestricted cutting pattern.

  • length::Any

    The length of the pattern.

  • width::Any

    The width of the pattern.

  • piece_idx::Any

    If the pattern represents a piece, then the piece index; otherwise zero.

  • cuts_are_vertical::Bool

    The common orientation of the cuts between the plates in subpatterns.

  • subpatterns::Array{CutPattern{D,S},1} where S where D

    The subpatterns that constitute the pattern.

Notes

  • cuts_are_vertical is only relevant if subpatterns has length two or more.
  • If subpatterns is non-empty, and cuts_are_vertical == true, then the sum of the width of the patterns in subpatterns cannot be greater than width, and each individual length of a pattern in subpatterns cannot be greater than length. If cuts_are_vertical == false the same applies except length and width switch roles.
  • It is assumed that zero is not a valid piece index, as it is used in piece_idx to mark that a pattern is not sold as a piece (in this case, it is either a cut pattern or waste).
  • If piece_idx has a value different from zero, then subpatterns must be empty. In other words, a piece cannot be subdivided.
  • Waste may be represented explicitly, by having plates with piece_idx == 0 but no elements in subpatterns, or implicitly, by having elements in subpatterns that do not fill all the area defined by length and width.
source
GuillotineModels.build_model — Function
build_model(problem, formulation, instance, model[, options])

Given an instance of problem, build formulation inside model.

A dict of options that are problem- and formulation-specific may be also provided (otherwise defaults are used).

Should always return two values: the first is always an element of BuildStopReason; the second is problem- and formulation-specific.

Arguments

  1. problem: An object that identifies the problem being solved, e.g., Val(:G2KP). Each problem often requires a different instance type but sometimes an instance of a more general problem (that is not using the extra generality) may be passed to a more specific problem.
  2. formulation: An object that identifies the formulation used to model the problem, e.g., Val(:PPG2KP). Often same formulation can be adapted to multiple different problems with minimal changes.
  3. instance: An object containing the problem data, e.g., G2KP or SLOPP.
  4. model: An object that behaves as a JuMP model, it will have variables and constraints added to it.
  5. options::Dict{String, Any}: Problem- and formulation-specific options.

Returns

  1. ::BuildStopReason: The reason for which the method returned. It can be: BUILT_MODEL (the model was built successfully) or FOUND_OPTIMUM (in the process of building the model, the optimal solution was already found, so the building process was abandoned). See get_cut_pattern for more information.
  2. ::Any: the specific type of the second returned value depends on the problem and formulation, however it should always exist (even if it is nothing). It is passed as an argument to get_cut_pattern in order to assemble a solution (CutPattern) from the variables values of a model.
source
GuillotineModels.get_cut_pattern — Function
get_cut_pattern(problem, formulation, model, build_model_return)

Given a model built with build_model(problem, formulation, ...) and its respective build_model_return (i.e., the second return of build_model), returns a CutPattern representing the optimal solution found. If the first return of build_model is BUILT_MODEL, then the model needs to be solved before calling this method; however, if it is FOUND_OPTIMUM then the model does not need to be solved.

The implementation of this method is responsability of whoever implemented the corresponding build_model method.

The D and S type parameters from CutPattern{D, S} are inferred from build_model_return as of now.

If build_model returns nothing then model somehow needs to contain all information needed to build the CutPattern. Note that the problem instance (l, w, L, W, ...) is not passed to this method, consequently, a common pattern is to have build_model return a struct containing the problem instance and the auxiliary tables used to build the model (especially the ones associating variables with dimensions or piece indexes).

The solutions of some problems are not a single CutPattern but instead multiple CutPatterns inside an iterable collection of them (often a Vector).

See also: build_model

source
GuillotineModels.simplify! — Method
simplify!(p :: CutPattern{D, S}) :: CutPattern{D, S} where {D, S}

This method is free to make any changes while keeping all the packed pieces and the the validity of the solution, its purpose is to make the structure easier to understand by human beings. If you are trying to debug a model you will probably want to see both the simplified and not simplified output. The simplified will make it easier to understand the solution itself, and the non-simplified will show peculiarities that given insight on how the model works/'see things' internally.

NOTE: the returned pattern is not always the given parameter, in some rare cases (a root plate with a single piece inside) the pattern returned may be another object.

NOTE: this method does not create any new CutPattern objects but instead prunes and rearranges the pattern tree (i.e., throws away some objects and changes the position of others in the tree).

source
GuillotineModels.solution_value — Function
solution_value(problem, instance, solution)

Return the value of solution for problem and instance.

The returned value is often an Int. If the solution (i) was extracted from a model with a valid primal solution and (ii) the model correctly computed the objective function, then the value returned by this function should match the value of the objective function in the model from which the solution was extracted. Basically, this function serves as a formulation-agnostic double-check of the obtained solution value.

solution is something returned by get_cut_pattern so often it is either a Vector{CutPattern{D, S}} or a single CutPattern{D, S}.

!!! This function does not check the validity of the given solution, it assumes a valid solution and just compute the value it would have if it was valid.

source
GuillotineModels.to_pretty_str — Method
to_pretty_str(p :: CutPattern{D, S}; kwargs...) :: String

Creates a simplified and indented string representing the CutPattern.

Format

The format represents pieces as "piece_idxplengthxwidth" (e.g., "1p10x20" is a copy of piece 1 which have length 10 and width 20); non-piece patterns are represented by "Plengthxwidth" (note the P is uppercase); if the non-piece pattern has subpatterns (i.e., is not waste) then it starts a set of vertical (horizontal) cuts with [ ({) and close it with ] (}). There is always whitespace between the elements of such sets but, for conciseness and ease of reading, if all the elements of a subpattern have no children they are separated by single spaces (no matter how long the list), otherwise they are separated by newlines.

Keyword Arguments

  • lvl :: Int64: The current level of indentation.
  • indent_str: The string or character to be repeated as indentation.
source
GuillotineModels.to_rectangles — Method
to_rectangles(p :: CutPattern{D, S}[, x, y])

Returns a Vector with a normalized spatial positioning of pieces and plates.

The returned value is a Vector{Tuple{D, NTuple{4, S}}}, the first value is the piece/plate piece_idx, the second is a quadruplet (xo, yo, xf, yf) (i.e., the origins and the final coordinates in each dimension).

source
GuillotineModels.to_tikz_picture — Method
to_tikz_picture(p :: CutPattern{D, S}) :: String

Creates a String with tikz code representing the CutPattern.

This is the same as to_tikz_rectangles but wraps the rectangles inside a "\begin{tikzpicture} ... \end{tikzpicture}" environment (i.e., the first and last lines are environment declarations).

source
GuillotineModels.to_tikz_rectangles — Method
to_tikz_rectangles(p :: CutPattern{D, S}) :: String

Creates a String with tikz \draw commands representing the CutPattern.

The tikz code has nodes indicating the piece indexes (waste pieces are not labeled because we do not distinguish between the waste pieces and the intermediary plates yet). The same node command is also outputted commented and with the size of piece, for easy alternance between these two informations.

source