text:
# Time Series Analysis by State Space Methods statespace¶

statsmodels.tsa.statespace contains classes and functions that are useful for time series analysis using state space methods.

A general state space model is of the form

$\begin{split}y_t & = Z_t \alpha_t + d_t + \varepsilon_t \\ \alpha_{t+1} & = T_t \alpha_t + c_t + R_t \eta_t \\\end{split}$

where $$y_t$$ refers to the observation vector at time $$t$$, $$\alpha_t$$ refers to the (unobserved) state vector at time $$t$$, and where the irregular components are defined as

$\begin{split}\varepsilon_t \sim N(0, H_t) \\ \eta_t \sim N(0, Q_t) \\\end{split}$

The remaining variables ($$Z_t, d_t, H_t, T_t, c_t, R_t, Q_t$$) in the equations are matrices describing the process. Their variable names and dimensions are as follows

Z : design $$(k\_endog \times k\_states \times nobs)$$

d : obs_intercept $$(k\_endog \times nobs)$$

H : obs_cov $$(k\_endog \times k\_endog \times nobs)$$

T : transition $$(k\_states \times k\_states \times nobs)$$

c : state_intercept $$(k\_states \times nobs)$$

R : selection $$(k\_states \times k\_posdef \times nobs)$$

Q : state_cov $$(k\_posdef \times k\_posdef \times nobs)$$

In the case that one of the matrices is time-invariant (so that, for example, $$Z_t = Z_{t+1} ~ \forall ~ t$$), its last dimension may be of size $$1$$ rather than size nobs.

This generic form encapsulates many of the most popular linear time series models (see below) and is very flexible, allowing estimation with missing observations, forecasting, impulse response functions, and much more.

Example: AR(2) model

An autoregressive model is a good introductory example to putting models in state space form. Recall that an AR(2) model is often written as:

$y_t = \phi_1 y_{t-1} + \phi_2 y_{t-2} + \epsilon_t, \quad \epsilon_t \sim N(0, \sigma^2)$

This can be put into state space form in the following way:

$\begin{split}y_t & = \begin{bmatrix} 1 & 0 \end{bmatrix} \alpha_t \\ \alpha_{t+1} & = \begin{bmatrix} \phi_1 & \phi_2 \\ 1 & 0 \end{bmatrix} \alpha_t + \begin{bmatrix} 1 \\ 0 \end{bmatrix} \eta_t\end{split}$

Where

$Z_t \equiv Z = \begin{bmatrix} 1 & 0 \end{bmatrix}$

and

$\begin{split}T_t \equiv T & = \begin{bmatrix} \phi_1 & \phi_2 \\ 1 & 0 \end{bmatrix} \\ R_t \equiv R & = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \\ \eta_t \equiv \epsilon_{t+1} & \sim N(0, \sigma^2)\end{split}$

There are three unknown parameters in this model: $$\phi_1, \phi_2, \sigma^2$$.

## Models and Estimation¶

The following are the main estimation classes, which can be accessed through statsmodels.tsa.statespace.api and their result classes.

### Seasonal Autoregressive Integrated Moving-Average with eXogenous regressors (SARIMAX)¶

The SARIMAX class is an example of a fully fledged model created using the statespace backend for estimation. SARIMAX can be used very similarly to tsa models, but works on a wider range of models by adding the estimation of additive and multiplicative seasonal effects, as well as arbitrary trend polynomials.

 sarimax.SARIMAX(endog[, exog, order, ...]) Seasonal AutoRegressive Integrated Moving Average with eXogenous regressors model sarimax.SARIMAXResults(model, params, ...[, ...]) Class to hold results from fitting an SARIMAX model.

For an example of the use of this model, see the SARIMAX example notebook or the very brief code snippet below:

# Load the statsmodels api
import statsmodels.api as sm

# Load your dataset
endog = pd.read_csv('your/dataset/here.csv')

# We could fit an AR(2) model, described above
mod_ar2 = sm.tsa.SARIMAX(endog, order=(2,0,0))
# Note that mod_ar2 is an instance of the SARIMAX class

# Fit the model via maximum likelihood
res_ar2 = mod_ar2.fit()
# Note that res_ar2 is an instance of the SARIMAXResults class

# Show the summary of results
print(res_ar2.summary())

# We could also fit a more complicated model with seasonal components.
# As an example, here is an SARIMA(1,1,1) x (0,1,1,4):
mod_sarimax = sm.tsa.SARIMAX(endog, order=(1,1,1),
seasonal_order=(0,1,1,4))
res_sarimax = mod_sarimax.fit()

# Show the summary of results
print(res_sarimax.summary())

The results object has many of the attributes and methods you would expect from other statsmodels results objects, including standard errors, z-statistics, and prediction / forecasting.

Behind the scenes, the SARIMAX model creates the design and transition matrices (and sometimes some of the other matrices) based on the model specification.

### Unobserved Components¶

The UnobservedComponents class is another example of a statespace model.

 structural.UnobservedComponents(endog[, ...]) Univariate unobserved components time series model Class to hold results from fitting an unobserved components model.

For examples of the use of this model, see the example notebook or a notebook on using the unobserved components model to decompose a time series into a trend and cycle or the very brief code snippet below:

# Load the statsmodels api
import statsmodels.api as sm

# Load your dataset
endog = pd.read_csv('your/dataset/here.csv')

# Fit a local level model
mod_ll = sm.tsa.UnobservedComponents(endog, 'local level')
# Note that mod_ll is an instance of the UnobservedComponents class

# Fit the model via maximum likelihood
res_ll = mod_ll.fit()
# Note that res_ll is an instance of the UnobservedComponentsResults class

# Show the summary of results
print(res_ll.summary())

# Show a plot of the estimated level and trend component series
fig_ll = res_ll.plot_components()

# We could further add a damped stochastic cycle as follows
mod_cycle = sm.tsa.UnobservedComponents(endog, 'local level', cycle=True,
damped_cycle=True,
stochastic_cycle=True)
res_cycle = mod_cycle.fit()

# Show the summary of results
print(res_cycle.summary())

# Show a plot of the estimated level, trend, and cycle component series
fig_cycle = res_cycle.plot_components()

### Vector Autoregressive Moving-Average with eXogenous regressors (VARMAX)¶

The VARMAX class is an example of a multivariate statespace model.

 varmax.VARMAX(endog[, exog, order, trend, ...]) Vector Autoregressive Moving Average with eXogenous regressors model varmax.VARMAXResults(model, params, ...[, ...]) Class to hold results from fitting an VARMAX model.

For an example of the use of this model, see the VARMAX example notebook or the very brief code snippet below:

# Load the statsmodels api
import statsmodels.api as sm

# Load your (multivariate) dataset
endog = pd.read_csv('your/dataset/here.csv')

# Fit a local level model
mod_var1 = sm.tsa.VARMAX(endog, order=(1,0))
# Note that mod_var1 is an instance of the VARMAX class

# Fit the model via maximum likelihood
res_var1 = mod_var1.fit()
# Note that res_var1 is an instance of the VARMAXResults class

# Show the summary of results
print(res_var1.summary())

# Construct impulse responses
irfs = res_ll.impulse_responses(steps=10)

### Dynamic Factor Models¶

Statsmodels has two classes that support dynamic factor models: DynamicFactorMQ and DynamicFactor. Each of these models has strengths, but in general the DynamicFactorMQ class is recommended. This is because it fits parameters using the Expectation-Maximization (EM) algorithm, which is more robust and can handle including hundreds of observed series. In addition, it allows customization of which variables load on which factors. However, it does not yet support including exogenous variables, while DynamicFactor does support that feature.

 dynamic_factor_mq.DynamicFactorMQ(endog[, ...]) Dynamic factor model with EM algorithm; option for monthly/quarterly data. Results from fitting a dynamic factor model

For an example of the DynamicFactorMQ class, see the very brief code snippet below:

# Load the statsmodels api
import statsmodels.api as sm

# Load your dataset
endog = pd.read_csv('your/dataset/here.csv')

# Create a dynamic factor model
mod_dfm = sm.tsa.DynamicFactorMQ(endog, k_factors=1, factor_order=2)
# Note that mod_dfm is an instance of the DynamicFactorMQ class

# Fit the model via maximum likelihood, using the EM algorithm
res_dfm = mod_dfm.fit()
# Note that res_dfm is an instance of the DynamicFactorMQResults class

# Show the summary of results
print(res_ll.summary())

# Show a plot of the r^2 values from regressions of
# individual estimated factors on endogenous variables.
fig_dfm = res_ll.plot_coefficients_of_determination()

The DynamicFactor class is suitable for models with a smaller number of observed variables

 dynamic_factor.DynamicFactor(endog, ...[, ...]) Dynamic factor model dynamic_factor.DynamicFactorResults(model, ...) Class to hold results from fitting an DynamicFactor model.

For an example of the use of the DynamicFactor model, see the Dynamic Factor example notebook

### Linear Exponential Smoothing Models¶

The ExponentialSmoothing class is an implementation of linear exponential smoothing models using a state space approach.

Note: this model is available at sm.tsa.statespace.ExponentialSmoothing; it is not the same as the model available at sm.tsa.ExponentialSmoothing. See below for details of the differences between these classes.

 Linear exponential smoothing models Results from fitting a linear exponential smoothing model

A very brief code snippet follows:

# Load the statsmodels api
import statsmodels.api as sm

# Load your dataset
endog = pd.read_csv('your/dataset/here.csv')

# Simple exponential smoothing, denoted (A,N,N)
mod_ses = sm.tsa.statespace.ExponentialSmoothing(endog)
res_ses = mod_ses.fit()

# Holt's linear method, denoted (A,A,N)
mod_h = sm.tsa.statespace.ExponentialSmoothing(endog, trend=True)
res_h = mod_h.fit()

# Damped trend model, denoted (A,Ad,N)
mod_dt = sm.tsa.statespace.ExponentialSmoothing(endog, trend=True,
damped_trend=True)
res_dt = mod_dt.fit()

# Holt-Winters' trend and seasonality method, denoted (A,A,A)
# (assuming that endog has a seasonal periodicity of 4, for example if it
# is quarterly data).
mod_hw = sm.tsa.statespace.ExponentialSmoothing(endog, trend=True,
seasonal=4)
res_hw = mod_hw.fit()

Differences between Statsmodels’ exponential smoothing model classes

There are several differences between this model class, available at sm.tsa.statespace.ExponentialSmoothing, and the model class available at sm.tsa.ExponentialSmoothing.

• This model class only supports linear exponential smoothing models, while sm.tsa.ExponentialSmoothing also supports multiplicative models.

• This model class puts the exponential smoothing models into state space form and then applies the Kalman filter to estimate the states, while sm.tsa.ExponentialSmoothing is based on exponential smoothing recursions. In some cases, this can mean that estimating parameters with this model class will be somewhat slower than with sm.tsa.ExponentialSmoothing.

• This model class can produce confidence intervals for forecasts, based on an assumption of Gaussian errors, while sm.tsa.ExponentialSmoothing does not support confidence intervals.

• This model class supports concentrating initial values out of the objective function, which can improve performance when there are many initial states to estimate (for example when the seasonal periodicity is large).

• This model class supports many advanced features available to state space models, such as diagnostics and fixed parameters.

Note: this class is based on a “multiple sources of error” (MSOE) state space formulation and not a “single source of error” (SSOE) formulation.

### Custom state space models¶

The true power of the state space model is to allow the creation and estimation of custom models. Usually that is done by extending the following two classes, which bundle all of state space representation, Kalman filtering, and maximum likelihood fitting functionality for estimation and results output.

 mlemodel.MLEModel(endog, k_states[, exog, ...]) State space model for maximum likelihood estimation mlemodel.MLEResults(model, params, results) Class to hold results from fitting a state space model.

For a basic example demonstrating creating and estimating a custom state space model, see the Local Linear Trend example notebook. For a more sophisticated example, see the source code for the SARIMAX and SARIMAXResults classes, which are built by extending MLEModel and MLEResults.

In simple cases, the model can be constructed entirely using the MLEModel class. For example, the AR(2) model from above could be constructed and estimated using only the following code:

import numpy as np
from scipy.signal import lfilter
import statsmodels.api as sm

# True model parameters
nobs = int(1e3)
true_phi = np.r_[0.5, -0.2]
true_sigma = 1**0.5

# Simulate a time series
np.random.seed(1234)
disturbances = np.random.normal(0, true_sigma, size=(nobs,))
endog = lfilter([1], np.r_[1, -true_phi], disturbances)

# Construct the model
class AR2(sm.tsa.statespace.MLEModel):
def __init__(self, endog):
# Initialize the state space model
super(AR2, self).__init__(endog, k_states=2, k_posdef=1,
initialization='stationary')

# Setup the fixed components of the state space representation
self['design'] = [1, 0]
self['transition'] = [[0, 0],
[1, 0]]
self['selection', 0, 0] = 1

# Describe how parameters enter the model
def update(self, params, transformed=True, **kwargs):
params = super(AR2, self).update(params, transformed, **kwargs)

self['transition', 0, :] = params[:2]
self['state_cov', 0, 0] = params[2]

# Specify start parameters and parameter names
@property
def start_params(self):
return [0,0,1]  # these are very simple

# Create and fit the model
mod = AR2(endog)
res = mod.fit()
print(res.summary())

This results in the following summary table:

                           Statespace Model Results
==============================================================================
Dep. Variable:                      y   No. Observations:                 1000
Model:                            AR2   Log Likelihood               -1389.437
Date:                Wed, 26 Oct 2016   AIC                           2784.874
Time:                        00:42:03   BIC                           2799.598
Sample:                             0   HQIC                          2790.470
- 1000
Covariance Type:                  opg
==============================================================================
coef    std err          z      P>|z|      [0.025      0.975]
------------------------------------------------------------------------------
param.0        0.4395      0.030     14.730      0.000       0.381       0.498
param.1       -0.2055      0.032     -6.523      0.000      -0.267      -0.144
param.2        0.9425      0.042     22.413      0.000       0.860       1.025
===================================================================================
Ljung-Box (Q):                       24.25   Jarque-Bera (JB):                 0.22
Prob(Q):                              0.98   Prob(JB):                         0.90
Heteroskedasticity (H):               1.05   Skew:                            -0.04
Prob(H) (two-sided):                  0.66   Kurtosis:                         3.02
===================================================================================

Warnings:
[1] Covariance matrix calculated using the outer product of gradients (complex-step).

The results object has many of the attributes and methods you would expect from other statsmodels results objects, including standard errors, z-statistics, and prediction / forecasting.

More advanced usage is possible, including specifying parameter transformations, and specifying names for parameters for a more informative output summary.

## Overview of usage¶

All state space models follow the typical Statsmodels pattern:

1. Construct a model instance with an input dataset

2. Apply parameters to the model (for example, using fit) to construct a results instance

3. Interact with the results instance to examine the estimated parameters, explore residual diagnostics, and produce forecasts, simulations, or impulse responses.

An example of this pattern is as follows:

# Load in the example macroeconomic dataset
dta = sm.datasets.macrodata.load_pandas().data
# Make sure we have an index with an associated frequency, so that
# we can refer to time periods with date strings or timestamps
dta.index = pd.date_range('1959Q1', '2009Q3', freq='QS')

# Step 1: construct an SARIMAX model for US inflation data
model = sm.tsa.SARIMAX(dta.infl, order=(4, 0, 0), trend='c')

# Step 2: fit the model's parameters by maximum likelihood
results = model.fit()

# Step 3: explore / use results

# - Print a table summarizing estimation results
print(results.summary())

# - Print only the estimated parameters
print(results.params)

# - Create diagnostic figures based on standardized residuals:
#   (1) time series graph
#   (2) histogram
#   (3) Q-Q plot
#   (4) correlogram
results.plot_diagnostics()

# - Examine diagnostic hypothesis tests
# Jarque-Bera: [test_statistic, pvalue, skewness, kurtosis]
print(results.test_normality(method='jarquebera'))
# Goldfeld-Quandt type test: [test_statistic, pvalue]
print(results.test_heteroskedasticity(method='breakvar'))
# Ljung-Box test: [test_statistic, pvalue] for each lag
print(results.test_serial_correlation(method='ljungbox'))

# - Forecast the next 4 values
print(results.forecast(4))

# - Forecast until 2020Q4
print(results.forecast('2020Q4'))

# - Plot in-sample dynamic prediction starting in 2005Q1
#   and out-of-sample forecasts until 2010Q4 along with
#   90% confidence intervals
predict_results = results.get_prediction(start='2005Q1', end='2010Q4', dynamic=True)
predict_df = predict_results.summary_frame(alpha=0.10)
fig, ax = plt.subplots()
predict_df['mean'].plot(ax=ax)
ax.fill_between(predict_df.index, predict_df['mean_ci_lower'],
predict_df['mean_ci_upper'], alpha=0.2)

# - Simulate two years of new data after the end of the sample
print(results.simulate(8, anchor='end'))

# - Impulse responses for two years
print(results.impulse_responses(8))

## Basic methods and attributes for estimation / filtering / smoothing¶

The most-used methods for a state space model are:

• fit - estimate parameters via maximum likelihood and return a results object (this object will have also performed Kalman filtering and smoothing at the estimated parameters). This is the most commonly used method.

• smooth - return a results object associated with a given vector of parameters after performing Kalman filtering and smoothing

• loglike - compute the log-likelihood of the data using a given vector of parameters

Some useful attributes of a state space model are:

Other methods that are used less often are:

## Output and postestimation methods and attributes¶

Commonly used methods include:

Commonly used attributes include:

### Estimates and covariances of the unobserved state¶

It can be useful to compute estimates of the unobserved state vector conditional on the observed data. These are available in the results object states, which contains the following elements:

• states.filtered - filtered (one-sided) estimates of the state vector. The estimate of the state vector at time t is based on the observed data up to and including time t.

• states.smoothed - smoothed (two-sided) estimates of the state vector. The estimate of the state vector at time t is based on all observed data in the sample.

• states.filtered_cov - filtered (one-sided) covariance of the state vector

• states.smoothed_cov - smoothed (two-sided) covariance of the state vector

Each of these elements are Pandas DataFrame objects.

As an example, in a “local level + seasonal” model estimated via the UnobservedComponents components class we can get an estimates of the underlying level and seasonal movements of a series over time.

fig, axes = plt.subplots(3, 1, figsize=(8, 8))

# Retrieve monthly retail sales for clothing
from pandas_datareader.data import DataReader
clothing = DataReader('MRTSSM4481USN', 'fred', start='1992').asfreq('MS')['MRTSSM4481USN']

# Construct a local level + seasonal model
model = sm.tsa.UnobservedComponents(clothing, 'llevel', seasonal=12)
results = model.fit()

# Plot the data, the level, and seasonal
clothing.plot(ax=axes[0])
results.states.smoothed['level'].plot(ax=axes[1])
results.states.smoothed['seasonal'].plot(ax=axes[2])

### Residual diagnostics¶

Three diagnostic tests are available after estimation of any statespace model, whether built in or custom, to help assess whether the model conforms to the underlying statistical assumptions. These tests are:

A number of standard plots of regression residuals are available for the same purpose. These can be produced using the command plot_diagnostics.

### Applying estimated parameters to an updated or different dataset¶

There are three methods that can be used to apply estimated parameters from a results object to an updated or different dataset:

• append - retrieve a new results object with additional observations that follow after the end of the current sample appended to it (so the new results object contains both the current sample and the additional observations)

• extend - retrieve a new results object for additional observations that follow after end of the current sample (so the new results object contains only the new observations but NOT the current sample)

• apply - retrieve a new results object for a completely different dataset

One cross-validation exercise on time-series data involves fitting a model’s parameters based on a training sample (observations through time t) and then evaluating the fit of the model using a test sample (observations t+1, t+2, …). This can be conveniently done using either apply or extend. In the example below, we use the extend method.

# Load in the example macroeconomic dataset
dta = sm.datasets.macrodata.load_pandas().data
# Make sure we have an index with an associated frequency, so that
# we can refer to time periods with date strings or timestamps
dta.index = pd.date_range('1959Q1', '2009Q3', freq='QS')

# Separate inflation data into a training and test dataset
training_endog = dta['infl'].iloc[:-1]
test_endog = dta['infl'].iloc[-1:]

# Fit an SARIMAX model for inflation
training_model = sm.tsa.SARIMAX(training_endog, order=(4, 0, 0))
training_results = training_model.fit()

# Extend the results to the test observations
test_results = training_results.extend(test_endog)

# Print the sum of squared errors in the test sample,
# based on parameters computed using only the training sample
print(test_results.sse)

### Understanding the Impact of Data Revisions¶

Statespace model results expose a news method that can be used to understand the impact of data revisions – news – on model parameters.

 news.NewsResults(news_results, model, ...[, ...]) Impacts of data revisions and news on estimates of variables of interest

## Additional options and tools¶

All state space models have the following options and tools:

### Holding some parameters fixed and estimating the rest¶

The fit_constrained method allows fixing some parameters to known values and then estimating the rest via maximum likelihood. An example of this is:

# Construct a model
model = sm.tsa.SARIMAX(endog, order=(1, 0, 0))

# To find out the parameter names, use:
print(model.param_names)

# Fit the model with a fixed value for the AR(1) coefficient:
results = model.fit_constrained({'ar.L1': 0.5})

Alternatively, you can use the fix_params context manager:

# Construct a model
model = sm.tsa.SARIMAX(endog, order=(1, 0, 0))

# Fit the model with a fixed value for the AR(1) coefficient using the
# context manager
with model.fix_params({'ar.L1': 0.5}):
results = model.fit()

### Low memory options¶

When the observed dataset is very large and / or the state vector of the model is high-dimensional (for example when considering long seasonal effects), the default memory requirements can be too large. For this reason, the fit, filter, and smooth methods accept an optional low_memory=True argument, which can considerably reduce memory requirements and speed up model fitting.

Note that when using low_memory=True, not all results objects will be available. However, residual diagnostics, in-sample (non-dynamic) prediction, and out-of-sample forecasting are all still available.

## Low-level state space representation and Kalman filtering¶

While creation of custom models will almost always be done by extending MLEModel and MLEResults, it can be useful to understand the superstructure behind those classes.

Maximum likelihood estimation requires evaluating the likelihood function of the model, and for models in state space form the likelihood function is evaluated as a byproduct of running the Kalman filter.

There are two classes used by MLEModel that facilitate specification of the state space model and Kalman filtering: Representation and KalmanFilter.

The Representation class is the piece where the state space model representation is defined. In simple terms, it holds the state space matrices (design, obs_intercept, etc.; see the introduction to state space models, above) and allows their manipulation.

FrozenRepresentation is the most basic results-type class, in that it takes a “snapshot” of the state space representation at any given time. See the class documentation for the full list of available attributes.

 representation.Representation(k_endog, k_states) State space representation of a time series process Frozen Statespace Model

The KalmanFilter class is a subclass of Representation that provides filtering capabilities. Once the state space representation matrices have been constructed, the filter method can be called, producing a FilterResults instance; FilterResults is a subclass of FrozenRepresentation.

The FilterResults class not only holds a frozen representation of the state space model (the design, transition, etc. matrices, as well as model dimensions, etc.) but it also holds the filtering output, including the filtered state and loglikelihood (see the class documentation for the full list of available results). It also provides a predict method, which allows in-sample prediction or out-of-sample forecasting. A similar method, predict, provides additional prediction or forecasting results, including confidence intervals.

 kalman_filter.KalmanFilter(k_endog, k_states) State space representation of a time series process, with Kalman filter Results from applying the Kalman filter to a state space model. kalman_filter.PredictionResults(results, ...) Results of in-sample and out-of-sample prediction for state space models generally

The KalmanSmoother class is a subclass of KalmanFilter that provides smoothing capabilities. Once the state space representation matrices have been constructed, the filter method can be called, producing a SmootherResults instance; SmootherResults is a subclass of FilterResults.

The SmootherResults class holds all the output from FilterResults, but also includes smoothing output, including the smoothed state and loglikelihood (see the class documentation for the full list of available results). Whereas “filtered” output at time t refers to estimates conditional on observations up through time t, “smoothed” output refers to estimates conditional on the entire set of observations in the dataset.

 kalman_smoother.KalmanSmoother(k_endog, k_states) State space representation of a time series process, with Kalman filter and smoother. Results from applying the Kalman smoother and/or filter to a state space model.

The SimulationSmoother class is a subclass of KalmanSmoother that further provides simulation and simulation smoothing capabilities. The simulation_smoother method can be called, producing a SimulationSmoothResults instance.

The SimulationSmoothResults class has a simulate method, that allows performing simulation smoothing to draw from the joint posterior of the state vector. This is useful for Bayesian estimation of state space models via Gibbs sampling.

 State space representation of a time series process, with Kalman filter and smoother, and with simulation smoother. Results from applying the Kalman smoother and/or filter to a state space model. "Cholesky Factor Algorithm" (CFA) simulation smoother

## Statespace Tools¶

There are a variety of tools used for state space modeling or by the SARIMAX class:

 tools.companion_matrix(polynomial) Create a companion matrix tools.diff(series[, k_diff, ...]) Difference a series simply and/or seasonally along the zero-th axis. tools.is_invertible(polynomial[, threshold]) Determine if a polynomial is invertible. Transform unconstrained parameters used by the optimizer to constrained parameters used in likelihood evaluation Transform constrained parameters used in likelihood evaluation to unconstrained parameters used by the optimizer Transform unconstrained parameters used by the optimizer to constrained parameters used in likelihood evaluation for a vector autoregression. Transform constrained parameters used in likelihood evaluation to unconstrained parameters used by the optimizer tools.validate_matrix_shape(name, shape, ...) Validate the shape of a possibly time-varying matrix, or raise an exception tools.validate_vector_shape(name, shape, ...) Validate the shape of a possibly time-varying vector, or raise an exception

format: plain


text:
# How to avoid that listings are interrupted by floats?

And again I have another problem I just can't figure out. I defined a listing with some XML code:

\begin{lstlisting}[captionpos=b, caption=XML detection strategy for Refused Parent Bequest, label=lst:refused_parent_bequest]
<strategy name="Refused Parent Bequest" ...>
<gate type="AND">
<gate type="OR">
<gate type="AND">
<rule>
<metric>NProtM</metric>
<comparison>greater than</comparison>
<value>10</value>
</rule>
<rule>
<metric>BUR</metric>
<comparison>smaller than</comparison>
<value>0.33</value>
</rule>
</gate>
<rule>
<metric>BOvR</metric>
<comparison>smaller than</comparison>
<value>0.33</value>
</rule>
</gate>
<gate type="AND">
<gate type="OR">
<rule>
<metric>AMW</metric>
<comparison>greater than</comparison>
<value>-1</value>
</rule>
<rule>
<metric>WMC</metric>
<comparison>greater than</comparison>
<value>-1</value>
</rule>
</gate>
<rule>
<metric>NOM</metric>
<comparison>greater than</comparison>
<value>-1</value>
</rule>
</gate>
</gate>
</strategy>
\end{lstlisting}

Very near to this I also defined a table. Now the problem is the listing starts on the first page, the there is a page break, then there is the table and then the listing continues. How can I force the layout to not interrupt my listing?

-
–  Martin Scharrer Sep 18 '11 at 22:59

You can adjust the placing of floats the following ways:

For once you could add \FloatBarrier from the placeins package before the listing to flush all previous floats. This wont help if the table is defined just after it.

The \suppressfloats macro allows you to suppress floats on the current page. You could add it before the listing inside an \afterpage{...} (afterpage package) so that it counts for the second page of the listing.

There is also the flafter package which makes floats only appear after their definition. This should handle a table defined shortly after the listing.

-
Another (and less hacky) possibility is, to add the float Parameter to your listing. It will then float like the tables do, but floating environments don't interrupt each other:
\begin{lstlisting}[float]


text:
0
Research Papers

# Multiscale Topology Optimization for Additively Manufactured ObjectsPUBLIC ACCESS

[+] Author and Article Information
John C. Steuben

Mem. ASME
Computational Multiphysics Systems Laboratory,
Center of Materials Physics and Technology,
U.S. Naval Research Laboratory,
Washington, DC 20375

Athanasios P. Iliopoulos

Mem. ASME
Computational Multiphysics Systems Laboratory,
Center of Materials Physics and Technology
U.S. Naval Research Laboratory,
Washington, DC 20375

John G. Michopoulos

Fellow ASME
Computational Multiphysics Systems Laboratory,
Center of Materials Physics and Technology,
U.S. Naval Research Laboratory,
Washington, DC 20375

1Corresponding author.

Contributed by the Computers and Information Division of ASME for publication in the JOURNAL OF COMPUTING AND INFORMATION SCIENCE IN ENGINEERING. Manuscript received October 15, 2017; final manuscript received January 23, 2018; published online June 12, 2018. Assoc. Editor: Jitesh H. Panchal.

J. Comput. Inf. Sci. Eng 18(3), 031002 (Jun 12, 2018) (10 pages) Paper No: JCISE-17-1229; doi: 10.1115/1.4039312 History: Received October 15, 2017; Revised January 23, 2018

## Abstract

The precise control of mass and energy deposition associated with additive manufacturing (AM) processes enables the topological specification and realization of how space can be filled by material in multiple scales. Consequently, AM can be pursued in a manner that is optimized such that fabricated objects can best realize performance specifications. In the present work, we propose a computational multiscale method that utilizes the unique meso-scale structuring capabilities of implicit slicers for AM, in conjunction with existing topology optimization (TO) tools for the macro-scale, in order to generate structurally optimized components. The use of this method is demonstrated on two example objects including a load bearing bracket and a hand tool. This paper also includes discussion concerning the applications of this methodology, its current limitations, a recasting of the AM digital thread, and the future work required to enable its widespread use.

<>

## Introduction

Additive manufacturing (AM) has recently been a topic of great excitement, largely driven by its unique capabilities. AM processes successively add material, energy, or both to a domain in order to generate a pre-specified geometry. Compared to traditional manufacturing technologies, AM provides a great deal of freedom from geometric constraints and can readily produce components that are difficult or impossible to realize using conventional means. Furthermore, it provides the ability to tailor the topology of space-filling mass accretion in a way that enables the part to perform certain required functions in an optimal manner. As a result, the use of topologically optimized AM for low volume or customized manufacturing applications has become increasingly widespread.

The primary goal of the work described here is the development of a new multiscale topology optimization (TO) methodology for AM in a manner that extends the benefits of the macro-scale topology optimization to the meso-scale in a synergistic manner. While the topic of topology optimization for AM has been explored previously [1,2], the present work describes a novel multiscale approach that is enabled by combining an implicit slicing methodology acting at the meso-scale with a traditional topology optimization for the macro-scale. This allows the optimization of both the macro- and meso-structures in order to improve the mechanical performance of the resulting components. More broadly, this work presents modifications to the additive manufacturing digital thread that enable tailoring the response of additively manufactured structures with respect to performance specifications. Because the AM digital thread presents an often inflexible architecture connected by proprietary interfaces and formats, which often precludes the development of tools that interface with commercial AM systems, we also examine the topic of a reinterpreted digital thread with optimization processes at its heart.

This paper expands on previous work [3,4] and is organized as follows. Background material on the topics of the digital thread, slicing, and topology optimization is given in Sec. 2. Following that, the multiscale topology optimization methodology is outlined. A load bearing bracket structure is selected for demonstrating the proposed methodology, that is also followed by yet another demonstration problem, concerning the optimization of a hand-held spanner wrench. We conclude with our remarks on the development of this methodology, and on the future work that will be required to generalize it for more widespread use.

## Background

Before the subject of multiscale topology optimization for AM can be explored, there is a wide array of existing literature that must be discussed in order to provide context. We begin with a general discussion of additive manufacturing and the digital thread, before turning to the topic of slicers, and recent developments with respect to implicit slicing algorithms in particular. Following this, we discuss the history of topology optimization algorithms in general, and then focus on discussion of topology optimization for AM.

Since the AM concept first emerged in the late 1970s, a large number of AM methods have been developed. Common techniques at present include stereolithography [5], fused deposition modeling (FDM) [6], selective laser sintering [79], electron beam melting [10], and direct metal deposition [11,12]. The architectural, structural, and operation details of these processes vary widely, but they share a common digital thread representing the associated data flow necessary for their proper operation. A block diagram of the AM digital thread concept is shown in Fig. 1. This diagram represents a somewhat extended definition of the term “digital thread.” Because of the highly integrated nature of the additive manufacturing software implementations produced by AM hardware manufacturers, most of the individual components of the digital thread, such as those that are executed on the runtime system of the AM hardware, are frequently inaccessible the end-users. A highly useful classification of the different methods and algorithms applicable to each step of the digital thread is given by Livesu et al. [13].

As Fig. 1 shows, the AM-specific digital thread is subdivided into a design environment, a preprocessing environment, and a manufacturing environment. The digital thread begins in the design environment and originates from a computer-aided design model produced by a designer. The ultimate goal of the additive manufacturing process is to produce this model within acceptable constraints on accuracy, time, cost, and other parameters. Within the design environment, this geometry is converted to a triangular mesh form, typically encoded as a stereolithography, an additive manufacturing file, or similar file. It is important to note that this conversion preserves approximate [14] geometric information regarding the original model only. Any other ancillary information encoded within the original model is lost in this process. Moving to the preprocessing stage, the position of the resultant mesh within the build volume of the additive manufacturing process is determined by a layout optimization routine. In practice, a collection of many meshes is packed into the build volume of the machine in order to reduce per-unit production costs, using a method such as that presented in Ref. [15]. The mesh (or collection of meshes) is then processed by a “slicer.” The purpose of the slicer is to subdivide the mesh(es) into a series of distinct layers, and to compute the numeric control (NC) commands issued to the additive manufacturing machine in order to produce the distinct toolpaths making up each layer. The NC code is usually a customization of classical G-code commands used with computer numeric control machines. The build layout and slicer tools are often combined into a single commercial software product, that largely behaves as a “black box.” Once the toolpath has been produced and the proper G-code sequences have been generated, the motion control software and hardware systems present in the manufacturing environment are used to drive the additive manufacturing machine in order to produce the output object. Further information on the digital thread may be found in Refs. [13], [16], and [17].

An inherent limitation of the digital thread at the preprocessing environment level as depicted in Fig. 1 is the fact that the build layout and slicer components of typical commercial machines utilize mostly heuristic criteria that are not exposed to the user. Thus, the “black box” character of these modules does not permit the user to control the build layout and slicer software in a manner that can be tailored to address functional specification needs for the part. This work is motivated by the need to control the build layout and slicing process in a manner that enables tailoring of such processes to achieve optimal structural performance.

###### Slicers and Associated Terminology.

Slicers are based on the field of computational geometry and manifest as computational tools that convert input three-dimensional (3D) models into a series of motion commands (a “toolpath”) for an additive manufacturing machine. The slicer is required to both process the input geometry into a suitable toolpath for additive manufacturing and export this toolpath as a series of NC commands that are subsequently conveyed to the additive manufacturing hardware. As the second stage of this process depends heavily on the specific additive manufacturing process and device employed, we restrict our discussion to that of toolpath generation. Figure 2 demonstrates a hypothetical toolpath generated by a slicing algorithm.

While there are strong similarities between slicers and the broader topic of NC toolpath generation, there are several unique aspects of additive manufacturing slicing that render it a distinct research field. A review of early work in this vein may be found in Refs. [1821]. Various improvements to these early algorithms, generally termed “adaptive” slicing, can be found in Refs. [2227]. Efforts to improve the results of slicing, for instance by eliminating voids in the infill portion of the toolpath, are explored by Yang et al. [28] and Qiu et al. [29]. Recent research into slicing, for instance the work of Siraskar et al. [30] and Qiu et al. [31], has primarily been focused on increasing computational performance. Additionally, some work including Refs. [20] and [31] has focused on “direct” slicers, which bypass the model triangularization step and convert the input computer-aided design geometry directly into toolpaths. Most recently, image-space approaches to slicing have emerged [32,33], which operate on point-cloud or volumetric image data in a reverse-engineering context. One such slicer utilizes general-purpose graphics processing unit computing [34]. Additionally, slicers intended to produce objects with spatially varying elastic properties have also been developed [3537].

###### Implicit Slicing.

To address the issue of tailoring the slicing in a manner that enables the part to respond optimally under its usage conditions, we have developed an alternative to the aforementioned slicing algorithms. This alternative is termed “implicit slicing” [38,39] and we provide here a short description of it for the sake of completeness.

The implicit slicer is based on computing the level sets of functional fields defined over the spatial domain of the object to be manufactured. Generally, it defines the AM toolpath to be a singleton set gDisplay Formula

(1)$g≡⊎i=0nl⊎j=0no⊎k=0nkHj(x)=ck,x∈ωi$

where ωi are the two-dimensional regions corresponding to each slice of the input model, and $x$ is a Cartesian coordinate within such a slice. Hj are the field functions defining the toolpath shape, and ck are the values at which the toolpath is computed. The operator $⊎$ indicates a superset union corresponding the sequencing and ordering of toolpath segments in a manner appropriate for the AM system being targeted, nk is the number of level sets computed for each field function, no is the number of field functions considered for each slice, and nl is the number of layers used to slice the part.

This formulation elegantly solves the problem of computing polygon offsets for arbitrary (and possibly degenerate) geometries, but it allows the introduction of “design intent” into the digital thread. Since the field(s) upon which the infill toolpaths are computed may be specified by the user, this function may be chosen based on performance criteria. An example, illustrated in Fig. 3 shows the use of the von Mises stress in order to generate the infill for a dogbone test specimen. Experimentation showed that the meso-scale toolpath tailoring of the implicit slicer produced parts with mechanical performance superior to those exhibited by parts produced using conventional slicers [38].

###### Topology Optimization.

The term TO refers to a diverse family of methods that seeks to optimize the distribution of material within a given design space, for a given set of boundary conditions, with the goal of maximizing a measure of performance of the resulting structure. Alternatively, topology optimization can be imagined as the process of determining where to “poke holes” in a structure or where to deposit material in a design volume, in order to reduce its mass, without compromising performance. A broad overview of TO techniques and algorithms can be found in Refs. [4042]. Common approaches include solid isotropic material with penalization (SIMP) [4345], evolutionary approaches [46], level set methods [47,48], and topological sensitivity [49,50]. Beyond isotropic materials, TO for optimal structural performance has been applied to anisotropic material systems, such as composite shells [51], and to performance requirements involving buckling and thermoelasticity [52]. Furthermore, TO has been widely applied to many engineering design challenges, such as [5355].

The topic of topology optimization has recently become of great interest within the additive manufacturing research community. This has largely been driven by the capability of AM technologies to produce the “organic” geometries, which often emerge from TO solvers, as clearly demonstrated by Zegard and Paulino [1]. Examples of the coupling between TO and AM methods are also demonstrated by Wang et al. [56], Robbins et al. [57], and Quan et al. [58]. The work of Gaynor et al. [59] is especially interesting, as this approach incorporates some of the limitations of AM technology (e.g., overhangs) into the TO formulation. Other recent works, such as Refs. [60] and [61], demonstrate the strong potential for the use of TO to achieve effective property tailoring in AM.

The present work utilizes the SIMP topology optimization method. In the SIMP model, the true Young's modulus E0 is multiplied by an artificial density factor, ρdDisplay Formula

(2)$E(x)=ρd(x)pE0, x∈Ω$

where again $x$ is a coordinate in the domain $Ω$ and p is a penalty factor that reduces the effective stiffness of intermediate densities. The artificial density is constrained to $0≤ρd≤1$. This spatially resolved reduced modulus is used to evaluate a multiresolution finite element analysis (FEA) model. In the present context, the term “multi-resolution” indicates a model that is solved with a subsequently denser mesh in order to achieve the desired spatial resolution. The density of every element in the FEA model is then adjusted according to an optimization scheme. The optimization is defined to minimize an objective function that represents the sum of two terms according to Display Formula

(3)$minf=(1−q)Ws0∫ΩWs(x)dΩ+qh0hmaxA∫Ω|∇ρd(x)|2dΩ$
subject to the inequality constraints Display Formula
(4)$0≤∫Ωρd(x)dΩ≤γA$

where Ws is the strain energy density functional, and $Ws0$ is the total strain energy assuming a constant density $ρd(x)=γ$ throughout the domain Ω. h0 and hmax are the initial and maximum FEA mesh element sizes, $A=∫Ω1dΩ$, and q is a weighting factor. The first term of f seeks to minimize strain energy, while the second term provides regularization by minimizing the gradient of the density.

## Proposed Methodology

From the discussion in the prior section, it is clear that there is a strong conceptual link between topology optimization and implicit slicing. The purpose of TO is to produce a density function that describes the optimal distribution of material within the original domain. The implicit slicer, on the other hand, accepts a function describing where material should be distributed (in order to achieve a functional performance goal) and produces an output toolpath for AM hardware based on this function. Previous applications of the implicit slicer [38] have used common measures such as von Mises stress to indirectly capture the notion of where material should be concentrated in order to improve performance. The use of topology optimization notably improves this situation, since ρd is a direct measurement of where material should be placed. It is clear that the two tools can be easily linked by first conducting the topology optimization, and subsequently invoking the implicit slicer with Display Formula

(5)$Hj(x)=ρd(x)$

In practice, there are numerous details associated with the coupling of these two methodologies in a manner that enables multiscale tailoring of mass deposition topology associated with AM processes. An schematic overview of the proposed methodology is depicted schematically by the workflow in Fig. 4.

###### Topology Optimization for the Macroscale.

We begin by extending the formulation of Eq. (3) to include multiple loading cases, by means of a weighted average. At every iteration of the outer optimization loop shown in Fig. 4, a separate FEA analysis is conducted using the ith of nlc set of boundary conditions. The resulting strain energy density for each load case is denoted $Wsi$. The objective function f is, thus, given by Display Formula

(6)$f=(1−q)∑i=1nlcwiWs0i∑i=1nlc[∫Ω0Ws(x)dΩ0]+qh0hmaxA∫Ω0|∇ρd(x)|2dΩ0$

The $Ws0i$ are computed in a preprocessing step, by setting the density to a uniform value of $ρd=γ$ and evaluating the FEA for each load case.

The SIMP formulation utilizes an exponent p to artificially and rapidly soften the response of material with intermediate density ($ρd<1$). This is driven by the desire to achieve a binary solution, where material is either present or not present at any location, in order to allow production via conventional means such as casting or machining. Values of p = 5 are typical. However, in the domain of additive manufacturing, it is easy to produce regions of intermediate density by varying the infill density. To reflect this, the SIMP implementation uses a small exponent of $1≤p≤2$. A unitary exponent is not used in practice, as it tends to produce output components that occupy the entire initial domain.

The SIMP topology optimization was implemented in the “comsolmultiphysics” FEA software tool [62]. In the present work, we consider the case of two-dimensional (2D) topology optimization, with the results then extended to 3D for AM under assumptions of either plane stress or plane strain, as appropriate. The implementation allows for arbitrary boundary conditions and arbitrary mesh elements. The FEA is performed using the mumps solver [63]. The method of moving asymptotes [64] is used to solve the topology optimization problem.

An example input problem involving the design of a bracket is given in Fig. 5. Figure 5(a) shows the original problem domain $Ω0$, with applied loads and boundary conditions. Figure 5(b) shows the density field computed by the topology optimization, using the parameters $γ=0.3, p=1.25, h0=0.5mm$, and $hmax=1mm$. The domain of the component to be additively manufactured $Ω$ is defined Display Formula

(7)$Ω={x∈Ω0 : ρd(x)≥ρmin}$

Figure 5(b) highlights the value $ρmin=0.25$ and Fig. 5(c) shows $Ω∈Ω0$.

While this set-theoretic definition of Ωf is easy to apply to the TO output, it is not compatible with the AM digital thread. Within the context of the FEA solution, ρd is defined by nodal values and interpolated over the elements via basis functions. The digital thread requires the input of a surface geometry model, typically a triangular mesh. The method of computing this mesh depends on if the TO was conducted in 2D or 3D. For specificity, in the following discussion the variables $Γ$ and $Ω$ are styled $2Γ$ or $2Ω$ for the 2D problem, and $3Γ$ or $3Ω$ for the 3D problem.

For the 2D TO formulation, computation of the triangular mesh is straightforward. We denote the 2D-domain containing the output component $2Ω$, and its boundary to be $2Γ$. We first utilize the contour-calculating method of [38] to find the level set Display Formula

(8)$2Γρ={x∈Ω0 : ρd(x)=ρmin}$

Because the value of density at some points on the initial boundary of the TO domain may exceed the cutoff value, $2Γρ$ does not hold the entire boundary of $2Ω$. This is illustrated in Fig. 6(a). We must also account for the boundary of $Ω0$, which is denoted $2Γ0$. At this point, $2Γρ$ and $2Γ0$ are disjoint sets of line segments. We split the elements of $2Γ0$ if they are intersected by a member of $2Γρ$ into two line segments with a common endpoint at the intersection. We then discard any elements of $2Γ0$ that have a value of $ρd(x)<ρmin$ at either endpoint. We then take $2Γ= 2Γρ ∪ 2Γ¯0$, with $2Γ¯0$ indicating the trimmed set of boundary segments. This is shown in Figs. 6(b) and 6(c).

With $2Γ$ known, the reconstruction of the domain $2Ω$ may be achieved using several well-known algorithms. In the present work, we utilize constrained Delaunay triangulation for this purpose. This approach is given in detail by Chew [65] and Sloan [66], implemented in several high-quality freely available software libraries, [67,68], and also available in commonly used computer algebra tools such as mathematica and matlab. The results of the Delaunay triangulation of $2Γ$ are shown in Fig. 6(d).

Once $2Ω$ has been calculated, what remains is to calculate $3Γ$, the final 3D surface mesh that will be processed by the AM digital thread. We make two copies of $2Ω$ and project both from 2D to 3D space. The z coordinate of the first copy is set to zero and that of the second is set to the prespecified thickness t. The two copies are then connected by a series of facets connecting corresponding line segments in both copies. The final result is shown in Fig. 6(e). Notably, the geometry calculated in this fashion is invariant along the z-axis and is, therefore, very simple to produce using virtually any AM technology.

###### Implicit Slicing for the Mesoscale.

With ρd determined by the topology optimizer, it is a straightforward matter to compute the AM toolpath using the implicit slicer as shown in Fig. 4. In previous work, it was necessary to determine the planar domain ωi for the ith slice by intersecting the input geometry model with a slicing plane. Here, the domain for each slice is determined by a level set of the TO density output, as seen in Fig. 5(c). Additionally, it is assumed that all slices will have the same bounding geometry, resulting in “2.5D” structures. Under such assumptions Display Formula

(9)$ωi=Ω∀i$

The output toolpath, sometimes known as “g-code” and hence denoted g, is partitioned into separate components Display Formula

(10)$g=gpr⊎gin$

where the $⊎$ operator indicates an optimized interleaved sequencing of toolpath segments. gpr and gin are associated with the perimeter and infill portions of the toolpath, respectively. The perimeters and infill are dictated by separate functions and level sets Display Formula

(11)$gpr≡⊎i=0nl⊎k=0nkHpr(x)=ck,x∈ωi$
Display Formula
(12)$gin≡⊎i=0nl⊎k=0nkHin(x)=ĉk,x∈ωi$

The most fundamental requirement of the slicer is that the output toolpath must replicate the geometry of the input model. This suggests the form Display Formula

(13)$Hpr(x)=c0,x∈γi$

where γi is the boundary of ωi. Since the shape of γ must be strongly encoded in Hpr, the signed distance transform is the most logical selection for this function. With this choice Display Formula

(14)$Hpr(x)={min‖x−xγ‖,xγ∈γix∈ωi−min‖x−xγ‖,xγ∈γiotherwise$

From previous work [38], we conclude that it is not feasible to directly compute the contours of ρd to produce gin. Instead, we first compute a purely rectilinear grid infill, as used in many existing slicers, as Display Formula

(15)$Hlin(x,θ)=xx sin(θ)+xy cos(θ)(−1(xz/lt)%2)$

where $xx$ and $xy$ are the Cartesian coordinates within each slice, $xz$ is the Cartesian coordinate normal to the slices, lt is the nominal layer thickness, and % indicates the arithmetic modulo operator. This function creates a grid of parallel diagonal lines, rotated by θ from the x-axis for each slice's infill, which flip about the y-axis every other layer. The linear infill is subsequently modulated according to the value of ρd in order to produce infill that is denser in high-stress regions. As is common in existing slicers, a value of $θ=π/4$ is used. The infill function, thus, takes the form Display Formula

(16)$Hin(x,y,z)=ρd(x)Hlin(x,π/4)k$

where k is a scalar parameter that controls the total mass of the final component. A visualization of the field functions σvm, Hlin, and Hin, for the same problem shown in Fig. 5 is given in Fig. 7. From Fig. 7(f), in particular, it is clear that the implicit slicer concentrates the infill in the high-density areas indicated by the topology optimizer. The complete bracket toolpath is shown in Fig. 8. The 2.5D nature of the resulting component is clearly visible, as is the stackup of infill toolpaths over multiple layers.

###### Optimized Toolpath Sequencing.

One aspect of toolpath generation that was not addressed in the previous development of the implicit slicer [38,39] was the sequencing of output toolpaths in order to achieve optimal production times. With the expectation of an extensive experimental validation campaign, we decided to address this shortcoming in order to produce large numbers of test articles efficiently. Because the implicit slicer is currently implemented in the mathematica computational system, we had a large number of analysis routines readily available. Therefore, we recast the trajectory sequencing problem as a classic traveling salesman problem (TSP) [69]. For the toolpaths corresponding to each layer of the build, we form a graph G consisting of a set of vertices V and edges E. We take the vertex set to be the union of the endpoints of each distinct segment of the toolpath Display Formula

(17)$V=∪ig¯ini∪g¯pri$
and the edge weights Eij are given by Display Formula
(18)$Eij={−‖Vi−Vj‖Vi and Vj connected in g‖Vi−Vj‖otherwise$

The edge weights encode the distance between vertices, however, that distance is negated if vertices i and j are connected by the toolpath. Since each toolpath segment in g has exactly two endpoints, this may be implemented by a trivial scheme based on the indices; Eij has a negative weight if i is odd and $j=i+1$ or i is even and $j=i−1$. An example graph formed using these definitions is shown in Fig. 9. The negation of weights ensures that the edge corresponding to each segment of g will be traversed once in the final Hamiltonian cycle that satisfies the TSP. Due to the economic significance of the TSP, very powerful algorithms exist for finding an optimal cycle. The present work utilizes a simulated annealing algorithm to find the solution to the TSP. While such a solution cannot be proved to be the global optimum in finite time but is sufficient for practical purposes. Once the optimal Hamiltonian cycle is found by the TSP algorithm, the optimal sequencing of the toolpaths can be recovered trivially.

## Demonstration Results

The approach outlined in Sec. 3 allows the practical application of multiscale topology optimization for common engineering design problems. We sought to find an illustrative example of this capability and found such an example during the construction of a uniaxial test machine. We required a spanner wrench to adjust the oddly shaped fasteners pictured in Fig. 10. The wrench for such a nut must be compact, lightweight, and support the load applied to tighten the fastener; an ideal candidate for topology optimization. The initial domain for the wrench geometry, along with applied loads and constraints, are also shown in Fig. 10.

The methodology outlined previously was applied, using largely the same settings. The mesh size parameter of $h0=0.5mm$ and $hmax=1.0mm$ were used, and the volume fraction was increased to 0.5. Because of the fine mesh, 14 min and 50 s were required for the comsol topology optimizer to converge. The layer thickness lt was set at 0.5 mm, and the overall height was 10 mm. The implicit slicing required approximately 1 s per layer (50 s total) of computation time on a dual-core laptop computer. The topology optimizer and implicit slicer results, along with the final toolpath may be seen in Fig. 11.

The output toolpath was formatted into “g-code” for an FDM 3D printer. Printing of the wrench required approximately 20 min. The finished component may be seen in Fig. 11(f). We note that the wrench is of adequate strength for the task of tightening the fastener shown.

## Discussion and Future Work

In this paper we have discussed work conducted toward the goal of developing a multiscale topology optimization framework for AM that is enabled by combining implicit slicing for the meso-scale, with TO for the macro-scale. The results presented in the prior section demonstrate significant progress in this pursuit. It was demonstrated that the generation of 2.5D structural components, such as a bracket and a wrench, can be optimized and produced using the proposed framework and applying it with FDM AM. However, it is clear that there is a great deal of work required to improve and refine this framework. Items of particular importance include extension to true 3D objects, incorporation of TO formulations beyond the simple SIMP model, and rigorous experimental validation.

###### Planned Implementation Extensions.

The methodology explored in this paper is readily extensible to 3D. Both the topology optimizer and implicit slicer are capable of conducting 3D analyses, the only change required is to relax the constraint $ωi=Ω∀i$. As a result, there will be a distinct $Ω$ and Hin will be a function of a 3D coordinate. However, we note that topology optimization in three dimensions may be extremely costly in computational terms.

The implementation of the methodology presented in this paper should also be extended to other AM techniques beside FDM. This will require process–specific, and possibly manufacturer or machine-specific translators in order to produce appropriately formatted and sequenced output commands. Additionally, some fabrication processes (e.g., selective laser melting of metals) tend to produce parts with 100% solid infill. As a result, it may be desirable to develop optimization formulations that are based on criteria, such as reducing residual stress/strain, instead of mechanical performance.

###### Planned Optimization Formulations.

The SIMP model used in the present work is widespread and easy to implement but has several shortcomings. Because it assumes a linear-isotropic material domain, the “optimal” topology produced may not be valid for an AM-produced material (that is, presumably not isotropic). Further effort is required to determine the most appropriate TO formulation, perhaps considering plane-isotropic or orthotropic constitutive models. However, this may not be a readily tractable problem, since the anisotropy depends heavily on the slicing results. A multimaterial TO formulation such as that of Ref. [70] may be more appropriate in this case.

In addition, there is a parametric optimization problem implied by the formulation of the present work. The free variables k and θ (slice density and orientation) are selected according to common practice but actually define a parametric optimization problem. While the effect of k is easy to predict (denser infill leading to increased stiffness and strength), its effect on specific properties (e.g., stiffness/mass) is more difficult to predict. Experience with orthotropic materials such as composites strongly suggests that θ will play an important role in the properties of the as-produced structure. It is clear that the optimal values of these variables must be determined either from, or in conjunction with, the topology optimization. The best method for accomplishing this without experimental testing is not readily apparent and may depend on the particular TO formulation employed.

Finally, we note that the multiscale optimization approach may be utilized to achieve tailored functional performance, as measured by criteria other than the strain energy formulation of Eq. (3). Because the implicit slicer can generate infill based on any input function, the TO algorithm may be selected with considerable freedom. One readily implementable example is the use of a TO objective function which penalizes deviation from a prespecified deformation profile, in order to generate a component with desired flexture properties.

On one hand, the present work offers an immediate path forward for the production of lightweight functional structures using AM. On the other hand, viewed more broadly, the present work represents one possible path toward an improved digital thread. As Gao et al. [17] makes clear, there is a broad interest in (and much research devoted to) such improvements. Re-examining Fig. 1, differences from the multiscale topology optimization framework become clear. In this new scheme, the triangularization and layout steps are not present. Instead, the geometry and boundary conditions specified by the designer are directly incorporated by the topology optimizer, rendering the reintroduction of design intent at the slicer stage unnecessary. The reinterpretation of the digital thread using the present work is given in Fig. 12.

We imagine that the various steps in the existing “preprocessing environment,” which are largely based on heuristics, may be replaced by an “design optimization environment” that encapsulates the present work. Importantly, the steps in the optimization environment are driven by algorithms that explicitly seek to tailor the AM component for some functional purpose. Additionally, the geometric input of the digital thread is replaced with a design specification, which includes geometry and functional specifications such as boundary conditions. The production environment remains unchanged, reflecting the desire to make the reinterpreted digital thread compatible with existing hardware systems.

Although the present work represents only the initial steps toward one possible reimagining the digital thread, it shows great potential. Despite the magnitude of future research effort that remains, the idea of multiscale topology optimization via combining TO with implicit slicing to achieve multiscale TO has been shown to offer unique possibilities for realizing many benefits of additive manufacturing that are currently unavailable and can be further extended to apply beyond structural to multiphysics performance requirements.

## Acknowledgements

• Office of Naval Research through the Naval Research Laboratory's core funding as well as the National Research Council's Research Associateship Program.

• The National Institute of Standards and Technology (Inter-agency Agreement NIST IAA-2018-0011-0).

## References

Zegard, T. , and Paulino, G. H. , 2016, “Bridging Topology Optimization and Additive Manufacturing,” Struct. Multidiscip. Optim., 53(1), pp. 175–192.
Brackett, D. , Ashcroft, I. , and Hague, R. , 2011, “Topology Optimization for Additive Manufacturing,” Solid Freeform Fabrication Symposium, Austin, TX, pp. 348–362.
Steuben, J. C. , Iliopoulos, A. P. , and Michopoulos, J. G. , 2017, “Towards Multiscale Topology Optimization for Additively Manufactured Components Using Implicit Slicing,” ASME Paper No. DETC2017-67596.
Steuben, J. C. , Michopoulos, J. G. , Iliopoulos, A. P. , and Birnbaum, A. J. , 2017, “Functional Performance Tailoring of Additively Manufactured Components Via Topology Optimization,” ASME Paper No. DETC2017-67600.
Jacobs, P. F. , 1992, Rapid Prototyping & Manufacturing: Fundamentals of Stereolithography, Society of Manufacturing Engineers, Dearborn, MI.
Hutmacher, D. W. , Schantz, T. , Zein, I. , Ng, K. W. , Teoh, S. H. , and Tan, K. C. , 2001, “Mechanical Properties and Cell Cultural Response of Polycaprolactone Scaffolds Designed and Fabricated Via Fused Deposition Modeling,” J. Biomed. Mater. Res., 55(2), pp. 203–216. [PubMed]
Gibson, I. , and Shi, D. , 1997, “Material Properties and Fabrication Parameters in Selective Laser Sintering Process,” Rapid Prototyping J., 3(4), pp. 129–136.
Kruth, J. , Wang, X. , Laoui, T. , and Froyen, L. , 2003, “Lasers and Materials in Selective Laser Sintering,” Assem. Autom., 23(4), pp. 357–371.
Kruth, J. , Mercelis, P. , Vaerenbergh, J. V. , Froyen, L. , and Rombouts, M. , 2005, “Binding Mechanisms in Selective Laser Sintering and Selective Laser Melting,” Rapid Prototyping J., 11(1), pp. 26–36.
Murr, L. E. , Gaytan, S. M. , Ramirez, D. A. , Martinez, E. , Hernandez, J. , Amato, K. N. , Shindo, P. W. , Medina, F. R. , and Wicker, R. B. , 2012, “Metal Fabrication by Additive Manufacturing Using Laser and Electron Beam Melting Technologoies,” J. Mater. Sci. Technol., 28(1), pp. 1–14.
Lewis, G. K. , and Schlienger, E. , 2000, “Practical Considerations and Capabilities for Laser Assisted Direct Metal Deposition,” Mater. Des., 21(4), pp. 417–423.
Mazumder, J. , Dutta, D. , Kikuchi, N. , and Ghosh, A. , 2000, “Closed Loop Direct Metal Deposition: Art to Part,” Opt. Lasers Eng., 34(4–6), pp. 397–414.
Livesu, M. , Ellero, S. , Martínez, J. , Lefebvre, S. , and Attene, M. , 2017, “From 3D Models to 3D Prints: An Overview of the Processing Pipeline,” Computer Graphics Forum, Vol. 36, Wiley, Hoboken, NJ, pp. 537–564.
Huotilainen, E. , Jaanimets, R. , Valášek, J. , Marcián, P. , Salmi, M. , Tuomi, J. , Mäkitie, A. , and Wolff, J. , 2014, “Inaccuracies in Additive Manufactured Medical Skull Models Caused by the DICOM to STL Conversion Process,” J. Cranio-Maxillofacial Surg., 42(5), pp. e259–e265.
Chernov, N. , Stoyan, Y. , and Romanova, T. , 2010, “Mathematical Model and Efficient Algorithms for Object Packing Problem,” Comput. Geom., 43(5), pp. 535–553.
Gibson, I. , Rosen, D. , and Stucker, B. , 2015, “Software Issues for Additive Manufacturing,” Additive Manufacturing Technologies SE - 15, Springer, New York, pp. 351–374.
Gao, W. , Zhang, Y. , Ramanujan, D. , Ramani, K. , Chen, Y. , Williams, C. B. , Wang, C. C. , Shin, Y. C. , Zhang, S. , and Zavattieri, P. D. , 2015, “The Status, Challenges, and Future of Additive Manufacturing in Engineering,” Comput.-Aided Des., 69, pp. 65–89.
Pandey, P. M. , Reddy, N. V. , and Dhande, S. G. , 2003, “Slicing Procedures in Layered Manufacturing: A Review,” Rapid Prototyping J., 9(5), pp. 274–288.
Luo, R. , and Ma, Y. , 1995, “A Slicing Algorithm for Rapid Prototyping and Manufacturing,” IEEE International Conference on Robotics and Automation (ICRA), Nagoya, Japan, May 21–27.
Jamieson, R. , and Hacker, H. , 1995, “Direct Slicing of CAD Models for Rapid Prototyping,” Rapid Prototyping J., 1(2), pp. 4–12.
Tata, K. , Fadel, G. , Bagchi, A. , and Aziz, N. , 1998, “Efficient Slicing for Layered Manufacturing,” Rapid Prototyping J., 4(4), pp. 151–167.
Tyberg, J. , and Bøhn, J. H. , 1998, “Local Adaptive Slicing,” Rapid Prototyping J., 4(3), pp. 118–127.
Ma, W. , and He, P. , 1999, “Adaptive Slicing and Selective Hatching Strategy for Layered Manufacturing,” J. Mater. Process. Technol., 89–90, pp. 191–197.
Hope, R. L. , Roth, R. N. , and Jacobs, P. A. , 1997, “Adaptive Slicing With Sloping Layer Surfaces,” Rapid Prototyping J., 3(3), pp. 89–98.
Sabourin, E. , Houser, S. A. , and Bøhn, J. H. , 1996, “Adaptive Slicing Using Stepwise Uniform Refinement,” Rapid Prototyping J., 2(4), pp. 20–26.
Xu, F. , Wong, Y. S. , Loh, H. T. , Fuh, J. Y. H. , and Miyazawa, T. , 1997, “Optimal Orientation With Variable Slicing in Stereolithography,” Rapid Prototyping J., 3(3), pp. 76–88.
Yang, P. , and Qian, X. , 2008, “Adaptive Slicing of Moving Least Squares Surfaces: Toward Direct Manufacturing of Point Set Surfaces,” ASME J. Comput. Inf. Sci. Eng., 8(3), p. 031003.
Yang, Y. , Loh, H. , Fuh, J. , and Wang, Y. , 2002, “Equidistant Path Generation for Improving Scanning Efficiency in Layered Manufacturing,” Rapid Prototyping J., 8(1), pp. 30–37.
Qiu, D. , and Langrana, N. A. , 2002, “Void Eliminating Toolpath for Extrusion-Based Multi-Material Layered Manufacturing,” Rapid Prototyping J., 8(1), pp. 38–45.
Siraskar, N. , Paul, R. , and Anand, S. , 2015, “Adaptive Slicing in Additive Manufacturing Process Using a Modified Boundary Octree Data Structure,” ASME J. Manuf. Sci. Eng., 137(1), p. 011007.
Qiu, Y. , Zhou, X. , and Qian, X. , 2011, “Direct Slicing of Cloud Data With Guaranteed Topology for Rapid Prototyping,” Int. J. Adv. Manuf. Technol., 53(1–4), pp. 255–265.
Huang, P. , Wang, C. C. L. , and Chen, Y. , 2013, “Intersection-Free and Topologically Faithful Slicing of Implicit Solid,” ASME J. Comput. Inf. Sci. Eng., 13(2), p. 021009.
Huang, P. , Wang, C. C. L. , and Chen, Y. , 2014, Advances in Computers and Information in Engineering Research, Vol. 1, American Society of Mechanical Engineers, New York, pp. 377–409. [PubMed] [PubMed]
Lefebvre, S. , 2013, “IceSL: A GPU Accelerated CSG Modeler and Slicer,” 18th European Forum on Additive Manufacturing (AEFA13), Paris, France.
Schumacher, C. , Bickel, B. , Rys, J. , Marschner, S. , Daraio, C. , and Gross, M. , 2015, “Microstructures to Control Elasticity in 3D Printing,” ACM Trans. Graph., 34(4), p. 136.
Martínez, J. , Song, H. , Dumas, J. , and Lefebvre, S. , 2017, “Orthotropic k-Nearest Foams for Additive Manufacturing,” ACM Trans. Graph. (TOG), 36(4), p. 121.
Cramer, A. D. , Challis, V. J. , and Roberts, A. P. , 2017, “Physically Realizable Three-Dimensional Bone Prosthesis Design With Interpolated Microstructures,” ASME J. Biomech. Eng., 139(3), p. 031013.
Steuben, J. C. , Iliopoulos, A. P. , and Michopoulos, J. G. , 2016, “Implicit Slicing for Functionally Tailored Additive Manufacturing,” Comput.-Aided Des., 77, pp. 107–119.
Steuben, J. C. , Iliopoulos, A. P. , and Michopoulos, J. G. , 2016, “Implicit Slicing for Functionally Tailored Additive Manufacturing,” ASME Paper No. DETC2016-59638.
Bendsoe, M. P. , and Sigmund, O. , 2013, Topology Optimization: Theory, Methods, and Applications, Springer Science & Business Media, Berlin.
Eschenauer, H. A. , and Olhoff, N. , 2001, “Topology Optimization of Continuum Structures: A Review,” ASME Appl. Mech. Rev., 54(4), pp. 331–390.
Rozvany, G. I. , 2009, “A Critical Review of Established Methods of Structural Topology Optimization,” Struct. Multidiscip. Optim., 37(3), pp. 217–237.
Bendsøe, M. P. , 1989, “Optimal Shape Design as a Material Distribution Problem,” Struct. Optim., 1(4), pp. 193–202.
Sigmund, O. , 2001, “A 99 Line Topology Optimization Code Written in Matlab,” Struct. Multidiscip. Optim., 21(2), pp. 120–127.
Stolpe, M. , and Svanberg, K. , 2001, “An Alternative Interpolation Scheme for Minimum Compliance Topology Optimization,” Struct. Multidiscip. Optim., 22(2), pp. 116–124.
Munk, D. J. , Vio, G. A. , and Steven, G. P. , 2015, “Topology and Shape Optimization Methods Using Evolutionary Algorithms: A Review,” Struct. Multidiscip. Optim., 52(3), pp. 613–631.
Sethian, J. A. , and Wiegmann, A. , 2000, “Structural Boundary Design Via Level Set and Immersed Interface Methods,” J. Comput. Phys., 163(2), pp. 489–528.
Allaire, G. , Jouve, F. , and Toader, A.-M. , 2004, “Structural Optimization Using Sensitivity Analysis and a Level-Set Method,” J. Comput. Phys., 194(1), pp. 363–393.
Suresh, K. , 2010, “A 199-Line Matlab Code for Pareto-Optimal Tracing in Topology Optimization,” Struct. Multidiscip. Optim., 42(5), pp. 665–679.
Chen, J. , Shapiro, V. , Suresh, K. , and Tsukanov, I. , 2007, “Shape Optimization With Topological Changes and Parametric Control,” Int. J. Numer. Methods Eng., 71(3), pp. 313–346.
Stegmann, J. , and Lund, E. , 2005, “Discrete Material Optimization of General Composite Shell Structures,” Int. J. Numer. Methods Eng., 62(14), pp. 2009–2027.
Deng, S. , and Suresh, K. , 2017, “Topology Optimization Under Thermo-Elastic Buckling,” Struct. Multidiscip. Optim., 55(5), pp. 1759–1772.
Harzheim, L. , and Graf, G. , 2006, “A Review of Optimization of Cast Parts Using Topology Optimization,” Struct. Multidiscip. Optim., 31(5), pp. 388–399.
Coverstone-Carroll, V. , Hartmann, J. , and Mason, W. , 2000, “Optimal Multi-Objective Low-Thrust Spacecraft Trajectories,” Comput. Methods Appl. Mech. Eng., 186(2–4), pp. 387–402.
Alonso, J. J. , LeGresley, P. , and Pereyra, V. , 2009, “Aircraft Design Optimization,” Math. Comput. Simul., 79(6), pp. 1948–1958.
Wang, X. , Xu, S. , Zhou, S. , Xu, W. , Leary, M. , Choong, P. , Qian, M. , Brandt, M. , and Xie, Y. M. , 2016, “Topological Design and Additive Manufacturing of Porous Metals for Bone Scaffolds and Orthopaedic Implants: A Review,” Biomaterials, 83, pp. 127–141. [PubMed]
Robbins, J. , Owen, S. , Clark, B. , and Voth, T. , 2016, “An Efficient and Scalable Approach for Generating Topologically Optimized Cellular Structures for Additive Manufacturing,” Addit. Manuf., 12(Pt. B), pp. 296–304.
Quan, Z. , Larimore, Z. , Wu, A. , Yu, J. , Qin, X. , Mirotznik, M. , Suhr, J. , Byun, J.-H. , Oh, Y. , and Chou, T.-W. , 2016, “Microstructural Design and Additive Manufacturing and Characterization of 3D Orthogonal Short Carbon Fiber/Acrylonitrile-Butadiene-Styrene Preform and Composite,” Compos. Sci. Technol., 126, pp. 139–148.
Gaynor, A. T. , Meisel, N. A. , Williams, C. B. , and Guest, J. K. , 2014, “Topology Optimization for Additive Manufacturing: Considering Maximum Overhang Constraint,” AIAA Paper No. 2014-2036.
Wu, J. , Clausen, A. , and Sigmund, O. , 2017, “Minimum Compliance Topology Optimization of Shell-Infill Composites for Additive Manufacturing,” Comput. Methods Appl. Mech. Eng., 326, pp. 358–375.
Jiang, L. , Ye, H. , Zhou, C. , Chen, S. , and Xu, W. , 2017, “Parametric Topology Optimization Toward Rational Design and Efficient Prefabrication for Additive Manufacturing,” ASME Paper No. MSEC2017-2954.
Comsol, 2015, “Comsol Multiphysics, Version 5,” Comsol, Burlington, MA.
Amestoy, P. R. , Duff, I. S. , LExcellent, J.-Y. , and Koster, J. , 2000, “Mumps: A General Purpose Distributed Memory Sparse Solver,” International Workshop on Applied Parallel Computing, Bergen, Norway, June 18–20, pp. 121–130.
Svanberg, K. , 1987, “The Method of Moving Asymptotes—A New Method for Structural Optimization,” Int. J. Numer. Methods Eng., 24(2), pp. 359–373.
Chew, L. P. , 1989, “Constrained Delaunay Triangulation,” Algorithmica, 4(1–4), pp. 97–108.
Sloan, S. W. , 1993, “A Fast Algorithm for Generating Constrained Delaunay Triangulations,” Comput. Struct., 47(3), pp. 441–450.
Shewchuk, J. R. , 1996, “Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator,” Applied Computational Geometry Towards Geometric Engineering, Vol. 1148, Springer, Berlin, pp. 203–222.
Si, H. , 2015, “TetGen a Delaunay-Based Quality Tetrahedral Mesh Generator,” ACM Trans. Math. Software, 41(2), pp. 1--36.
Kruskal, J. B. , 1956, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proc. Am. Math. Soc., 7(1), pp. 48–50.
Mirzendehdel, A. M. , and Suresh, K. , 2015, “A Pareto-Optimal Approach to Multimaterial Topology Optimization,” ASME J. Mech. Des., 137(10), p. 101701.
View article in PDF format.

## References

Zegard, T. , and Paulino, G. H. , 2016, “Bridging Topology Optimization and Additive Manufacturing,” Struct. Multidiscip. Optim., 53(1), pp. 175–192.
Brackett, D. , Ashcroft, I. , and Hague, R. , 2011, “Topology Optimization for Additive Manufacturing,” Solid Freeform Fabrication Symposium, Austin, TX, pp. 348–362.
Steuben, J. C. , Iliopoulos, A. P. , and Michopoulos, J. G. , 2017, “Towards Multiscale Topology Optimization for Additively Manufactured Components Using Implicit Slicing,” ASME Paper No. DETC2017-67596.
Steuben, J. C. , Michopoulos, J. G. , Iliopoulos, A. P. , and Birnbaum, A. J. , 2017, “Functional Performance Tailoring of Additively Manufactured Components Via Topology Optimization,” ASME Paper No. DETC2017-67600.
Jacobs, P. F. , 1992, Rapid Prototyping & Manufacturing: Fundamentals of Stereolithography, Society of Manufacturing Engineers, Dearborn, MI.
Hutmacher, D. W. , Schantz, T. , Zein, I. , Ng, K. W. , Teoh, S. H. , and Tan, K. C. , 2001, “Mechanical Properties and Cell Cultural Response of Polycaprolactone Scaffolds Designed and Fabricated Via Fused Deposition Modeling,” J. Biomed. Mater. Res., 55(2), pp. 203–216. [PubMed]
Gibson, I. , and Shi, D. , 1997, “Material Properties and Fabrication Parameters in Selective Laser Sintering Process,” Rapid Prototyping J., 3(4), pp. 129–136.
Kruth, J. , Wang, X. , Laoui, T. , and Froyen, L. , 2003, “Lasers and Materials in Selective Laser Sintering,” Assem. Autom., 23(4), pp. 357–371.
Kruth, J. , Mercelis, P. , Vaerenbergh, J. V. , Froyen, L. , and Rombouts, M. , 2005, “Binding Mechanisms in Selective Laser Sintering and Selective Laser Melting,” Rapid Prototyping J., 11(1), pp. 26–36.
Murr, L. E. , Gaytan, S. M. , Ramirez, D. A. , Martinez, E. , Hernandez, J. , Amato, K. N. , Shindo, P. W. , Medina, F. R. , and Wicker, R. B. , 2012, “Metal Fabrication by Additive Manufacturing Using Laser and Electron Beam Melting Technologoies,” J. Mater. Sci. Technol., 28(1), pp. 1–14.
Lewis, G. K. , and Schlienger, E. , 2000, “Practical Considerations and Capabilities for Laser Assisted Direct Metal Deposition,” Mater. Des., 21(4), pp. 417–423.
Mazumder, J. , Dutta, D. , Kikuchi, N. , and Ghosh, A. , 2000, “Closed Loop Direct Metal Deposition: Art to Part,” Opt. Lasers Eng., 34(4–6), pp. 397–414.
Livesu, M. , Ellero, S. , Martínez, J. , Lefebvre, S. , and Attene, M. , 2017, “From 3D Models to 3D Prints: An Overview of the Processing Pipeline,” Computer Graphics Forum, Vol. 36, Wiley, Hoboken, NJ, pp. 537–564.
Huotilainen, E. , Jaanimets, R. , Valášek, J. , Marcián, P. , Salmi, M. , Tuomi, J. , Mäkitie, A. , and Wolff, J. , 2014, “Inaccuracies in Additive Manufactured Medical Skull Models Caused by the DICOM to STL Conversion Process,” J. Cranio-Maxillofacial Surg., 42(5), pp. e259–e265.
Chernov, N. , Stoyan, Y. , and Romanova, T. , 2010, “Mathematical Model and Efficient Algorithms for Object Packing Problem,” Comput. Geom., 43(5), pp. 535–553.
Gibson, I. , Rosen, D. , and Stucker, B. , 2015, “Software Issues for Additive Manufacturing,” Additive Manufacturing Technologies SE - 15, Springer, New York, pp. 351–374.
Gao, W. , Zhang, Y. , Ramanujan, D. , Ramani, K. , Chen, Y. , Williams, C. B. , Wang, C. C. , Shin, Y. C. , Zhang, S. , and Zavattieri, P. D. , 2015, “The Status, Challenges, and Future of Additive Manufacturing in Engineering,” Comput.-Aided Des., 69, pp. 65–89.
Pandey, P. M. , Reddy, N. V. , and Dhande, S. G. , 2003, “Slicing Procedures in Layered Manufacturing: A Review,” Rapid Prototyping J., 9(5), pp. 274–288.
Luo, R. , and Ma, Y. , 1995, “A Slicing Algorithm for Rapid Prototyping and Manufacturing,” IEEE International Conference on Robotics and Automation (ICRA), Nagoya, Japan, May 21–27.
Jamieson, R. , and Hacker, H. , 1995, “Direct Slicing of CAD Models for Rapid Prototyping,” Rapid Prototyping J., 1(2), pp. 4–12.
Tata, K. , Fadel, G. , Bagchi, A. , and Aziz, N. , 1998, “Efficient Slicing for Layered Manufacturing,” Rapid Prototyping J., 4(4), pp. 151–167.
Tyberg, J. , and Bøhn, J. H. , 1998, “Local Adaptive Slicing,” Rapid Prototyping J., 4(3), pp. 118–127.
Ma, W. , and He, P. , 1999, “Adaptive Slicing and Selective Hatching Strategy for Layered Manufacturing,” J. Mater. Process. Technol., 89–90, pp. 191–197.
Hope, R. L. , Roth, R. N. , and Jacobs, P. A. , 1997, “Adaptive Slicing With Sloping Layer Surfaces,” Rapid Prototyping J., 3(3), pp. 89–98.
Sabourin, E. , Houser, S. A. , and Bøhn, J. H. , 1996, “Adaptive Slicing Using Stepwise Uniform Refinement,” Rapid Prototyping J., 2(4), pp. 20–26.
Xu, F. , Wong, Y. S. , Loh, H. T. , Fuh, J. Y. H. , and Miyazawa, T. , 1997, “Optimal Orientation With Variable Slicing in Stereolithography,” Rapid Prototyping J., 3(3), pp. 76–88.
Yang, P. , and Qian, X. , 2008, “Adaptive Slicing of Moving Least Squares Surfaces: Toward Direct Manufacturing of Point Set Surfaces,” ASME J. Comput. Inf. Sci. Eng., 8(3), p. 031003.
Yang, Y. , Loh, H. , Fuh, J. , and Wang, Y. , 2002, “Equidistant Path Generation for Improving Scanning Efficiency in Layered Manufacturing,” Rapid Prototyping J., 8(1), pp. 30–37.
Qiu, D. , and Langrana, N. A. , 2002, “Void Eliminating Toolpath for Extrusion-Based Multi-Material Layered Manufacturing,” Rapid Prototyping J., 8(1), pp. 38–45.
Siraskar, N. , Paul, R. , and Anand, S. , 2015, “Adaptive Slicing in Additive Manufacturing Process Using a Modified Boundary Octree Data Structure,” ASME J. Manuf. Sci. Eng., 137(1), p. 011007.
Qiu, Y. , Zhou, X. , and Qian, X. , 2011, “Direct Slicing of Cloud Data With Guaranteed Topology for Rapid Prototyping,” Int. J. Adv. Manuf. Technol., 53(1–4), pp. 255–265.
Huang, P. , Wang, C. C. L. , and Chen, Y. , 2013, “Intersection-Free and Topologically Faithful Slicing of Implicit Solid,” ASME J. Comput. Inf. Sci. Eng., 13(2), p. 021009.
Huang, P. , Wang, C. C. L. , and Chen, Y. , 2014, Advances in Computers and Information in Engineering Research, Vol. 1, American Society of Mechanical Engineers, New York, pp. 377–409. [PubMed] [PubMed]
Lefebvre, S. , 2013, “IceSL: A GPU Accelerated CSG Modeler and Slicer,” 18th European Forum on Additive Manufacturing (AEFA13), Paris, France.
Schumacher, C. , Bickel, B. , Rys, J. , Marschner, S. , Daraio, C. , and Gross, M. , 2015, “Microstructures to Control Elasticity in 3D Printing,” ACM Trans. Graph., 34(4), p. 136.
Martínez, J. , Song, H. , Dumas, J. , and Lefebvre, S. , 2017, “Orthotropic k-Nearest Foams for Additive Manufacturing,” ACM Trans. Graph. (TOG), 36(4), p. 121.
Cramer, A. D. , Challis, V. J. , and Roberts, A. P. , 2017, “Physically Realizable Three-Dimensional Bone Prosthesis Design With Interpolated Microstructures,” ASME J. Biomech. Eng., 139(3), p. 031013.
Steuben, J. C. , Iliopoulos, A. P. , and Michopoulos, J. G. , 2016, “Implicit Slicing for Functionally Tailored Additive Manufacturing,” Comput.-Aided Des., 77, pp. 107–119.
Steuben, J. C. , Iliopoulos, A. P. , and Michopoulos, J. G. , 2016, “Implicit Slicing for Functionally Tailored Additive Manufacturing,” ASME Paper No. DETC2016-59638.
Bendsoe, M. P. , and Sigmund, O. , 2013, Topology Optimization: Theory, Methods, and Applications, Springer Science & Business Media, Berlin.
Eschenauer, H. A. , and Olhoff, N. , 2001, “Topology Optimization of Continuum Structures: A Review,” ASME Appl. Mech. Rev., 54(4), pp. 331–390.
Rozvany, G. I. , 2009, “A Critical Review of Established Methods of Structural Topology Optimization,” Struct. Multidiscip. Optim., 37(3), pp. 217–237.
Bendsøe, M. P. , 1989, “Optimal Shape Design as a Material Distribution Problem,” Struct. Optim., 1(4), pp. 193–202.
Sigmund, O. , 2001, “A 99 Line Topology Optimization Code Written in Matlab,” Struct. Multidiscip. Optim., 21(2), pp. 120–127.
Stolpe, M. , and Svanberg, K. , 2001, “An Alternative Interpolation Scheme for Minimum Compliance Topology Optimization,” Struct. Multidiscip. Optim., 22(2), pp. 116–124.
Munk, D. J. , Vio, G. A. , and Steven, G. P. , 2015, “Topology and Shape Optimization Methods Using Evolutionary Algorithms: A Review,” Struct. Multidiscip. Optim., 52(3), pp. 613–631.
Sethian, J. A. , and Wiegmann, A. , 2000, “Structural Boundary Design Via Level Set and Immersed Interface Methods,” J. Comput. Phys., 163(2), pp. 489–528.
Allaire, G. , Jouve, F. , and Toader, A.-M. , 2004, “Structural Optimization Using Sensitivity Analysis and a Level-Set Method,” J. Comput. Phys., 194(1), pp. 363–393.
Suresh, K. , 2010, “A 199-Line Matlab Code for Pareto-Optimal Tracing in Topology Optimization,” Struct. Multidiscip. Optim., 42(5), pp. 665–679.
Chen, J. , Shapiro, V. , Suresh, K. , and Tsukanov, I. , 2007, “Shape Optimization With Topological Changes and Parametric Control,” Int. J. Numer. Methods Eng., 71(3), pp. 313–346.
Stegmann, J. , and Lund, E. , 2005, “Discrete Material Optimization of General Composite Shell Structures,” Int. J. Numer. Methods Eng., 62(14), pp. 2009–2027.
Deng, S. , and Suresh, K. , 2017, “Topology Optimization Under Thermo-Elastic Buckling,” Struct. Multidiscip. Optim., 55(5), pp. 1759–1772.
Harzheim, L. , and Graf, G. , 2006, “A Review of Optimization of Cast Parts Using Topology Optimization,” Struct. Multidiscip. Optim., 31(5), pp. 388–399.
Coverstone-Carroll, V. , Hartmann, J. , and Mason, W. , 2000, “Optimal Multi-Objective Low-Thrust Spacecraft Trajectories,” Comput. Methods Appl. Mech. Eng., 186(2–4), pp. 387–402.
Alonso, J. J. , LeGresley, P. , and Pereyra, V. , 2009, “Aircraft Design Optimization,” Math. Comput. Simul., 79(6), pp. 1948–1958.
Wang, X. , Xu, S. , Zhou, S. , Xu, W. , Leary, M. , Choong, P. , Qian, M. , Brandt, M. , and Xie, Y. M. , 2016, “Topological Design and Additive Manufacturing of Porous Metals for Bone Scaffolds and Orthopaedic Implants: A Review,” Biomaterials, 83, pp. 127–141. [PubMed]
Robbins, J. , Owen, S. , Clark, B. , and Voth, T. , 2016, “An Efficient and Scalable Approach for Generating Topologically Optimized Cellular Structures for Additive Manufacturing,” Addit. Manuf., 12(Pt. B), pp. 296–304.
Quan, Z. , Larimore, Z. , Wu, A. , Yu, J. , Qin, X. , Mirotznik, M. , Suhr, J. , Byun, J.-H. , Oh, Y. , and Chou, T.-W. , 2016, “Microstructural Design and Additive Manufacturing and Characterization of 3D Orthogonal Short Carbon Fiber/Acrylonitrile-Butadiene-Styrene Preform and Composite,” Compos. Sci. Technol., 126, pp. 139–148.
Gaynor, A. T. , Meisel, N. A. , Williams, C. B. , and Guest, J. K. , 2014, “Topology Optimization for Additive Manufacturing: Considering Maximum Overhang Constraint,” AIAA Paper No. 2014-2036.
Wu, J. , Clausen, A. , and Sigmund, O. , 2017, “Minimum Compliance Topology Optimization of Shell-Infill Composites for Additive Manufacturing,” Comput. Methods Appl. Mech. Eng., 326, pp. 358–375.
Jiang, L. , Ye, H. , Zhou, C. , Chen, S. , and Xu, W. , 2017, “Parametric Topology Optimization Toward Rational Design and Efficient Prefabrication for Additive Manufacturing,” ASME Paper No. MSEC2017-2954.
Comsol, 2015, “Comsol Multiphysics, Version 5,” Comsol, Burlington, MA.
Amestoy, P. R. , Duff, I. S. , LExcellent, J.-Y. , and Koster, J. , 2000, “Mumps: A General Purpose Distributed Memory Sparse Solver,” International Workshop on Applied Parallel Computing, Bergen, Norway, June 18–20, pp. 121–130.
Svanberg, K. , 1987, “The Method of Moving Asymptotes—A New Method for Structural Optimization,” Int. J. Numer. Methods Eng., 24(2), pp. 359–373.
Chew, L. P. , 1989, “Constrained Delaunay Triangulation,” Algorithmica, 4(1–4), pp. 97–108.
Sloan, S. W. , 1993, “A Fast Algorithm for Generating Constrained Delaunay Triangulations,” Comput. Struct., 47(3), pp. 441–450.
Shewchuk, J. R. , 1996, “Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator,” Applied Computational Geometry Towards Geometric Engineering, Vol. 1148, Springer, Berlin, pp. 203–222.
Si, H. , 2015, “TetGen a Delaunay-Based Quality Tetrahedral Mesh Generator,” ACM Trans. Math. Software, 41(2), pp. 1--36.
Kruskal, J. B. , 1956, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proc. Am. Math. Soc., 7(1), pp. 48–50.
Mirzendehdel, A. M. , and Suresh, K. , 2015, “A Pareto-Optimal Approach to Multimaterial Topology Optimization,” ASME J. Mech. Des., 137(10), p. 101701.

## Figures

Fig. 1

An overview of the AM “digital thread” concept

Fig. 2

Illustration of toolpath concepts. Note the perimeter shells (black) that enclose a sparse infill pattern (red); this combination of path types is commonly used in AM applications.

Fig. 3

Example of implicit slicing. At top, the input geometry and applied force F. At center, the von Mises stress in the part, as calculated using FEA. At bottom, the toolpath produced by the implicit slicer.

Fig. 4

Flowchart of the workflow demonstrating the stages of the proposed multiscale methodology for TO

Fig. 5

TO example. At top (a) the original domain and boundary conditions are shown. At center (b), the output ρd is shown, with the cutoff value ρd=ρmin highlighted. At the bottom (c), the output domain Ω corresponding to ρd≥ρmin is highlighted: (a) TO domain, (b) results of TO, and (c) output domain from TO.

Fig. 11

Multiscale TO of the wrench. At top (a), the density function is computed by the topology optimizer. Below (b) is the domain Ω upon which the implicit slicer operates. The infill function Hin is shown, for the first two layers, in (c). In (d) and (e) the output toolpath can be seen. At bottom (f), the FDM-manufactured wrench is photographed: (a) ρd(x), (b) Ω, (c) Hin for z = 0 and z=lt, (d) ρd(x) with gin∪gpr superimposed, (e) output toolpath, and (f) photograph of as-manufactured wrench.

Fig. 8

Complete bracket toolpath in 3D space. All slices are of the same bounding geometry, resulting in a 2.5D part.

Fig. 7

TO example. (a) the density field from the topology optimizer. (b, c) the corresponding linear infill function defined over the first and second layers. (d, e) the modulated infill function for the first and second layers. (f) contours corresponding to the infill for the first two layers superimposed, along with the perimeter contours: (a) ρd(x), (b) Hlin(x) for z = 0, (c) Hlin(x) for z=lt, (d) Hin(x) for z = 0, (e) Hin(x) for z=lt, and (f) superimposed infill for first two layers.

Fig. 6

Steps for computing the 2D and 3D domains: (a) 2Γρ, (b) 2Γρ ∪ 2Γ0, (c) Γ=2Γρ ∪ 2Γ0¯, and (d) 2Ω, and (e) 3Γ

Fig. 10

The fastener that the spanner must drive (top), and the corresponding dimensions and boundary conditions on the outer envelope of the spanner wrench

Fig. 9

Illustration of the graph formulation for optimal toolpath sequencing. The original toolpath segments are shown in bold, with the vertices Vi on either end. The negative-weight edges connecting the endpoints of the original segments are bold and dashed. The positive weight edges representing movement between toolpath segments are shown by light dashed lines.

Fig. 12

The reinterpreted digital thread incorporating an optimization environment

## Errata

Some tools below are only available to our subscribers or users with an online account.

### Related Content

Customize your page view by dragging and repositioning the boxes below.

Related Journal Articles
Related Proceedings Articles
Related eBook Content
Topic Collections


text:
## Intermediate Algebra: Connecting Concepts through Application

$\color{blue}{2}$
The rational expressions have the same denominator so they are similar. Add the numerators and copy the denominator to obtain: $=\dfrac{b-3+b-15}{b-9} \\=\dfrac{2b-18}{b-9}$ Factor out $2$ in the numerator to obtain: $\\=\dfrac{2(b-9)}{b-9}$ Cancel the common factors to obtain: $\\=\color{blue}{2}$