Daniel Riness, Sunnye Kim
MATH 480A
Final Project: Linear Optimization
Background/Motivation: The purpose of this project for us was to create a program that would help future MATH 407 students to better understand Linear Optimization and Linear Programming. Both of us had taken MATH 407 some time ago during our academic journey at the University of Washington and we hope that future students will find our work helpful in their understanding of Linear Optimization.
The matrices we use are the initial simplex tableau and are always formed from LP's in standard form. We say that an LP is in standard form when it is a maximization problem with objective function (c^T)x (where the ^T is meant to indicate the transpose of the vector), the inequalities are of the form of Ax <= b, where A is a matrix, x is a vector, and b is a vector as well, and we have 0 <= x. This is also called the 'primal' LP. The condition for the primal simplex algorithm is that the origin is a feasible solution, which means that the components of b are entirely non-negative. To use the dual simplex method, we must have that the cost row is entirely non-positive. This is associated with the dual LP having feasible origin.
The initial simplex matrix is of the form (which is also called the block structured format of the simplex tableau):
[A I | b]
[c 0| 0]
where A is the matrix from the original LP (in other words, the constraint matrix), b is from the initial LP as well, and c is the objective function from the LP
For more information on LP's in standard form please refer to: http://www.math.washington.edu/~burke/crs/407/notes/section1.pdf
For more information on the simplex algorithm please refer to: http://www.math.washington.edu/~burke/crs/407/notes/section2.pdf
For more information on Duality please refer to: http://www.math.washington.edu/~burke/crs/407/notes/section4.pdf
All of the notes on Prof. Burke's website are what are used when he teaches the course and are very thourough and easy to understand.
####
Instructions for use: Note: Interact blocks are indicated by two lines of #### at the top. All function blocks start with def, and each function has a seperate block (as they can be used separately). The one exception is pivot() which requires most of the others to be used.
In the first interact block, specify the number of constraints + the cost row and set it to nr. Specify the number of variables + the number of constraints + the b column, and set it to nc. Run the block of code. Enter your initial primal simplex tableau.
In the 2nd block, specify which row or column (but not both!) you wish to pivot on.
Run all blocks of code with only functions defined in them (indicated by the first line starting with ## and a very brief description of the function).
Use pivot(). If want to be able to use get_plot(), set pivot() = p1, p2, etc for however many pivots are done.
To use get_plot(), make a tuple of the first object in each of p1, p2, etc and pass the initial simplex tableau as the first parameter, and the tuple of primal solutions as the second parameter.
####
More explanation of the algorithms:
Primal simplex method: The simplex method starts with a primal feasible tableau that has the origin as a feasible solution. From here, the user picks a column based on the coefficients of the cost row. The user may choose a column if the cost row coefficient is positive. From there, the algorithm looks at that column, forms the ratios of the b column, over the column chosen by the user, finds the minimum, keeps track of that row index, and pivots on that (row, column).
Dual simplex method: Very similar to the primal simplex method, but instead of being primal feasible, we require dual feasibility which is covered when the objective function (also called the cost row), is entirely nonpostive. The user then chooses a row. The rows that can be chosen are those where the values in the b column are negative, then the same thing occurs as the primal simplex method. Ratios are formed (except this time it's the objective row over the row chosen by the user). This (row, column) is then pivoted on.
Graphical display: We alway start at the origin (0,0) and move to some adjacent vertex of the constraint region (also called a convex polyhedron). As such, there are multiple ways to get to the optimal value. Be aware, there are situations where the simplex algorithm can stall. This can be handled by using the smallest subscript rule: when choosing a row or column, if you have multiple options with the same value to increase the objective, you choose the one closest to the top when choosing the row, or closest to the left when choosing the column. When the ratios are formed, if some of the ratios are the same, you again use the same idea, choose the one closest to the top, or closest to the left.
All situations that should arrise should be documented in the individual functions below. If more explanation is required, please refer to Prof. Burke's notes.
Note: There are a number of disclaimers throughout the code that explain a few things that are lacking, or very important to be aware of. They are contained in the docstrings of the pivot() and get_plot() functions. Please read them as they are critical to the use of this code and understanding what we have done.
General Disclaimer: These functions work under the premise that the matrix is of rational form (QQ). To change this, in the first interact block of code, change it to RR for reals, but note that ZZ will not work, as the algorithm will deal with noninteger values in the A matrix after pivoting. One must also change each of the function checks from 'sage.matrix.matrix_rational_dense.Matrix_rational_dense' to 'sage.matrix.matrix_generic_dense.Matrix_generic_dense'.
{{{id=8| #### #### #enter initial information of simplex tableau nr=5 #number of constraints plus cost row nc=7 #number of variables plus number of constraints plus b column @interact def matrixsetup(a=input_grid(nr, nc, label="Please enter the initial simplex tableau", default=0, to_value=matrix), ): global dummy dummy = matrix(QQ, a) print dummy /// }}} {{{id=70| #### #### @interact #Note, this assumes that the user treats the top left entry of the above matrix as (1,1) and not (0,0). In other #words, the indices #are 1 based, and not 0 def colrowsetup(b=input_box(label="row index to pivot"), c=input_box(label="column index to pivot on")): global rowindex global colindex rowindex = b colindex = c /// }}} {{{id=123| #Leave this alone, this is a copy of the matrix made with the interact block om = copy(dummy) /// }}} {{{id=156| #This is a test matrix that can be used to illustrate how to use pivot() and the get_plot() functions. The next 6 blocks (including #this one) provide a full illustration of how to use these functions. #This is the original LP: # max 3x + y # subject to -x + 2y <= 4 # 3x - y <= 3 # test = matrix(QQ, [[-1,2,1,0,4], [3,-1,0,1,3], [3,1,0,0,0]]) test2 = copy(test) test2 /// [-1 2 1 0 4] [ 3 -1 0 1 3] [ 3 1 0 0 0] }}}To indicate one of the disclaimers, in the above plot, the constraint region is the region between 0<=x, 0<=y, -x+2y<=4, and 3x-y<=3. We couldn't figure out how to shade everything accordingly. In the end, the constraint region is not as important (but it still is important nonetheless to know and understand what the constraint region is), as the simplex algorithm moves between adjacent vertices of the convex polyhedron.
To illustrate, we start at (0,0), after the first pivot we move to (1,0), and with the 2nd pivot we move to (2,3), where we find that we have obtained the optimal value of 9.
{{{id=80| #Here we're using the primal simplex algorithm, and pivoting on the first column. p1 =pivot(test2, None, 1) /// [ 0 5/3 1 1/3 5] [ 1 -1/3 0 1/3 1] [ 0 2 0 -1 -3] Current objective value: 3 Current solution: [1, 0] Current dual solution: [0, 1] Optimal? False }}} {{{id=116| #Again using the primal simplex algorithm, and pivoting on the 2nd column. p2 =pivot(test2, None, 2) /// [ 0 1 3/5 1/5 3] [ 1 0 1/5 2/5 2] [ 0 0 -6/5 -7/5 -9] Current objective value: 9 Current solution: [2, 3] Current dual solution: [6/5, 7/5] Optimal? True }}} {{{id=117| t = (p1[0], p2[0]) /// }}} {{{id=119| get_plot(test, t) ///
}}}
To indicate one of the disclaimers, in the above plot, the constraint region is the region between 0<=x, 0<=y, -x+2y<=4, and 3x-y<=3.
{{{id=9| ##pivots a given matrix by either the dual or primal simplex method depending on whether a row or column index is provided def pivot(mat, ri = None, ci = None): r""" This functions pivots on the given row or column of the simplex tableau, obtains the primal and dual solutions, the current objective value, and checks optimality. INPUT: - ``mat`` - A simplex tableau matrix. - ``ri`` - Row index. - ``ci`` - Column index. OUTPUT: tuple -- Returns a tuple of the primal solution, dual solution, and current objective value. EXAMPLES: This example shows the pivoting process. :: mat = [ 2 1 -1 1 0 0 -1] [-1 2 0 0 1 0 -1] [ 1 -2 1 0 0 1 5] [-1 -2 -3 0 0 0 0] rowindex = 2 colindex = None sage: pivot(m1, rowindex, colindex) [ 0 5 -1 1 2 0 -3] [ 1 -2 0 0 -1 0 1] [ 0 0 1 0 1 1 4] [ 0 -4 -3 0 -1 0 1] Current objective value: -1 Current solution: [1, 0, 0] Current dual solution: [0, 1, 0] Optimal? False This is another example that shows when the pivot makes the tableau optimal. :: mat = [ 0 5 -1 1 2 0 -3] [ 1 -2 0 0 -1 0 1] [ 0 0 1 0 1 1 4] [ 0 -4 -3 0 -1 0 1] rowindex = 1 colindex = None sage: pivot(mat, rowindex, colindex) [ 0 -5 1 -1 -2 0 3] [ 1 -2 0 0 -1 0 1] [ 0 5 0 1 3 1 1] [ 0 -19 0 -3 -7 0 10] Current objective value: -10 Current solution: [1, 0, 3] Current dual solution: [3, 7, 0] Optimal? True This example shows what happens when something that is not a rational matrix is passed as a parameter. :: sage: pivot('1', 1, None) Traceback (click to the left of this block for traceback) ... TypeError: Please pass a rational matrix as the parameter This example shows what happens when neither a column or row are specified. :: mat = [ 2 1 -1 1 0 0 -1] [-1 2 0 0 1 0 -1] [ 1 -2 1 0 0 1 5] [-1 -2 -3 0 0 0 0] sage: pivot(mat) Traceback (click to the left of this block for traceback) ... ValueError: Please only specify a single row or column This example shows what happens when both the row and column are specified. :: mat = [ 2 1 -1 1 0 0 -1] [-1 2 0 0 1 0 -1] [ 1 -2 1 0 0 1 5] [-1 -2 -3 0 0 0 0] sage: pivot(mat, 1, 1) Traceback (click to the left of this block for traceback) ... ValueError: Please only specify a single row or column This example shows what happens when the primal LP is unbounded. :: mat = [ 5 -4 3 1 0 0 4] [ 0 -1 2 0 1 0 7] [ 7 0 1 0 0 1 5] [ 4 8 6 0 0 0 0] rowindex = 2 colindex = None sage: pivot(mat, rowindex, colindex) The primal is unbounded, thus the dual is infeasible, and the primal optimal value is +Infinity This example shows what happens when the dual LP is unbounded. :: mat = [ 5 -4 3 1 0 0 -1] [ 0 1 5 0 1 0 -2] [ 7 0 1 0 0 1 5] [-2 -4 -6 0 0 0 0] rowindex = 2 colindex = None sage: pivot(mat, rowindex, colindex) The dual is unbounded, thus the primal is infeasible, and the dual optimal value is -Infinity This is an example that shows what happens when the tableau is already optimal. :: mat = [ 1 2 3 1 0 0 5] [ 4 5 6 0 0 0 7] [ 7 8 9 0 0 1 9] [-1 -5 -9 0 0 0 0] rowindex = 1 colindex = None sage: pivot(mat, rowindex, colindex) The simplex tableau is already optimal DISCLAIMER: This function DOES change the matrix that is passed to it. If you are going to use the original matrix again, make a copy of it and pass the copy to the function. NOTES: This algorithm uses the append() and index() functions for lists, and add_multiple_of_row(), rescale_row() for matrices. It also uses the functions dualfeas() primalfeas(), dualoptsol(), optsol(), and optcheck() from below. AUTHORS: - Daniel Riness (2011-5-24) - Sunnye Kim (2011-5-24) """ if ((ri != None) & (ci != None)) | ((ri == None) & (ci == None)): raise ValueError, "Please only specify a single row or column" elif type(mat) != sage.matrix.matrix_rational_dense.Matrix_rational_dense: raise TypeError, "Please pass a rational matrix as the parameter" elif optcheck(mat): print "The simplex tableau is already optimal" return else: ratios = [] countinfin = 0 if ri != None: if ri == 0: raise ValueError, "Please list the first row as 1, and not 0" else: if dualfeas(mat): for i in [0..mat.ncols()-2]: if mat[ri-1, i] >= 0: ratios.append(Infinity) countinfin += 1 else: ratios.append(mat[mat.nrows()-1, i]/mat[ri-1,i]) if countinfin == len([0..mat.ncols()-2]): print "The dual is unbounded, thus the primal is infeasible, and the dual optimal value is %s"%(-Infinity) return else: colindex = ratios.index(min(ratios)) mat.rescale_row(ri-1, 1/mat[ri-1,colindex]) for j in [0..mat.nrows()-1]: if j != (ri-1): mat.add_multiple_of_row(j, ri-1, -mat[j, colindex]) else: print "Not dual feasible, cannot use the dual simplex method" return if ci != None: if ci == 0: raise ValueError, "Please list the first column as 1, and not 0" else: if primalfeas(mat): for i in [0..mat.nrows()-2]: if mat[i, ci-1] <= 0: ratios.append(Infinity) countinfin += 1 else: ratios.append(mat[i, mat.ncols()-1]/mat[i, ci-1]) if countinfin == len([0..mat.nrows()-2]): print "The primal is unbounded, thus the dual is infeasible, and the primal optimal value is %s"%(Infinity) return else: rowindex = ratios.index(min(ratios)) mat.rescale_row(rowindex, 1/mat[rowindex, ci-1]) for j in [0..mat.nrows()-1]: if j != (rowindex): mat.add_multiple_of_row(j, rowindex, -mat[j, ci-1]) else: print "Not primal feasible, cannot use the primal simplex method" return print mat print "Current objective value: " + str(-mat[mat.nrows()-1, mat.ncols()-1]) print "Current solution: " + str(optsol(mat)) print "Current dual solution: " + str(dualoptsol(mat)) print "Optimal? " + str(optcheck(mat)) return (optsol(mat), dualoptsol(mat), mat[mat.nrows()-1, mat.ncols()-1]) /// }}} {{{id=28| ##checks for optimality of the row and column def optcheck(m1): r""" This functions returns whether or not m1 is optimal. INPUT: - ``m1`` - A simplex tableau matrix. OUTPUT: boolean -- Returns True if the simplex tableau is optimal, False otherwise. EXAMPLES: This example shows when the tableau is not optimal. :: m1 = [ 1 2 3 1 0 0 4] [ 5 6 7 0 1 0 8] [ 9 10 11 0 0 1 12] [ 3 6 9 0 0 0 0] sage: optcheck(m1) False This is another example that shows when the tableau is optimal. :: m1= [ 0 -5 1 -1 -2 0 3] [ 1 -2 0 0 -1 0 1] [ 0 5 0 1 3 1 1] [ 0 -19 0 -3 -7 0 10] sage: optcheck(m1) True This example shows what happens when something that is not a rational matrix is passed as a parameter. :: optsol('1') Traceback (click to the left of this block for traceback) ... TypeError: Please pass a rational matrix as the parameter AUTHORS: - Daniel Riness (2011-5-24) - Sunnye Kim (2011-5-24) """ if type(m1) == sage.matrix.matrix_rational_dense.Matrix_rational_dense: colcheck=True rowcheck=True for i in [0..m1.nrows()-2]: if m1[i, m1.ncols()-1] < 0: colcheck=False for j in [0..m1.ncols()-2]: if m1[m1.nrows()-1, j] > 0: rowcheck=False if colcheck & rowcheck: return True return False else: raise TypeError, "Please pass a rational matrix as the parameter" /// }}} {{{id=37| ##obtains optimal solution def optsol(m1): r""" This functions returns the current primal solution. INPUT: - ``m1`` - A simplex tableau matrix. OUTPUT: list -- A list of the values for the primal solution. EXAMPLES: This example shows what current primal solution is. :: m1 = [ 1 2 3 1 0 0 4] [ 5 6 7 0 1 0 8] [ 9 10 11 0 0 1 12] [ 3 6 9 0 0 0 0] sage: optsol(m1) [0,0,0] This is another example that shows what current primal solution is. :: m1= [ 0 -5 1 -1 -2 0 3] [ 1 -2 0 0 -1 0 1] [ 0 5 0 1 3 1 1] [ 0 -19 0 -3 -7 0 10] sage: optsol(m1) [1,0,3] This example shows what happens when something that is not a rational matrix is passed as a parameter. :: optsol('1') Traceback (click to the left of this block for traceback) ... TypeError: Please pass a rational matrix as the parameter AUTHORS: - Daniel Riness (2011-5-24) - Sunnye Kim (2011-5-24) """ if type(m1) == sage.matrix.matrix_rational_dense.Matrix_rational_dense: sol = [] index = 0 for i in [0..m1.ncols()-m1.nrows()-1]: count0 = 0 count1 = 0 for j in [0..m1.nrows()-1]: if m1[j,i] == 0: count0 += 1 elif m1[j,i] == 1: index = j count1 += 1 if (count1 == 1) & (count0 == m1.nrows()-1): sol.append(m1[index, m1.ncols()-1]) else: sol.append(0) return sol else: raise TypeError, "Please pass a rational matrix as the parameter" /// }}} {{{id=43| ##obtains dual solution def dualoptsol(m1): r""" This functions returns the current dual solution. INPUT: - ``m1`` - A simplex tableau matrix. OUTPUT: list -- A list of the values for the dual solution. EXAMPLES: This example shows what the current dual solution is. :: m1 = [ 1 2 3 1 0 0 4] [ 5 6 7 0 1 0 8] [ 9 10 11 0 0 1 12] [ 3 6 9 0 0 0 0] sage: dualoptsol(m1) [0,0,0] This is another example that shows what current dual solution is. :: m1= [ 0 -5 1 -1 -2 0 3] [ 1 -2 0 0 -1 0 1] [ 0 5 0 1 3 1 1] [ 0 -19 0 -3 -7 0 10] sage: dualoptsol(m1) [3,7,0] This example shows what happens when something that is not a rational matrix is passed as a parameter. :: dualoptsol('1') Traceback (click to the left of this block for traceback) ... TypeError: Please pass a rational matrix as the parameter AUTHORS: - Daniel Riness (2011-5-24) - Sunnye Kim (2011-5-24) """ if type(m1) == sage.matrix.matrix_rational_dense.Matrix_rational_dense: sol = [] for j in [m1.ncols()-m1.nrows()..m1.ncols()-2]: sol.append(-1*m1[m1.nrows()-1, j]) return sol else: raise TypeError, "Please pass a rational matrix as the parameter" /// }}} {{{id=65| ##checks primal feasability def primalfeas(m1): r""" This functions returns whether the matrix m1 is primal feasible. Primal feasible means that the b column of the simplex tableau entirely nonnegative. INPUT: - ``m1`` - A simplex tableau matrix. OUTPUT: boolean -- returns True if the matrix is primal feasible, returns False otherwise. EXAMPLES: This example shows what happens with the simplex tableau is primal feasible. :: m1 = [ 1 2 3 1 0 0 4] [ 5 6 7 0 1 0 8] [ 9 10 11 0 0 1 12] [ 3 6 9 0 0 0 0] sage: primalfeas(m1) True This example shows what happens with a simplex tableau that is not primal feasible. :: m1= [ 1 2 3 1 0 0 -4] [ 5 6 7 0 1 0 -7] [ 9 10 11 0 0 1 12] [-3 -6 -9 0 0 0 0] sage: primalfeas(m1) False This example shows what happens when something that is not a rational matrix is passed as a parameter. :: primalfeas('1') Traceback (click to the left of this block for traceback) ... TypeError: Please pass a rational matrix as the parameter AUTHORS: - Daniel Riness (2011-5-24) - Sunnye Kim (2011-5-24) """ if type(m1) == sage.matrix.matrix_rational_dense.Matrix_rational_dense: for i in [0..m1.nrows()-2]: if m1[i, m1.ncols()-1] < 0: return False return True else: raise TypeError, "Please pass a rational matrix as the parameter" /// }}} {{{id=78| ##checks dual feasability def dualfeas(m1): r""" This functions returns whether the matrix m1 is dual feasible. Dual feasible means that the objective function of the LP is entirely nonpositive. INPUT: - ``m1`` - A simplex tableau matrix. OUTPUT: boolean -- returns True if the matrix is dual feasible, returns False otherwise. EXAMPLES: This example shows what happens with the simplex tableau is not dual feasible. :: m1 = [ 1 2 3 1 0 0 4] [ 5 6 7 0 1 0 8] [ 9 10 11 0 0 1 12] [ 3 6 9 0 0 0 0] sage: dualfeas(m1) False This example shows what happens with a simplex tableau that is dual feasible. :: m1= [ 1 2 3 1 0 0 -4] [ 5 6 7 0 1 0 -7] [ 9 10 11 0 0 1 12] [-3 -6 -9 0 0 0 0] sage: dualfeas(m1) True This example shows what happens when something that is not a rational matrix is passed as a parameter. :: dualfeas('1') Traceback (click to the left of this block for traceback) ... TypeError: Please pass a rational matrix as the parameter AUTHORS: - Daniel Riness (2011-5-24) - Sunnye Kim (2011-5-24) """ if type(m1) == sage.matrix.matrix_rational_dense.Matrix_rational_dense: for j in [0..m1.ncols()-2]: if m1[m1.nrows()-1, j] > 0: return False return True else: raise TypeError, "Please pass a rational matrix as the parameter" /// }}} {{{id=79| ##illustrates linear programming through graphical methods (2d only at the moment) def get_plot(m1, v): r""" This functions returns the graph of the constraint equations given by the user. It also plots the vertices that are found while using the pivot() function. This function only deals with 2 dimensions at the moment, but could easily be expanded to 3D but we we're unable to find the time to do so. This only works when the the columns after the first 2 form the identity matrix. To better explain, if m1 is the matrix stated at the top of the handout in the text section, then A has only 2 columns, and some number (call it a) of constraints, then the Identity matrix is an a by a matrix. INPUT: - ``m1`` - A simplex tableau matrix. - ``v`` - A list or tuples. OUTPUT: plot -- shows the plot of all the constraint equations with the list of tuples. NOTES: This algorithm uses the submatrix() and augment() functions for the matrix. Also, the function uses axes_range() and show() for the graphics. DISCLAIMER: The xmax and ymax could not be found exactly using the algorithms we used. Therefore, we added a buffer of +5 so that the user would be able to see more of the graphical solution. Please be aware that if the buffer is too small or too large (which will possibly result in part of the constraint region being cut off), please change it accordingly. DISCLAIMER 2: This plot does not actually show the proper constraint region of the LP. The constraint region is the region indicated by the intersection of all of the constraints. We could not find a good way to use fill and fillcolor for the plots, especially since when we plot, we sometimes use plot() and other times use lines(). AUTHORS: - Daniel Riness (2011-06-01) - Sunnye Kim (2011-06-01) """ A = m1.submatrix(0,0, m1.nrows()-1, 2) b = m1.submatrix(0,m1.ncols()-1, m1.nrows()-1) Ab = A.augment(b) xmax = -Infinity ymax = -Infinity for i in v: if i[0] > xmax: xmax = i[0] if i[1] > ymax: ymax = i[1] gmax = max(0, xmax, ymax) P = plot(0, (x, 0, xmax+5), thickness = 2) P += line([(0, 0), (0, ymax+5)], thickness = 2) if type(m1) == sage.matrix.matrix_rational_dense.Matrix_rational_dense: if m1.ncols()-m1.nrows() == 2: for i in [0..Ab.nrows()-1]: if (Ab[i,0] != 0) & (Ab[i,1] != 0): P += plot((Ab[i,0]*x - Ab[i,2])/(-Ab[i,1]), (x, 0, xmax+5), thickness = 2) if Ab[i, 0] == 0: #plots lines of the form y = a P += plot(Ab[i, 2], (x, 0, xmax+5), thickness = 2) if Ab[i, 1] == 0: #our solution to plotting lines of the form x = a P += line([(Ab[i,2],0), (Ab[i,2], gmax+5)], thickness = 2) else: raise ValueError, "Please pass a matrix that can be solved graphically" else: raise TypeError, "Please pass a rational matrix as the parameter" P += point((0,0), pointsize=50, color="red", zorder=5) for i in v: P += point(i, pointsize=50, color="red", zorder=5) P.axes_range(-1, xmax+5, -1, ymax+5) P.show(aspect_ratio=1) /// }}} {{{id=135| ###NOTE: This was an attempt to solve the bounds of the graph problem (showing the complete feasible region). It is not used in any ###of the above code, but we spent long enough trying to figure it out, and we thought it might be useful if someone else took this ###up. ##obtains all intersections of every pair of equations def vertices(m1): A = m1.submatrix(0,0, m1.nrows()-1, 2) b = m1.submatrix(0, m1.ncols()-1, m1.nrows()-1) test = A.augment(b) xs = [] ys = [] var('x,y') for i in [0..3]: for j in [i+1..3]: if i != j: eqn = [test[i,0]*x + test[i,1]*y == test[i,2], test[j,0]*x + test[j,1]*y == test[j,2]] s = solve(eqn, x, y, solution_dict= True) xs.append(s[0][x]) ys.append(s[0][y]) /// }}} {{{id=155| /// }}}