Quick Reference
By LOG-UFPB.
Welcome to Quick Reference, a collection of useful knowledge that can be accessed quickly.
The effort of one person to understand how to solve a problem should be recorded so that others in the same situation only need to consult the QR instead of going through the same struggle. Besides, random knowledge such as links (to videos or websites), libraries, tips, and tricks can be useful to many people but are not always intuitive to find or use. Therefore, documenting them is important.
Here, you will find quick references related to the topics below and more:
- Programming
- Optimization
- Mathematics
- Data science
The QR is Markdown-based book created with mdBook, just like The Rust Programming Language and Helix Documentation.
Data structures
Vector
They store a group of elements, sequentially.
- Part of the C++ STL
- Implementation: Arrays that can be reallocated in case they exceed a specific size.
- Time complexity for the main operations:
- Insertion of elements at the end of the vector: \(O(1)\)
- Insertion of elements in the middle of the vector: \(O(n)\)
- Removal of elements at the end of the vector: \(O(1)\)
- Removal of elements in the middle of the vector: \(O(n)\)
- Search for an element in a certain position: \(O(1)\)
- Search for an element with a certain value: \(O(n)\)
Priority queues
They store a group of elements sequentially, and efficiently obtain its maximum or minimum value.
- Part of the C++ STL
- Implementation: Max/Min Heap
- Time complexity for the main operations:
- Insertion of any element: \(O(\log n)\)
- Removal of any element: \(O(\log n)\)
- Search for the maximum/minimum value: \(O(1)\)
Set
They efficiently store a group of non-repeating elements.
- Part of the C++ STL
- Implementation: Binary Search Trees
- Time complexity for the main operations:
- Insertion of any element: \(O(\log n)\)
- Removal of any element: \(O(\log n)\)
- Search for an element with a certain value: \(O(\log n)\)
Map
They store elements of type <key, value> efficiently avoiding key repetition (repetition of values is possible).
- Part of the C++ STL
- Implementation: Binary Search Trees
- Time complexity for the main operations:
- Insertion of any element: \(O(\log n)\)
- Removal of any element: \(O(\log n)\)
- Search for an element with a certain key: \(O(\log n)\)
Disjoint Set Union
This data structure stores a collection of sets without element overlap. It allows for efficient operations to create and join sets, as well as checking if two elements are part of the same set. Disjoint Set Union is used in efficient implementations of the Kruskal algorithm for finding the Minimum Spanning Tree of a graph.
- Not a part of the C++ STL
- Implementation: Vectors or Arrays
- Time complexity for the main operations:
- Create a set: \(O(1)\)
- Join two sets: \(\approx O(1)\)
- Search for a set of a certain element: \(\approx O(1)\)
- Check if two elements are part of the same set: \(\approx O(1)\)
Example:
#include <iostream>
#include <vector>
using namespace std;
class Disjointed_set_union{
private:
struct Element{
int root;
int rank;
Element() = default;
Element(int root) : root(root), rank(1){}
};
vector<Element> map;
public:
Disjointed_set_union(int total_elements){
map.resize(total_elements);
}
void make_set(int value){
int last_idx = map.size();
map[value] = Element(value);
}
int find(int value){
if(map[value].root == value){
return value;
}
return map[value].root = find(map[value].root);
}
void union_sets(int value_1, int value_2){
int root_1 = find(value_1);
int root_2 = find(value_2);
if (root_1 != root_2){
int rank_1 = map[root_1].rank;
int rank_2 = map[root_2].rank;
if(rank_1 > rank_2){
map[root_2].root = root_1;
}else if(rank_1 < rank_2){
map[root_1].root = root_2;
}else{
map[root_2].root = root_1;
map[root_1].rank++;
}
}
}
bool is_same_set(int value_1, int value_2){
return find(value_1) == find(value_2);
}
};
int main(){
// The elements are numbered from 1 to 4 to match the figure above
int max_elements = 5;
Disjointed_set_union dsu(max_elements); // Max of elements is 4
dsu.make_set(1);
dsu.make_set(2);
dsu.make_set(3);
dsu.make_set(4);
for(int i = 1; i < max_elements; ++i){
for(int j = i+1; j < max_elements; ++j){
if (dsu.is_same_set(i, j)){
printf("%d and %d are in the same set\n", i, j);
}else{
printf("%d and %d are not in the same set\n", i, j);
}
}
}
printf("\n ------------- \n\n");
dsu.union_sets(1, 2);
for(int i = 1; i < max_elements; ++i){
for(int j = i+1; j < max_elements; ++j){
if (dsu.is_same_set(i, j)){
printf("%d and %d are in the same set\n", i, j);
}else{
printf("%d and %d are not in the same set\n", i, j);
}
}
}
printf("\n ------------- \n\n");
dsu.union_sets(3, 4);
for(int i = 1; i < max_elements; ++i){
for(int j = i+1; j < max_elements; ++j){
if (dsu.is_same_set(i, j)){
printf("%d and %d are in the same set\n", i, j);
}else{
printf("%d and %d are not in the same set\n", i, j);
}
}
}
printf("\n ------------- \n\n");
dsu.union_sets(1, 3);
for(int i = 1; i < max_elements; ++i){
for(int j = i+1; j < max_elements; ++j){
if (dsu.is_same_set(i, j)){
printf("%d and %d are in the same set\n", i, j);
}else{
printf("%d and %d are not in the same set\n", i, j);
}
}
}
return 0;
}
It is possible to use unordered_map instead of vector for a more general implementation.
Graphs (adjacency list)
They represent sparse graphs when it is necessary to know which arcs touch a certain vertex. This data structure is efficient in memory spaces when compared to other implementations (e.g., adjacency matrix). Moreover, they can be more efficient, time-wise, for algorithms such as breadth-first search and depth-first search.
- Not a part of the C++ STL
- Implementation: Vector of vectors
- Time complexity for the main operations:
- Insertion of elements at the end of the vector: \(O(1)\)
- Removal of elements at the end of the vector: \(O(1)\)
- Check the existence of an arc between any two vertices: \(O(n)\)
Example:
#include<cstdio>
#include<vector>
using namespace std;
int main(){
int total_nodes = 4;
vector<vector<int>> graph(total_nodes); // initialise with 4 empty vectors
graph[0].push_back(1); // adds an arc from 0 to 1
graph[1].push_back(2); // adds an arc from 1 to 2
graph[1].push_back(4); // adds an arc from 1 to 4
graph[2].push_back(3); // adds an arc from 2 to 3
graph[3].push_back(0); // adds an arc from 3 to 0
graph[3].push_back(1); // adds an arc from 3 to 1
graph[4].push_back(3); // adds an arc from 4 to 3
// iterate over the arcs from each vertex
for(int i = 0; i < total_nodes; ++i){
for(auto j : graph[i]){
printf("There is an arc from %d to %d\n", i, j);
}
}
return 0;
}
Graphs (adjacency matrix)
They represent dense graphs when it is necessary to know if there is an arc between any two vertices or its cost in weighted graphs.
- Not a part of the C++ STL
- Implementation: Array of arrays or vector of vectors. It is important it is a matrix \(n \times n\).
- Time complexity for the main operations:
- Insertion of an arc: \(O(1)\)
- Removal of an arc: \(O(1)\)
- Changing an arc: \(O(1)\)
- Check the existence of an arc between any two vertices: \(O(1)\)
- Obtain the cost of an arc between any two vertices: \(O(1)\)
- Insertion of a vertex costs the same as a matrix reallocation for an array of arrays or the vertex insertion in each vector when implementing this structure as a vector of vectors.
Example:
#include<cstdio>
#include<vector>
using namespace std;
int main(){
int total_nodes = 5;
int graph_arr[total_nodes][total_nodes] = {
{0, 3, 0, 7, 8},
{3, 0, 1, 4, 0},
{0, 1, 0, 2, 0},
{7, 4, 2, 0, 3},
{8, 0, 0, 3, 0}
};
// iterate over the vertices
for(int i = 0; i < total_nodes; ++i){
for(int j = i+1; j < total_nodes; ++j){
if(graph_arr[i][j])
printf("There is an edge from %d to %d with cost: %d\n", i, j, graph_arr[i][j]);
}
}
printf("\n-----------------------\n\n");
vector<vector<int>> graph_vec {
{0, 3, 0, 7, 8},
{3, 0, 1, 4, 0},
{0, 1, 0, 2, 0},
{7, 4, 2, 0, 3},
{8, 0, 0, 3, 0}
};
// iterate over the vertices
for(int i = 0; i < total_nodes; ++i){
for(int j = i+1; j < total_nodes; ++j){
if(graph_vec[i][j])
printf("There is an edge from %d to %d with cost: %d\n", i, j, graph_vec[i][j]);
}
}
return 0;
}
Libraries
-
nlohmann/json: A Popular, header-only C++ library for working with JSON. It provides an intuitive, STL-like API for parsing, serializing, and manipulating JSON data.
-
p-ranav/argparse: A lightweight, header-only C++ library for command-line argument parsing with a Python argparse-like API.
-
google/benchmark: A microbenchmarking library for measuring the performance of C++ code, designed for benchmarking functions and code snippets.
-
google/googletest: A widely used C++ testing framework that provides unit testing capabilities with assertions, fixtures, and test runners.
-
catchorg/Catch2: A modern, header-only C++ testing framework that supports simple test case definitions and expressive assertions.
-
fmtlib/fmt: A fast and safe formatting library for C++, providing an alternative to
printfandstd::ostream. -
gabime/spdlog: A fast, header-only C++ logging library with support for console and file output, formatting, and multithreading.
Reference materials
Documentation
-
https://cplusplus.com/
-
https://en.cppreference.com/w/
Github repositories
-
https://github.com/federico-busato/Modern-CPP-Programming
-
https://github.com/cpp-best-practices/cppbestpractices
Books
- The Art of Writing Efficient Programs: An advanced programmer’s guide to efficient hardware utilization and compiler optimizations using C++ examples (Fedor G. Pikus, 2021)
- C++ High Performance, Second Edition: Master the art of optimizing the functioning of your C++ code (Björn Andrist, Viktor Sehr, 2020)
- C++ Concurrency in Action: Practical Multithreading 1st Edition (Anthony Williams, 2012)
Youtube channels
-
https://www.youtube.com/@TheCherno
-
https://www.youtube.com/@cppweekly
-
https://www.youtube.com/@CppNow
Constraint programming
Solvers
Benders
BendersLib
BendersLib is a Python library that supports a range of Benders decomposition variants, including Classical Benders Decomposition, Combinatorial Benders Decomposition, L-shaped Method, Integer L-shaped Method, Generalized Benders Decomposition, and Logic-based Benders Decomposition.
While BendersLib provides built-in implementations of these methods, it is designed to be extensible. Users can implement custom Benders decomposition methods by customizing subproblem solvers and cut generators, and defining callback functions for enhancement strategies. BendersLib is solver agnostic and has built-in interfaces for popular Mathematical Programming and Constraint Programming solvers. Its support for rapid prototyping and high extensibility are designed to meet the needs of both researchers and practitioners in Operations Research and related fields.
TSP
TSPLIB95
The TSPLIB95 is the contains instances and optimal values for the symmetric TSP. This instances follow the TSPLIB File Format, which can be read and written using python library tsplib95. You can also find data for the HCP, ATSP, SOP and CVRP.
Concorde Solver
The Concorde solver is a state-of-the-art algorithm for efficiently solving the symmetric Travelling Salesman Problem (TSP) exactlty.
Python Wrapper
A convenient way to use this solver is through the PyConcorde library, a Python wrapper that interfaces with Concorde.
Installation
Installation instructions are well-described in the PyConcorde Documentation.
Loading a TSP problem
To load a TSP problem into the solver, provide a TSP instance file. In this example, an existing instance, a280.tsp, is passed to the solver.
from concorde.tsp import TSPSolver
INSTANCE_PATH = "./a280.tsp"
solver = TSPSolver.from_tspfile(INSTANCE_PATH)
If you only have the distance matrix, create a TSP instance file using the TSPLIB 95 library.
import tsplib95
distance_matrix = [
[0, 4, 6, 9, 7],
[4, 0, 3, 2, 2],
[6, 3, 0, 1, 8],
[9, 2, 1, 0, 4],
[7, 2, 8, 4, 0]
]
SIZE = len(distance_matrix)
problem = tsplib95.models.StandardProblem()
problem.name = "example"
problem.type = "TSP"
problem.dimension = SIZE
problem.edge_weight_type = "EXPLICIT"
problem.edge_weight_format = "FULL_MATRIX"
problem.edge_weights = distance_matrix
problem.save("example.tsp")
To generate instances with alternative edge weight types such as EUC_2D or GEO, you can create TSP files by referring to the following examples.
Solving
To execute the algorithm, call the .solve() method:
solution = solver.solve()
By default, the solver prints detailed information during execution. To disable verbosity, use the verbose parameter:
solution = solver.solve(verbose=False)
After execution, the solver returns an object containing, among others, the runtime and the computed tour, as well as flags indicating if the solve was successful and if the time bound was reached.
def print_solution(solution):
print(f"Success: {solution.success}")
print(f"Hit timebound: {solution.hit_timebound}")
print(f"Optimal value: {solution.optimal_value} ")
print(f"Tour: {solution.tour}")
Packing
Solvers
Machine Learning Under a Modern Optimization Lens
Summary
- Learning to make decisions directly from data
- Optimal Policy Trees
- Prescriptive Neural Networks
- ROAD
- Multimodal data
- TabText
- How to deal with missing data
- Data Imputation
- Matrix Completion
- Tensor Completion
Learning to make decisions directly from data
Description: This is useful when you want to make decisions based on historical data (observations).
Take a set of features per observation \(\mathbf{x}\), a set of mutually-exclusive policy options, and, for each observation, a real-valued outcome resulting from applying a given treatment to this observation. Our end goal is to learn the treatment assignment that optimizes the outcome for a new observation \(\mathbf{x}\). This is challenging to learn because in observational data, we only know the outcome for the prescription \(t_i\) that patient \(i\) actually received. We do not know what would have happened (counterfactuals) to patient \(i\) under the alternative treatments.
To overcome this challenge, we apply causal inference techniques, developed to learn the true causal dependence between the treatment application and the outcome. We highlight three approaches:
- Direct Method: Train a different model for each treatment. However, this method is susceptible to treatment assignment bias (e.g., a stronger treatment may be prescribed more often to sicker patients, who die with higher probability because they are sicker, not because the treatment is worse; and the model for the lighter treatment may estimate a better survival outcome for the sicker out-of-sample patient because its training data contained more healthier patients than sicker patients).
- Inverse Propensity Weighting: This method tries to fix the treatment assignment bias by reweighing the population. For an observation (e.g., patient) with features \(\mathbf{x}\), the propensity score measures how likely this observation was to receive the treatment observed in the data, as opposed to any other treatment. We can then reweigh the outcomes in the observed data to make it balanced. However, this method usually has high variance, because it is very sensitive to minor changes in the propensity score estimates.
- Doubly Robust: Combines both in a joint reward expression.
For any of these approaches, we can now estimate the outcomes for the alternative treatments and train a model that prescribes the best treatment given the observed features (with trees or neural networks).
References: Lecture slides (Lecture 11, Recitation 6); Bertsimas and Dunn book (Chapters 13 and 14); paper on “Optimal Prescriptive Trees” by Bertsimas, Dunn, and Mundru.
ROAD
Description: Combining some of the definitions above, ROAD is a framework for computing counterfactuals in prescriptive problems that involve a binary decision (treat / do not treat) in which one option is known to be generally beneficial, and where we learn from observational (non-randomized) data. Its purpose is to correct the confounding that arises because the decision in the data was not assigned at random, addressing both the observed confounding (differences in recorded features between the two groups) and the unobserved confounding (hidden differences the recorded features do not capture) before prescribing a policy. The medical setting (using observational data instead of clinical trials) is the motivating application, but the framework is general.
The pipeline has three steps. First, prognostic matching corrects the observed confounding: a baseline model trained only on the untreated observations estimates each observation’s outcome under no treatment, observations are grouped into risk buckets, and within each bucket, treated and untreated observations are matched by feature similarity through optimization (optimal assignment), discarding non-comparable observations so the resulting cohort emulates a randomized trial. Second, weight tuning corrects residual unobserved confounding: two outcome estimators (one per option) produce the counterfactuals, and if their average outcomes contradict the known benefit of the treatment, a weight on the good-outcome treated observations is increased until they no longer do. Third, an Optimal Policy Tree is trained on the corrected counterfactuals to prescribe the option for each observation and reveal interpretable subgroups. Sensitivity and specificity are used to validate the prescriptions and to tune the weight.
Consider ROAD when the decision is binary, one option is known to be beneficial in general, the outcome is binary, and only observational (non-randomized) data are available.
References: Lecture slides (Lecture 18, Recitation 11); paper on “ROAD to precision medicine” by Bertsimas, Koulouras, and Margonis.
Multimodal data: TabText
Description: For tabular data, machine learning models do not get contextual information from the column labels. For example, the model does not have the context that the column “Glucose” may have thresholds and correlations with other indicators already known in the literature. TabText converts tables into contextual language and applies pretrained large language models to generate enriched embeddings. Moreover, when we have unstructured data in addition to the tabular data (e.g., clinical notes), this allows us to convert everything into text and process the different kinds of information together.
Reference: paper on “TabText: Language-Based Representations of Tabular Health Data for Predictive Modelling” by Carballo et al.
How to deal with missing data
Data imputation
Description: Imputation methods in the literature may struggle to scale, lose accuracy when the percentage of missing data is large, or require strong assumptions about the underlying distribution of the missing data. This is an optimization-based alternative to data imputation.
We formulate the problem as a (non-convex, nonlinear) integer program, in which we minimize the sum of Euclidean distances from each imputed value to its \(K\) nearest neighbors. To solve this problem, due to its non-convexity and nonlinearity, we use first-order methods with random warm starts (Block Coordinate Descent and Coordinate Descent). The method can be extended to handle categorical variables and imputation models other than KNN (e.g., decision trees, SVM).
References: Lecture slides (Lecture 19); Bertsimas and Dunn book (Chapter 19).
Matrix Completion
Description: Here, we have a sparse matrix that records interactions between users (e.g., Netflix user) and products (e.g., movies). In principle, we do not have associated features to either the user or the product, but only some of their interactions.
We cannot fill the missing data without imposing any sort of structure on it. Thus, we impose the low-rank assumption, which carries two components:
- Sparsity: The interaction between user \(i\) and product \(j\) (e.g., a movie) is affected by a small number of underlying factors (e.g., genre, director, cast). In other words, this component assumes that the users only look at \(k\) factors when determining their (movie) preferences, but at varying weights for each user. However, in general, the features are in a latent space that is not interpretable, as you will see later that we are only decomposing our original matrix into a product of a user matrix (which learns the preferences - weights - of the user over the product features) and a product matrix (which learns the values each product should assume on the best latent space of \(k\) features) to force it to be \(k\)-rank (i.e., the resulting matrix will have at most \(k\) linearly independent rows).
- Linearity: The effect of each of the factors is additive (i.e., we can write the interaction as a weighted sum of the \(k\) factors for each user-product pair).
Under these assumptions, we can fit a completed low-rank matrix \(\mathbf{X} = \mathbf{U} \mathbf{V}\), where \(\mathbf{U} \in \mathbb{R}^{n \times k}\) is the user matrix and \(\mathbf{V} \in \mathbb{R}^{k \times m}\) is the product matrix, while minimizing the squared loss of our imputed matrix with respect to the existing data. If interpretability is important in our case, we can set \(\mathbf{V} = \mathbf{S} \mathbf{B}\), where \(\mathbf{B}\) is a known feature matrix (e.g., genre, director, cast, Rotten Tomatoes rating, duration, awards, etc.), then each feature in \(\mathbf{V}\) will be a linear combination of our known features. Since a general linear combination of known features is still not very interpretable, we could pose an additional sparsity assumption that chooses at most \(k\) out of the \(p\) known features. This problem can be formulated as a binary convex optimization problem, which can be solved by a cutting plane algorithm.
We can extend this method to tensors (arrays with 3 or more dimensions).
References: Lecture slides (Lectures 21 and 22, Recitation 13); Bertsimas and Dunn book (Chapters 24 and 25); paper on “Interpretable Matrix Completion: A Discrete Optimization Approach” by Bertsimas and Li; paper on “Tensor completion with noisy side information” by Bertsimas and Pawlowski.
Instance Space Analysis
Instance space analysis
According to Smith-Miles and Muñoz (2023),
“Instance Space Analysis (ISA) is a recently developed methodology to (a) support objective testing of algorithms and (b) assess the diversity of test instances. Representing test instances as feature vectors, the ISA methodology extends Rice’s 1976 Algorithm Selection Problem framework to enable visualization of the entire space of possible test instances, and gain insights into how algorithm performance is affected by instance properties. Rather than reporting algorithm performance on average across a chosen set of test problems, as is standard practice, the ISA methodology offers a more nuanced understanding of the unique strengths and weaknesses of algorithms across different regions of the instance space that may otherwise be hidden on average. It also facilitates objective assessment of any bias in the chosen test instances and provides guidance about the adequacy of benchmark test suites.”
An ISA is capable of generating a plot of instances based on the projection of various features into a 2D space. It may be necessary to analyze multiple graphs simultaneously in order to obtain meaningful conclusions when interpreting an ISA. For example, the following plot suggests that the analyzed algorithm performs worse for the instances projected in the lower right half of the 2D space, as the gap is higher in that section.
Concurrently, the following plot shows the value of the feature max-utilization in each instance. By comparing both graphs, we can infer a positive correlation tendency between the feature max-utilization and the instance difficulty. In other words, the higher the max-utilization, the harder the instance tends to be for the analyzed algorithm to solve.
Finally, some algorithms perform better in certain instance sets, and an ISA is also capable of providing this valuable insight. As already observed, the algorithm H performs well in instances with a low max-utilization. However, with the increase of max-utilization, F1_i becomes the best choice.
Making a legible projection of the instances into the 2D space is a challenging task since each instance is represented by a vector of features whose length is usually greater than 2. Fortunately, the Melbourne Algorithm Test Instance Library with Data Analytics (Matilda) takes care of everything.
Using Matilda
Matilda is an intuitive tool. Using the online version is recommended over downloading the code locally, as the former is much simpler.
For the input data, follow the instructions on their GitHub repository.
There is a complete tutorial available here. Start watching at time 33:32 if you want to use the online version.
References
Kate Smith-Miles and Mario Andrés Muñoz. 2023. Instance Space Analysis for Algorithm Testing: Methodology and Software Tools. ACM Comput. Surv. 55, 12, Article 255 (December 2023), 31 pages. https://doi.org/10.1145/3572895
Significance tests
When to use it
A significance test relies on two hypotheses: the null hypothesis (H0) and the alternative hypothesis (Ha). It can be applied, for instance, to formally confirm if the average gaps found by two algorithms are statistically different. In such a case, H0 states that there are no differences between the average gaps, and Ha states the logical opposite, i.e., that there are differences between the average gaps.
A few tips
Building the distribution of the differences
Suppose the samples, namely the average gaps found by algorithms A and B, are a = [250, 500, …, 300], and b = [251, 480, …, 350], respectively. Then, the distribution of the differences is a - b = [-1, 20, …, -50].
Normality test
Depending on the type of test one wishes to perform, a normality test might be required. That is the case for parametric tests like the t-test. For nonparametric tests, such as the Wilcoxon signed-rank test, no assumptions are made on the samples, and the normality test is not necessary. The following diagram shows the type of test one must use based on a few characteristics of the data.
Although not strictly necessary, one can apply a normality test on a - b to confirm that it is not normally distributed and justify the choice of employing a nonparametric test.
Wilcoxon signed-rank test
The Wilcoxon signed-rank test can either reject the null hypothesis in favor of the alternative hypothesis, or fail to reject H0. The latter does not mean that the null hypothesis is accepted.
Example of an article with significance tests
Generating guitar solos by integer programming
Oxford math classes
Oxford Mathematics offers a collection of math classes on YouTube. You can explore the entire playlist here.
Calculus
Probability
Graph Theory
Set Theory
Linear Algebra
Differential Equations
Networks
Algorithms
The use of algorithms for problem solving is almost mandatory in the field of optimization. Algorithms describe the sequence of step one must take to solve a problem, and as such, the way they are presented in scientific writing can highly impact understanding. Fortunately, LaTeX provides routines for neatly presenting both pseudocode and actual code. For instance, many packages allow writing pseudocode through the algorithm environment. For snippets of code in real programming languages, one may resort to minted or verbatim and listings.
Pseudocode
Package algorithm2e is frequently used for pseudocode. It is straightforward to use for programmers, as it resembles real code. It is also highly customizable and flexible. In the example below, the flags vlined and linesnumbered were used to add vertical lines and line numbering. As with equations, the label command can be used to assign labels to each line, so they can be referenced later in the text. It is also possible to use the tcc and tcp commands to add comments to the pseudocode.
\usepackage{mathtools}
\usepackage[ruled, vlined, linesnumbered, english, onelanguage]{algorithm2e}
...
\begin{algorithm}[ht]
\DontPrintSemicolon
\KwData{An array of numbers $A$}
\KwResult{A sorted array $A'$}
\Begin{
$A' \gets A$ \tcp{Make a copy of A}
\For{$j = 1,\dots,n$}{ \label{line:bubblefor1}
\For{$i=0,\dots,n-1$}
{ \label{line:bubblefor2}
\If{$A'[i] > A'[i+1]$}{ \label{line:bubbleif}
\tcc{Swapping A'[i] and A'[i + 1] through temporary variable}
$\text{temp} \gets A'[i]$ \label{line:swap1} \;
$A'[i] \gets A'[i+1]$ \;
$A'[i+1] \gets \text{temp} $ \label{line:swap2} \;
}
}
}
\Return{$A'$}
}
\caption{\textsc{Bubble Sort}\label{alg:bubblesort}}
\end{algorithm}
Algorithm \ref{alg:bubblesort} describes an implementaiton of Bubble Sort.
Lines \eqref{line:bubblefor1} and \eqref{line:bubblefor2} iterate through all pairs of elements in $A'$.
Line \eqref{line:bubbleif} checks if $A'[i]$ is greater than $A'[i+1]$, in which case these elements are swapped in lines \eqref{line:swap1}--\eqref{line:swap2}.
In case multiple procedures or functions are used and defined in the same pseudocode, use the \SetFwFunction and \SetKwProg commands. The former creates a macro for a function that may be called multiple times through the code. The latter is used if one wishes to create a block of code for each procedure. Both commands were used in the following snippet.
\begin{algorithm}[ht]
\DontPrintSemicolon
\KwData{A graph $G$, weight function $w$ and source $s$}
\KwResult{Predecessors $v.\pi$ for each $v \in G.V$ }
\SetKwFunction{FDijkstra}{\textsc{Dijkstra}}
\SetKwFunction{FExtract}{\textsc{Extract-Min}}
\SetKwFunction{FRelax}{\textsc{Relax}}
\SetKwFunction{FInit}{\textsc{Initialize-Single-Source}}
\SetKwProg{Proc}{Procedure}{ is}{end}
\Proc{\FDijkstra{$G, w, s$}}{
\FInit{$G,s$} \;
$S \gets \emptyset $ \;
$Q \gets G.V $ \;
\While{$Q \neq \emptyset$}{
$u \gets \FExtract$ \;
$S \gets S \cup \{u\}$ \;
\For{each vertex $v \in G.Adj[u]$}{
\FRelax{$u,v,w$}
}
}
}
\Proc{\FRelax{$u,v,w$}}{
\If{$v.d > u.d + w(u,v)$}{
$v.d \gets u.d + w(u,v)$ \;
$v.\pi \gets u$
}
}
\caption{\textsc{Dijkstra}\label{alg:dijkstra}}
\end{algorithm}
Real code
When it comes to showing real code within the text, the listings package is highly recommended, as it works quite well with most programming languages. One may also specify settings such as font size, background colors and framing as they wish. These settings can then be grouped into a “style” so they can be reused throughout the text, as shown below with the cplusplusListStyle.
\usepackage{listings}
\usepackage[scaled=0.9]{DejaVuSansMono}
\lstdefinestyle{cplusplusListStyle}{
belowcaptionskip=1\baselineskip,
breaklines=true,
xleftmargin=\parindent,
language=C++,
frame=tb,
showstringspaces=false,
tabsize=2,
%basicstyle=\footnotesize,
basicstyle=\footnotesize\ttfamily,
keywordstyle=\bfseries\color{green!40!black},
commentstyle=\itshape\color{purple!40!black},
identifierstyle=\color{blue},
stringstyle=\color{orange},
numbers=left,
stepnumber=1
}
% ...
\begin{lstlisting}[style=cplusplusListStyle]
// Your First C++ Program
#include <iostream>
int main() {
std::cout << "Hello World!";
return 0;
}
\end{lstlisting}
For more minimalist (no syntax highlighting) and simple snippets of code, try the verbatim environment. For an alternative to listings, try minted, which works pretty similarly. Unlike listings, however, the minted package contains ready-made syntax highlighting for most famous programming languages.
Equations
Being able to write mathematical expressions with plain text is one of LateX’s greatest features, and makes it well-suited for scientific writing. For instance, adding
$S = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} \alpha^k x_k + \frac{\log{i}}{i} \right) $
to a plain LaTeX file yields the expression $$S = \sum_{i=1}^{m} \left( \sum_{j=1}^{n} \alpha^k x_k + \frac{\log{i}}{i} \right). $$ Frequently used mathematical objects (e.g., matrices, vectors, sets, piecewise functions) can be easily written likewise.
For an overall introduction to latex math, refer to Overleaf guides.
Mathematical formulations
Mathematical formulations are commonly used to solve optimization problems. As such, one is often faced with the task to cleanly present them in scientific reports. Many times, a mathematical formulation can be seen as a collection of equations, inequations and expressions that are deeply related. Therefore, care must be taken to correctly organize and align such expressions, so they are presented in an easy to follow fashion.
The following example shows how one may write a formulation for the Traveling Salesman Problem in LaTeX. A label can be assigned to each equation with the \label{} command. Labeled equations can be referenced later in the text by using the \eqref{} command. By default, equations are automatically numbered. Alternatively, the \tag{} command can be used to assign a custom name to an equation instead of a number. All references to an equation will work as a hyperlink if the package hyperref is imported.
\begin{align}
\min & \sum_{i \in V, j > i} c_{ij} x_{ij} \tag{TSP}\label{eq:probTSP} \\
\text{s.t. } & \sum_{j>i} x_{ij} + \sum_{j<i} x_{ji} = 2, i \in V, \label{eq:degreeConstraintsTSP} \\
& \sum_{i \in S}\sum_{j \notin S} x_{ij} \geq 1, S \subset V, S \neq \emptyset, \label{eq:subtourConstraintsTSP} \\
& x_{ij} \in \{0,1\}, i \in V, j > i. \label{eq:integralityConstraintsTSP}
\end{align}
Problem \eqref{eq:probTSP} aims to minimize the total traveling cost.
Constraints \eqref{eq:degreeConstraintsTSP} force all vertices to have degree 2.
Constraints \eqref{eq:subtourConstraintsTSP} ensure connectivity.
Finally, constraints \eqref{eq:integralityConstraintsTSP} describe the domain of variables $x_{ij}$
Much of how formulations are actually structured is subject to one’s liking. In the previous example, the & operator was used to align equations to the left. The following snippet shows an alternative way to present the same formulation, in such a way that expressions are more evenly distributed, and the objective function is centered.
\begin{align}
\text{min} \sum_{i \in V, j > i} c_{ij} x_{ij} \tag{TSP}\label{eq:probTSP}
\end{align}
\begin{align}
\text{s.t. } \sum_{j>i} x_{ij} + \sum_{j<i} x_{ji} = 2 & & i \in V \label{eq:degreeConstraintsTSP} \\
\sum_{i \in S}\sum_{j \notin S} x_{ij} \geq 1 & & S \subset V, S \neq \emptyset \label{eq:subtourConstraintsTSP} \\
x_{ij} \in \{0,1\} & & i \in V, j > i \label{eq:integralityConstraintsTSP}
\end{align}
Problem \eqref{eq:probTSP} aims to minimize the total traveling cost.
Constraints \eqref{eq:degreeConstraintsTSP} force all vertices to have degree 2.
Constraints \eqref{eq:subtourConstraintsTSP} ensure connectivity.
Finally, constraints \eqref{eq:integralityConstraintsTSP} describe the domain of variables $x_{ij}$
Further yet, one may opt to use specialized packages. One such package is optidef, which allows us to write the formulation for optimization problems as in the example below. However, mastering default commands such as align{} and equation{} is highly recommended, as they give us much more control.
\usepackage{optidef}
...
\begin{maxi}
{}{\sum_{i=1}^{m}\sum_{j=1}^{n}p_{ij}x_{ij}}
{}{}
\addConstraint{\sum_{j=1}^n w_{ij} x_{ij}} {\leq t_i}{\quad i=1,\dots,n}
\addConstraint{\sum_{i=1}^m x_{ij}} {= 1}{\quad j=1,\dots,m}
\addConstraint{x_{ij}} {\in \{0,1\}} {\quad i=1,\dots,m,j=1,\dots,n}
\end{maxi}
Tips
- If your equation is too big and doesn’t fit the line width, split it with
split{}. You can also trymultline{}. - If you are running out of pages, try to reduce equation font size by using smaller fonts (e.g.,
\scriptsize,\footnotesize), or by usingscalebox{}, as in this answer. - Parenthesis (
()) have fixed size. For automatic scaling, use\left(and\right). The same applies to brackets, braces, ceil, floor, absolute value, etc. - If there is a variable in your paper whose name you have not yet decided, consider using
\newcommandas a placeholder so you can decide it later. - This document contains several LaTeX snippets that pertain to mathematical programming.
Extract as images
The main purpose of the preview package is to extract environments as images. To use it, the following line must be added to the preamble of the document.
\usepackage[active, tightpage]{preview}
where options active and tightpage are specified to activate the package, and to produce separate dimensions for every page, respectively.
The macro \PreviewEnvironment sets which environments must produce preview images.
\PreviewEnvironment{tikzpicture}
\PreviewEnvironment{tabular}
The code snippet above, for instance, makes all tikzpicture and tabular environments in the document produce images.
Full example:
\documentclass{article}
\usepackage{tikz}
\usepackage[active, tightpage]{preview}
\PreviewEnvironment{tikzpicture}
\PreviewEnvironment{tabular}
\begin{document}
\begin{figure}
\begin{tikzpicture}
\draw[step=1cm,gray,very thin] (-1,-1) grid (4,4);
\draw[thick,->] (0,0) -- (3.5,0);
\draw[thick,->] (0,0) -- (0,3.5);
\foreach \x in {0,1,2,3}
\draw (\x cm,1pt) -- (\x cm,-1pt) node[anchor=north] {$\x$};
\foreach \y in {0,1,2,3}
\draw (1pt,\y cm) -- (-1pt,\y cm) node[anchor=east] {$\y$};
\end{tikzpicture}
\end{figure}
\begin{center}
\begin{tabular}{ |c|c|c| }
\hline
cell1 & cell2 & cell3 \\
cell4 & cell5 & cell6 \\
cell7 & cell8 & cell9 \\
\hline
\end{tabular}
\end{center}
\end{document}