untilperfect

Introduction

The untilperfect application solves the buffer preparation vessel sizing and assignment problem using mixed integer linear programming.

The source repo is at https://github.com/multipitch/untilperfect.

Builds are hosted at https://pypi.org/project/untilperfect/.

Documentation is hosted at https://untilperfect.readthedocs.io/.

This project was forked from https://github.com/multipitch/dissertation. The dissertation repo was created for my masters dissertation on the subject towards an MSc in Business Analytics from University College Dublin; further development has been forked here so that the dissertation repo remains frozen.

Install via pip:

$ pip install untilperfect

Provides the untilperfect CLI command

$ untilperfect --help
usage: model.py [-h] [-b BUFFERS] [-n] [-p PARAMETERS] [-f PATH] [-s SOLVER]
                [-t PROBLEM_TYPE] [-v VESSELS] [-w]

Solves the buffer preparation assignment and selection problem.

optional arguments:
-h, --help            show this help message and exit
-b BUFFERS, --buffers BUFFERS
                      buffers filename (default: 'buffers.csv')
-n, --no-plot         do not generate plot
-p PARAMETERS, --parameters PARAMETERS
                      parameters filename (default: 'parameters.ini')
-f PATH, --path PATH  file path (default: <current working directory>)
-s SOLVER, --solver SOLVER
                      solver to be used (default: 'COIN_CMD')
-t PROBLEM_TYPE, --problem-type PROBLEM_TYPE
                      specify model to solve (default: 'complete'), other
                      model options are 'basic', 'minimized_hold_time',
                      'mimimized_used_volume'
-v VESSELS, --vessels VESSELS
                      vessel filename (default: vessels.csv)
-w, --write           write problem to file in .lp format

Distributed under the MIT License.

© Sean Tully 2018-2019.

Contents

Problem definition

The sections below detai lthe “complete” problem. Other problem variants are the “basic” and “minimized hold time” variants, which are discussed afterwards.

Given

_images/explanatory.svg

Data on buffers e.g.

indices names volumes use start times use_durations
n \hbox{--} U_{n} t_{\mathit{USE},n}^{*} \Delta t_{\mathit{USE},n}
0 Buffer #1 5825.23 62.86 39.16
1 Buffer #2 10214.75 79.63 25.5
2 Buffer #3 13995.95 17.6 61.7
3 Buffer #4 14619.52 74.28 44.19
4 Buffer #5 4504.94 29.73 36.0
5 Buffer #6 16361.95 5.5 38.78
6 Buffer #7 3464.09 38.25 57.93
7 Buffer #8 13387.42 11.35 36.55
8 Buffer #9 1064.93 61.21 45.84
9 Buffer #10 1654.58 34.88 22.03
10 Buffer #11 23631.53 26.26 37.99
11 Buffer #12 11546.57 94.15 56.41

Data on available vessels

indices names volumes costs
m \hbox{--} V_{m} c_{m}
0 1000 L 1000.0 63.10
1 2000 L 2000.0 95.64
2 3000 L 3000.0 121.98
3 4000 L 4000.0 144.96
4 5000 L 5000.0 165.72
5 6000 L 6000.0 184.88
6 8000 L 8000.0 219.71
7 10000 L 10000.0 251.19
8 12000 L 12000.0 280.23
9 16000 L 16000.0 333.02
10 18000 L 18000.0 357.41
11 20000 L 20000.0 380.73
12 22000 L 22000.0 403.14
13 25000 L 25000.0 435.28
14 30000 L 30000.0 485.59

And some additional parameters:

parameter symbol value
process cycle time (h) T 96.0
prep pre duration (h) \Delta t_{\mathit{PREP,PRE}} 12.0
prep post duration (h) \Delta t_{\mathit{PREP,POST}} 1.5
transfer duration (h) \Delta t_{\mathit{TRANSFER}} 2.0
hold pre duration (h) \Delta t_{\mathit{HOLD,PRE}} 8.0
hold post duration (h) \Delta t_{\mathit{HOLD,POST}} 1.5
minimum hold duration (h) \Delta t_{\mathit{HOLD,MIN}} 12.0
maximum hold duration (h) \Delta t_{\mathit{HOLD,MAX}} 60.0
vessel minimum fill ratio f_{\mathit{MINUSE}} 0.3
maximum prep utilization f_{\mathit{MAXUSE}} 0.8
max slots P 5

Support formulae:

m \in \mathcal{M}; \quad \mathcal{M} = \left\{ 0, 1, 2, \ldots, m, \ldots,
\left( M - 1 \right) \right\}

n \in \mathcal{N}; \quad \mathcal{N} = \left\{ 0, 1, 2, \ldots, n, \ldots,
\left( N - 1 \right) \right\}

p \in \mathcal{P}; \quad \mathcal{P} = \left\{ 0, 1, 2, \ldots, p, \ldots,
\left( P - 1 \right) \right\}

M = |\mathcal{M}|

N = |\mathcal{N}|

P = |\mathcal{P}|

t_{\mathit{USE},n} = t_{\mathit{USE},n}^{*} \enspace \text{mod} \enspace
T \quad \forall n \in \mathcal{N}

V_{\mathit{MAX}} = \text{max} \left( V_{m} \enspace \forall m \in
\mathcal{M} \right)

\Delta t_{\mathit{PREP}} = \Delta t_{\mathit{PREP,PRE}} +
\Delta t_{\mathit{TRANSFER}} + \Delta t_{\mathit{PREP,POST}}

Minimize

The total (relative) cost of buffer preparation vessels

\boldsymbol{Z} = \sum_{m \in \mathcal{M}} \sum_{p \in \mathcal{P}} c_m
\boldsymbol{y}_{mp}

Subject to

Each buffer must be prepared in a defined slot

\sum_{p \in \mathcal{P}} \boldsymbol{x}_{np} = 1 \quad \forall n \in
\mathcal{N}

Each slot may contain at most one vessel

\sum_{m \in \mathcal{M}} \boldsymbol{y}_{mp} \le 1 \quad \forall p \in
\mathcal{P}

Each vessel must be sufficiently large to prepare allocated buffers

U_{n} \boldsymbol{x}_{np} - \sum_{m \in \mathcal{M}} V_{m}
\boldsymbol{y}_{mp} \le 0 \quad \forall n \in \mathcal{N}, \enspace
\forall p \in \mathcal{P}

Each vessel must be sufficiently small to prepare allcoated buffers

V_{\mathit{MAX}} \boldsymbol{x}_{np} + f_{\mathit{MINFILL}}
\sum_{m \in \mathcal{M}} V_{m} \boldsymbol{y}_{mp} \le U_{n}
+ V_{\mathit{MAX}} \quad \forall n \in \mathcal{N}, \enspace \forall p \in
\mathcal{P}

Each preapration vessel must have a utilization below the maximum utilization limit

\Delta t_{\mathit{PREP}} \sum_{n \in \mathcal{N}} \boldsymbol{x}_{np} \le
f_{\mathit{UTIL}} T \quad \forall p \in \mathcal{P}

The total duration in each hold vessel must be less than the cycle time

\begin{aligned}
    \boldsymbol{z}_{n} \le T - \Delta t_{\mathit{HOLD,PRE}}
    - \Delta t_{\mathit{TRANSFER}} - \Delta t_{\mathit{USE},n}
    - \Delta t_{\mathit{HOLD,POST}}\\
    \quad \forall n \in \mathcal{N}
\end{aligned}

Buffer preparation procedures mustn’t clash with one another

\begin{split}
    \begin{alignedat}{11}
        2&\boldsymbol{w}_{nkp} {}-{} &&\boldsymbol{x}_{np}
        {}-{} && \boldsymbol{x}_{kp} {}&&\le{} &{}-{} 2\\
        &\boldsymbol{w}_{nkp} {}-{} &&\boldsymbol{x}_{np}
        {}-{} && \boldsymbol{x}_{kp} {}&&\ge{} &{}-{} 1\\
    \end{alignedat}
\end{split}
\quad
\begin{split}
    \forall n \in \mathcal{N}, \enspace \forall k \in \mathcal{N}; \;
    k > n, \enspace \forall p \in \mathcal{P}
\end{split}

\begin{split}
    \begin{alignedat}{2}
        T \boldsymbol{q}_{n} - \boldsymbol{z}_{n} &\ge
        - t_{\mathit{USE},n}\\
        T \boldsymbol{q}_{n} - \boldsymbol{z}_{n} &\le
        - t_{\mathit{USE},n} + T\\
    \end{alignedat}
\end{split}
\quad \forall n \in \mathcal{N}

\begin{split}
    \begin{alignedat}{2}
        -T \boldsymbol{q}_{n} + T \boldsymbol{r}_{n} + \boldsymbol{z}_{n}
        &\le t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}}\\
        -T \boldsymbol{q}_{n} + T \boldsymbol{r}_{n} + \boldsymbol{z}_{n}
        &\ge t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}} - T\\
        \end{alignedat}
    \quad \forall n \in \mathcal{N}
\end{split}

\begin{split}
    \begin{alignedat}{2}
        T \boldsymbol{q}_{n} + T \boldsymbol{s}_{n} - \boldsymbol{z}_{n}
        &\le -t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}}\\
        T \boldsymbol{q}_{n} + T \boldsymbol{s}_{n} - \boldsymbol{z}_{n}
        &\ge -t_{\mathit{USE},n} + \Delta t_{\mathit{PREP}} + T\\
        \end{alignedat}
    \quad \forall n \in \mathcal{N}
\end{split}

\begin{split}
    \begin{alignedat}{8}
        &&\boldsymbol{r}_{n} && {}+{} &&\boldsymbol{s}_{n} && {}-{}
        &&\boldsymbol{u}_{n} &\ge 0\\
        &&\boldsymbol{r}_{n} && {}+{} &&\boldsymbol{s}_{n} && {}-{}
        &2&\boldsymbol{u}_{n} &\le 0\\
    \end{alignedat}
    \quad \forall n \in \mathcal{N}
\end{split}

\begin{split}
    \begin{aligned}
        T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} - 2T \boldsymbol{u}_{n}
        + 2T \boldsymbol{v}_{nk} + 2T \sum_{p \in \mathcal{P}}
        \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\
        \le t_{\mathit{USE},n} - t_{\mathit{USE},k}
        - \Delta t_{\mathit{PREP}} + 4T
    \end{aligned}\\
    \begin{aligned}
        T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} + 2T \boldsymbol{u}_{n}
        + 2T \boldsymbol{v}_{nk} - 2T \sum_{p \in \mathcal{P}}
        \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\
        \ge t_{\mathit{USE},n} - t_{\mathit{USE},k}
        + \Delta t_{\mathit{PREP}} - 2T
    \end{aligned}\\
    \begin{aligned}
        T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} - T \boldsymbol{r}_{n}
        + 2T \boldsymbol{u}_{n} + 2T \sum_{p \in \mathcal{P}}
        \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\
        \le t_{\mathit{USE},n} - t_{\mathit{USE},k}
        - \Delta t_{\mathit{PREP}} + 4T
    \end{aligned}\\
    \begin{aligned}
        T \boldsymbol{q}_{k} - T \boldsymbol{q}_{n} + T \boldsymbol{s}_{n}
        - 2T \boldsymbol{u}_{n} - 2T \sum_{p \in \mathcal{P}}
        \boldsymbol{w}_{nkp} - \boldsymbol{z}_{k} + \boldsymbol{z}_{n}\\
        \ge t_{\mathit{USE},n} - t_{\mathit{USE},k}
        + \Delta t_{\mathit{PREP}} - 4T
    \end{aligned}\\
    \begin{aligned}
        \forall n \in \mathcal{N}, \enspace \forall k \in \mathcal{N}; \;
        k > n
    \end{aligned}\\
\end{split}

Where

The following decision variables are specified.

\boldsymbol{q}_{n} \in \left\{0, 1\right\} \quad \forall n \in \mathcal{N}

\boldsymbol{r}_{n} \in \left\{ 0, 1 \right\} \quad \forall n \in
\mathcal{N}

\boldsymbol{s}_{n} \in \left\{ 0, 1 \right\} \quad \forall n \in
\mathcal{N}

\boldsymbol{u}_{n} \in \left\{ 0, 1 \right\} \quad \forall n \in
\mathcal{N}

\boldsymbol{v}_{nk} \in \left\{ 0, 1 \right\} \quad \forall n \in
\mathcal{N}, \enspace \forall k \in \mathcal{N}; \; k > n

\boldsymbol{w}_{nkp} \in \left\{ 0, 1 \right\} \quad \forall n \in
\mathcal{N}, \enspace \forall k \in \mathcal{N}; \; k > n, \enspace \forall
p \in \mathcal{P}

\boldsymbol{x}_{np} \in \left\{ 0, 1 \right\} \quad \forall n \in
\mathcal{N}, \enspace \forall p \in \mathcal{P}

\boldsymbol{y}_{mp} \in \left\{ 0, 1 \right\} \quad \forall m \in
\mathcal{M}, \enspace \forall p \in \mathcal{P}

\Delta t_{\mathit{HOLD,MIN}} \le \boldsymbol{z}_{n} \le
\Delta t_{\mathit{HOLD,MAX}}; \quad
\boldsymbol{z}_{n} \in \mathbb{R} \quad \forall n \in \mathcal{N}

Variant Problems

Basic

The “basic” variant omits the buffer preparation scheduling constraints and as such does not compute a workable schedule. It merely calculates the vessels required to maintain the specified utilization ratio at minimum cost.

Minimized Hold Time

The “minimized hold time” variant involves two rounds of optimization. Firstly, the “complete” problem is solved, resulting in a minimum cost.

Next, the optimum (minimized) cost is set as a constraint:

Z^{\prime} = \min \boldsymbol{Z}
\label{eq.Zprime}

\sum_{m \in \mathcal{M}} \sum_{p \in \mathcal{P}} c_m \boldsymbol{y}_{mp}
= Z^{\prime}

Then the problem is re-run with the following objective to be minimized:

\boldsymbol{Y} = \sum_{n \in \mathcal{N}} \boldsymbol{z}_{n}

Nomenclature

Symbol Description
\boldsymbol{a}_{nk} buffers n and k prepared in same vessel (binary)
c_{m} (relative) cost of vessel m
f_{\mathit{MAXUSE}} buffer maximum use duration ratio
f_{\mathit{MINFILL}} vessel minimum fill ratio
f_{\mathit{MINUSE}} buffer minimum use duration ratio
f_{\mathit{UTIL}} preparation slot maximum utilisation ratio
k secondary buffer index \left( k \in \mathcal{N}, k \ne n \right)
m vessel size index \left( m \in \mathcal{M} \right)
n buffer index \left( n \in \mathcal{N} \right)
p slot index \left( p \in \mathcal{P} \right)
\boldsymbol{q}_{n} the buffer n hold operation crosses the single-cycle boundaries (binary)
\boldsymbol{r}_{n} \boldsymbol{t}_{\mathit{LOWER},n} occurs before \boldsymbol{t}_{\mathit{PREP},n} in the single-cycle window (binary)
\boldsymbol{s}_{n} \boldsymbol{t}_{\mathit{UPPER},n} occurs after \boldsymbol{t}_{\mathit{PREP},n} in the single-cycle window (binary)
\boldsymbol{t}_{\mathit{LOWER},n} lower bound of feasible scheduling region for all buffers k > n with respect to buffer n
\boldsymbol{t}_{\mathit{PREP},k} preparation reference time for buffer k
\boldsymbol{t}_{\mathit{PREP},n} preparation reference time for buffer n
\boldsymbol{t}_{\mathit{UPPER},n} upper bound of feasible scheduling region for all buffers k > n with respect to buffer n
t_{\mathit{USE},n} buffer n time of first use, normalised
t_{\mathit{USE},n}^{*} buffer n time of first use, un-normalised
\Delta t_{\mathit{FEAS}} maximum feasible buffer use duration
\Delta t_{\mathit{HOLD,MAX}} maximum allowable buffer hold duration
\Delta t_{\mathit{HOLD,MIN}} minimum allowable buffer hold duration
\Delta t_{\mathit{HOLD,POST}} duration of post-use operations in buffer hold procedures
\Delta t_{\mathit{HOLD,PRE}} duration of operations prior to receiving buffer in buffer hold procedures
\Delta t_{\mathit{PREP}} total duration of buffer preparation procedures
\Delta t_{\mathit{PREP,POST}} duration of operations post transferring out buffer in buffer preparation procedures
\Delta t_{\mathit{PREP,PRE}} duration of operations prior to transferring out buffer in buffer preparation procedures
\Delta t_{\mathit{USE},n} duration of use of buffer n
\Delta t_{\mathit{TRANSFER}} duration of transfers from buffer preparation vessel to buffer hold vessel
\boldsymbol{u}_{n} feasible scheduling window for buffer k with respect to buffer n does not cross cycle boundary (binary)
\boldsymbol{v}_{nk} feasible scheduling window for buffer k with respect to buffer n occurs before buffer n preparation procedure (binary)
\boldsymbol{w}_{nkp} distinct buffers n and k are both made in slot p (binary)
\boldsymbol{x}_{np} buffer n is prepared in slot p (binary)
\boldsymbol{y}_{mp} a vessel of size m is in slot p (binary)
\boldsymbol{z}_{n} buffer n hold duration
M number of vessel sizes
\mathcal{M} set of vessel sizes
N number of buffers
\mathcal{N} set of buffers
P number of slots
\mathcal{P} set of slots
T process cycle time (start–to–start duration)
U_{n} volume of buffer n to be prepared
V_{m} maximum working volume of vessel size m
V_{\mathit{MAX}} largest maximum working volume of available vessel sizes
\boldsymbol{Y} secondary objective; sum of buffer hold times, given minimal total vessel cost
\boldsymbol{Z} primary objective; total vessel cost
Z^{\prime} minimal total vessel cost

untilperfect package

Submodules

untilperfect.cli module

cli.py

Command line interface for untilperfect.

untilperfect.cli.main()[source]

Provides command line interface to untilperfect.

Returns:Status. See pulp.LpStatus.
Return type:int
untilperfect.iotools module

iotools.py

Tools for reading and writing of files.

untilperfect.iotools.column_reader(filename)[source]

Reads columnar data from csv file.

untilperfect.iotools.get_config_section(filename='config.ini', section='DEFAULT')[source]

Reads a section from a configuration file.

untilperfect.model module

model.py

This module contains the definition of the buffer preparation vessel assignment problem along with classes for Parameters, Buffers and Vessels. It also contains a function for solving the problem.

class untilperfect.model.BufferPrepProblem(parameters, buffers, vessels, solver=None)[source]

Bases: object

Determines the optium selection and assignment of prep vessels.

Parameters:
  • parameters (untilperfect.Parameters) –
  • buffers (untilperfect.Buffers) –
  • vessels (untilperfect.Vessels) –
  • solver (None or pulp.LpSolver, optional) –
basic(do_solve=True)[source]

Solve basic problem (no scheduling) to minimize cost.

Parameters:do_solve (bool, optional) – If set to True (default), solves the problem upon construcion. Set this parameter to false to defer solution (useful if other constraints are to be applied before solving).
Returns:If do_solve is set to True, returns problem status (see pulp.LpStatus).
Return type:int
complete(do_solve=True)[source]

Solve complete problem (includes scheduling) to minimize cost.

Parameters:do_solve (bool, optional) – If set to True (default), solves the problem upon construcion. Set this parameter to false to defer solution (useful if other constraints are to be applied before solving).
Returns:If do_solve is set to True, returns problem status (see pulp.LpStatus).
Return type:int
evaluate(problem_type)[source]

Generate some useful data from a solved problem.

minimized_hold_time()[source]

Solve complete problem to first minimize vessel cost, then minimize hold times subject to the minimum cost.

Returns:If do_solve is set to True, returns problem status (see pulp.LpStatus).
Return type:int
minimized_used_volume()[source]

Solve complete problem to first minimize vessel cost, then minimize used preparation volume, subject to minimum cost, finally, minimize hold times, subject to minimal cost and minimal used preparation volume.

Returns:If do_solve is set to True, returns problem status (see pulp.LpStatus).
Return type:int
plot(filename='single_cycle_plot.svg')[source]

Create a single-cycle steady-state equipment occupancy plot.

Parameters:filename (str, optional) – Plot file name.
write(filename='untilperfect.lp')[source]

Write problem to file in .LP format.

Parameters:filename (str, optional) – Output file name.
class untilperfect.model.Buffers(data)[source]

Bases: untilperfect.model.Data

Selection of buffers to be prepared.

Parameters:data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Data class instance. The filename should be that of a valid data file (csv format).
set_relative_use_start_times(cycle_time)[source]

Calculates use start times relative to cycle.

Parameters:cycle_time (float) – Process cycle time.
class untilperfect.model.Data(data)[source]

Bases: object

Parent class of ‘Buffers’ and ‘Vessels’. If initialized with a ‘dict’, reads data from the ‘dict’. If initialized with a ‘str’, treats it as a filename and reads data from the file.

Parameters:data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Data class instance. The filename should be that of a valid data file (csv format).
class untilperfect.model.Parameters(data)[source]

Bases: object

Problem parameters.

Parameters:data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Parameters instance. The filename should be that of a valid parameters file; in ini format and with a [parameters] section.
class untilperfect.model.Vessels(data)[source]

Bases: untilperfect.model.Data

Selection of preparation vessels available for use.

Parameters:data (str or dict) – Pass either a filename string or a dict of parameters to initialize a Vessels class instance. The filename should be that of a valid data file (csv format).
untilperfect.model.solve(parameters_file='parameters.ini', buffers_file='buffers.csv', vessels_file='vessels.csv', problem_type=<function BufferPrepProblem.complete>, solver=None, plot=True, write=True, cli=False)[source]

Solve BufferPrepProblem.

Parameters:
  • parameters_file (str, optional) – Parameters filename.
  • buffers_file (str, optional) – Buffers filename.
  • vessels_file (str, optional) – Vessels filename.
  • problem_type (optional) – Type of problem to solve.
  • solver (optional) – Solver to use; see pulp.LpSolver
  • plot (bool, optional) – Generate steady-state single-cylce equipent occupancy plot and save to file.
  • write (bool, optional) – Write the problem to file in .lp format.
  • cli (bool, optional) – Set to True to return problem status, returns problem object otherwise.
Returns:

If cli=True, returns status (int, see pulp.LpStatus), if cli=False, returns pulp.LpProblem instance.

Return type:

int or pulp.LpProblem

untilperfect.plots module

plots.py

This module contains functions to plot results.

untilperfect.plots.cyclic_xranges(start_time, duration, cycle_time)[source]

Where a range crosses the cycle time boundary, split into 2 ranges.

Parameters:
Returns:

List of operation time ranges.

Return type:

list

untilperfect.plots.explanatory_plot(filename='explanatory.svg')[source]

Plot that explains duration parameters.

untilperfect.plots.label_style(label)[source]

Wrapper to encode labels in latex format if this setting is active.

Parameters:label (str) –
Returns:
Return type:str
untilperfect.plots.matplotlib_init()[source]

Change some matplotlib settings.

untilperfect.plots.single_cycle_plot(problem, filename=None)[source]

Generate a single-cycle steady-state equipment occupancy plot.

Parameters:
  • problem (untilperfect.Problem) –
  • filename (str or None, optional) – If a filename string is specified, saves plot to file, otherwise opens plot in a tk window.
untilperfect.pulptools module

pulptools.py

This module contains a class to handle multidimensional variables in pulp.

class untilperfect.pulptools.LpVariableArray(name, dimensions, low_bound=None, up_bound=None, cat=None, e=None)[source]

Bases: object

Multidimensional decision variable array.

evaluate()[source]

Evaluates decision variable values.

Module contents

init.py

Indices and tables