pivot-utils.h#

Go to the source code of this file

some functions used in one or more solver, mainly related to Lemke’s algorithm

Defines

PIVOT_PATHSEARCH_SUCCESS#

Functions

int pivot_init_lemke(double *mat, unsigned int dim)#

find the first leaving variable for Lemke’s algorithm

Parameters:

mat – the matrix
dim – the dimension of the problem

Returns:

the index of the blocking variable

int pivot_init_pathsearch(unsigned dim, double *mat, unsigned *t_indx)#

find the first leaving variable for the pathsearch algorithm

Parameters:

dim – the dimension of the problem
mat – the matrix
t_indx – [out] the index of t in the basis (needed since block < 0 is possible and meaningful)

Returns:

the index of the blocking (leaving) variable

int pivot_selection_lemke(double *mat, unsigned dim, unsigned drive, unsigned aux_index)#

find the leaving variable for Lemke’s algorithm

Parameters:

mat – the matrix; we only use the columns of basic variable and the covering vector of the entering variable
dim – dimension of the problem
drive – the driving variable
aux_index – index of auxillary variable in the current basis

Returns:

the leaving (or blocking) variable

int pivot_selection_lemke2(unsigned n, double *col_drive, double *q_tilde, double *lexico_mat, unsigned aux_indx, double lexico_tol)#

find the leaving variable for Lemke’s algorithm

Parameters:

n – dimension of the problem pivots)
col_drive – column of the driving variable (contains all the possible pivots)
q_tilde – solution of the linear system
lexico_mat – matrix for the lexico ordering
aux_indx – index of auxillary variable in the current basis
lexico_tol – the tolerance on the lexicographic comparison

Returns:

the leaving (or blocking) variable

int pivot_selection_lemke3(unsigned n, double *col_drive, double *q_tilde, double *lexico_col, unsigned *basis, unsigned *candidate_indx, SN_lumod_dense_data *lumod_data, unsigned aux_indx, double lexico_tol)#

find the leaving variable for Lemke’s algorithm

Parameters:

n – dimension of the problem
col_drive – column of the driving variable (contains all the possible pivots)
q_tilde – solution of the linear system
lexico_col – column for the lexico ordering
basis – current basis
candidate_indx – array for storing the possible candidate indexes
lumod_data – data for the BLU update
aux_indx – index of auxillary variable in the current basis
lexico_tol – the tolerance on the lexicographic comparison

Returns:

the leaving (or blocking) variable

int pivot_selection_pathsearch(double *mat, unsigned dim, unsigned drive, unsigned t_indx)#

find the leaving variable in a path search procedure.

The code is almost the same as in pivot_selection_lemke, except that we also check if it is possible to set t = 1.

Parameters:

mat – the matrix (we only use the columns of basic variable and the covering vector of the entering variable
dim – dimension of the problem
drive – the driving or entering variable
t_indx – the index of the t variable in the basis

Returns:

the leaving (or blocking) variable

void init_M_lemke(double *mat, double *M, unsigned int dim, unsigned int size_x, double *q, double *d)#

Initialize the matrix for Lemke’s algorithm as [ q | Id | -d | -M ] with d_i = 1 if i < size_x if the argument d is NULL.

Otherwise take d from the arguments

Parameters:

mat – column-major matrix to fill
M – M matrix from the LCP formulation
dim – dimension of the problem
size_x – for the classical Lemke’s algorithm, this is set to dim. Its value is different when we solve an AVI using Cao and Ferris method
q – vector from the LCP formulation
d – covering vector for the auxiliary variable, possibly NULL

void do_pivot_driftless(double *mat, unsigned int dim, unsigned int dim2, unsigned int block, unsigned int drive)#

Do the pivot <block, drive>, driftless version.

Parameters:

mat – the matrix to update
dim – the number of rows
dim2 – the number of columns
block – the blocking or leaving variable
drive – the driving or entering variable

void do_pivot_driftless2(double *mat, unsigned int dim, unsigned int dim2, unsigned int block, unsigned int drive)#

Do the pivot <block, drive>, driftless version.

Parameters:

mat – the matrix to update
dim – the number of rows
dim2 – the number of columns
block – the blocking or leaving variable
drive – the driving or entering variable

void do_pivot(double *mat, unsigned int dim, unsigned int dim2, unsigned int block, unsigned int drive)#

Do the pivot <block, drive>, standart version.

Parameters:

mat – the matrix to update
dim – the number of rows
dim2 – the number of columns
block – the blocking or leaving variable
drive – the driving or entering variable

void do_pivot_lumod(SN_lumod_dense_data *lumod_data, NumericsMatrix *M, double *q_tilde, double *lexico_mat, double *col_drive, double *col_tilde, unsigned *basis, unsigned block, unsigned drive)#

Do the pivot <block, drive> with block-LU updates.

Parameters:

lumod_data – lumod data
M – the LCP matrix
q_tilde – the modified q vector: it is the current of the variables currently in the basis
lexico_mat – matrix for the lexicographic ordering
col_drive – column of the driving variable
col_tilde – Solution to H x = col
basis – current basis
block – the blocking or leaving variable
drive – the driving or entering variable

void lcp_pivot_diagnose_info(int info)#

print a diagnostic of the info value

Parameters:: info – the value given by the algorithm

int pivot_selection_bard(double *mat, unsigned int dim)#

int pivot_selection_least_index(double *mat, unsigned int dim)#

void init_M_bard (double *restrict mat, double *restrict M, unsigned int dim, double *restrict q)

void init_M_least_index (double *restrict mat, double *restrict M, unsigned int dim, double *restrict q)

int init_M_lemke_warm_start (int n, double *restrict u, double *restrict mat, double *restrict M, double *restrict q, int *restrict basis, double *restrict cov_vec)

const char *basis_to_name(unsigned nb, unsigned n)#

unsigned basis_to_number(unsigned nb, unsigned n)#

File numerics/src/LCP/pivot-utils.h

Contents

File numerics/src/LCP/pivot-utils.h#