help-glpk
[Top][All Lists]
Advanced
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-glpk] glpk simplex routines profiling

From: Bertani, Phil \(MLIM\)
Subject: [Help-glpk] glpk simplex routines profiling
Date: Thu, 13 Apr 2006 00:41:52 +0400 
Hi all

I thought you might be interested to see the performance results from
 collect on unix for an lp problem with lots of columns and not too many
 rows.  The subroutines spx_update_gvec and spx_eval_row are the
 outliers,  but I imagine they should be.  spx_update_gvec is a
 "pricing" subroutine (trying to find a new basic variable) and
 spx_eval_row computes a row of the simplex table.  They are both in
 the glpspx1.c file.  CPLEX solves the same problem in about 3 seconds. 

Here is the output describing the problem:
lpx_read_cpxlp: reading problem data from `opt2'...
lpx_read_cpxlp: 70 rows, 9108 columns, 142195 non-zeros
lpx_read_cpxlp: 38942 lines were read
lpx_simplex: original LP has 70 rows, 9108 columns, 142195 non-zeros
lpx_simplex: presolved LP has 70 rows, 5963 columns, 93201 non-zeros
lpx_adv_basis: size of triangular part = 70
      0:   objval =  -9.910232806e #43;03   infeas =   1.000000000e #43;00 (0)
    200:   objval =  -2.374739256e #43;04   infeas =   7.461877512e-02 (0)
    277:   objval =  -2.783282886e #43;04   infeas =   0.000000000e #43;00 (0)
*   277:   objval =  -2.783282886e #43;04   infeas =   0.000000000e #43;00 (0)
*   400:   objval =  -2.187922331e #43;04   infeas =   0.000000000e #43;00 (0)
*   600:   objval =  -1.908056967e #43;04   infeas =   0.000000000e #43;00 (0)
*   800:   objval =  -1.861617462e #43;04   infeas =   0.000000000e #43;00 (0)
*   935:   objval =  -1.855059308e #43;04   infeas =   0.000000000e #43;00 (0)
OPTIMAL SOLUTION FOUND
Time used:   13.0 secs
Memory used: 15.5M (16232092 bytes)


Here is the time spent in each subroutine with the --nosteep option:
Excl.     Incl.      Name
User CPU  User CPU
  sec.      sec.
12.949    12.949     <Total>
 6.815     6.815     glp_spx_eval_row
 1.191     1.211     glp_spx_prim_chuzc
 1.051     1.051     glp_spx_update_cbar
 0.570     1.071     glp_compare_str
 0.360     0.360     memset
 0.270     0.270     glp_spx_eval_cbar
 0.210     0.320     read_char
 0.140     0.200     glp_lpx_set_mat_row
 0.140     0.140     memcpy
 0.130     0.360     add_char
 0.120     0.120     glp_lpx_order_matrix
 0.120     0.120     strchr
 0.100     0.100     getc
 0.100     0.851     scan_token
 0.090     0.090     memcmp
 0.070     0.070     analyze_row
 0.070     1.121     glp_avl_find_by_key
 0.070     0.160     glp_dmp_get_atom
 0.070     0.070     glp_spx_eval_xn_j
 0.060     0.130     glp_lpp_add_aij
 0.060     0.060     glp_lpx_get_mat_row
 0.060     0.060     glp_luf_f_solve
 0.060     2.111     parse_linear_form
 0.050     0.080     __inrange_double
 0.050     1.121     compare_names
 0.050     1.271     glp_lpx_find_col
 0.050     0.050     glp_spx_prim_chuzr
 0.050     0.050     process_col_sngton2
 0.040     0.040     eliminate
 0.040     0.050     eq_scal
 0.040     0.040     glp_dmp_free_atom
 0.040     0.050     glp_inv_update
 0.040     0.040     glp_lpx_get_col_type
 0.040     0.040     glp_luf_v_solve
 0.040     0.040     string_to_decimal
 0.030     0.030     glp_inv_h_solve
 0.030     0.180     glp_lib_str2dbl
 0.030     0.030     glp_lpx_get_mat_col
 0.020     0.020     __set_ieee_flags
 0.020     0.030     glp_clear_str
 0.020     0.110     glp_lpp_build_prob
 0.020     0.030     glp_spx_update_bbar
 0.020     0.040     process_fixed_col
 0.020     0.020     strlen
 0.020     0.150     strtod
 0.020     0.100     triang
 0.010     0.010     __digits_to_double
 0.010     0.010     _brk_unlocked
 0.010     0.010     _return_zero
 0.010     0.010     build_v_cols
 0.010     0.090     decimal_to_double
 0.010     0.010     fabs
 0.010     0.010     fgetc
 0.010     0.010     glp_avl_find_prev_node
 0.010     0.090     glp_inv_ftran
 0.010     0.010     glp_lpp_add_col
 0.010     0.010     glp_lpx_add_cols
 0.010     0.050     glp_lpx_get_col_bnds
 0.010     0.010     glp_lpx_get_col_stat
 0.010     0.010     glp_lpx_get_obj_coef
 0.010     0.010     glp_lpx_get_rii
 0.010     0.010     glp_luf_enlarge_row
 0.010     0.010     glp_spx_eval_pi
 0.010     0.060     glp_spx_eval_rho
 0.010     0.010     glp_spx_update_pi
 0.010     0.020     initialize
 0.010     0.010     jday
 0.010     0.080     mat
 0.010     0.010     process_col_sngton1
 0.010     0.010     recover_fixed_col

And here is the time spent in each subroutine for steepest edge pricing:
14.830    14.830     <Total>
 6.344     6.404     glp_spx_update_gvec
 3.512     3.512     glp_spx_eval_row
 0.570     0.570     glp_spx_update_cbar
 0.550     0.560     glp_spx_prim_chuzc
 0.410     0.881     glp_compare_str
 0.250     0.340     read_char
 0.240     0.240     memset
 0.230     0.230     memcpy
 0.170     0.941     scan_token
 0.150     0.150     glp_spx_eval_cbar
 0.140     0.400     add_char
 0.140     0.140     glp_lpx_order_matrix
 0.130     0.150     glp_lpx_set_mat_row
 0.120     1.051     glp_avl_find_by_key
 0.090     0.971     compare_names
 0.080     0.080     analyze_row
 0.080     0.090     getc
 0.080     0.080     glp_lpx_get_mat_row
 0.070     0.100     _doprnt
 0.070     0.070     glp_lpx_get_sjj
 0.070     0.070     memcmp
 0.070     0.070     strchr
 0.060     0.210     glp_lib_str2dbl
 0.060     0.060     glp_lpx_get_mat_col
 0.060     0.060     glp_luf_v_solve
 0.050     0.100     glp_dmp_get_atom
 0.050     0.070     glp_lpp_add_aij
 0.050     0.050     string_to_decimal
 0.040     0.040     glp_inv_update
 0.040     0.080     glp_lpp_build_prob
 0.040     0.120     glp_lpp_load_orig
 0.040     1.211     glp_lpx_find_col
 0.040     0.040     glp_lpx_get_col_type
 0.040     0.040     glp_luf_f_solve
 0.030     0.070     decimal_to_double
 0.030     0.030     glp_clear_str
 0.030     0.030     glp_lpx_get_row_dual
 0.030     2.121     parse_linear_form
 0.030     0.030     process_col_sngton1
 0.030     0.030     process_col_sngton2
 0.020     0.020     __get_ieee_flags
 0.020     0.040     __inrange_double
 0.020     0.050     eq_scal
 0.020     0.020     glp_lpp_enque_row
 0.020     0.200     glp_lpx_check_kkt
 0.020     0.020     glp_lpx_get_col_prim
 0.020     0.080     glp_set_str
 0.020     0.020     glp_spx_check_bbar
 0.020     0.050     process_fixed_col
 0.020     0.150     strtod
 0.010     0.010     <static>@0xbe4dc
 0.010     0.010     _QgetRD
 0.010     0.010     __four_digits_quick
 0.010     0.010     __quorem10000
 0.010     0.010     _brk_unlocked
 0.010     0.020     _morecore
 0.010     0.010     _read
 0.010     0.010     eliminate
 0.010     0.010     fgetc
 0.010     0.110     fprintf
 0.010     0.010     glp_avl_find_prev_node
 0.010     0.060     glp_avl_insert_by_key
 0.010     0.030     glp_create_str
 0.010     0.040     glp_delete_str
 0.010     0.010     glp_dmp_free_atom
 0.010     0.010     glp_inv_h_solve
 0.010     0.200     glp_lpp_presolve
 0.010     0.030     glp_lpx_get_col_info
 0.010     0.010     glp_lpx_get_obj_coef
 0.010     0.010     glp_lpx_get_rii
 0.010     0.040     glp_lpx_get_row_info
 0.010     0.010     glp_lpx_put_lp_basis
 0.010     0.010     glp_lpx_put_solution
 0.010     0.010     glp_lpx_set_col_bnds
 0.010     0.010     glp_lpx_set_col_stat
 0.010     0.010     glp_lpx_set_obj_coef
 0.010     0.050     glp_spx_change_basis
 0.010     0.030     mat
 0.010     0.090     mat
 0.010     0.150     parse_bounds
 0.010     0.010     recover_fixed_col

I thought you might be interested to see the performance results from collect on unix for an lp problem with lots of columns and not too many rows.  The subroutines spx_update_gvec and spx_eval_row are the outliers,  but I imagine they should be.  spx_update_gvec is a "pricing" subroutine (trying to find a new basic variable) and spx_eval_row computes a row of the simplex table.  They are both in the glpspx1.c file.  CPLEX solves the same problem in about 3 seconds.

Here is the output describing the problem:
lpx_read_cpxlp: reading problem data from `opt2'...
lpx_read_cpxlp: 70 rows, 9108 columns, 142195 non-zeros
lpx_read_cpxlp: 38942 lines were read
lpx_simplex: original LP has 70 rows, 9108 columns, 142195 non-zeros
lpx_simplex: presolved LP has 70 rows, 5963 columns, 93201 non-zeros
lpx_adv_basis: size of triangular part = 70
      0:   objval =  -9.910232806e+03   infeas =   1.000000000e+00 (0)
    200:   objval =  -2.374739256e+04   infeas =   7.461877512e-02 (0)
    277:   objval =  -2.783282886e+04   infeas =   0.000000000e+00 (0)
*   277:   objval =  -2.783282886e+04   infeas =   0.000000000e+00 (0)
*   400:   objval =  -2.187922331e+04   infeas =   0.000000000e+00 (0)
*   600:   objval =  -1.908056967e+04   infeas =   0.000000000e+00 (0)
*   800:   objval =  -1.861617462e+04   infeas =   0.000000000e+00 (0)
*   935:   objval =  -1.855059308e+04   infeas =   0.000000000e+00 (0)
OPTIMAL SOLUTION FOUND
Time used:   13.0 secs
Memory used: 15.5M (16232092 bytes)


Here is the time spent in each subroutine with the --nosteep option:
Excl.     Incl.      Name
User CPU  User CPU
  sec.      sec.
12.949    12.949     <Total>
 6.815     6.815     glp_spx_eval_row
 1.191     1.211     glp_spx_prim_chuzc
 1.051     1.051     glp_spx_update_cbar
 0.570     1.071     glp_compare_str
 0.360     0.360     memset
 0.270     0.270     glp_spx_eval_cbar
 0.210     0.320     read_char
 0.140     0.200     glp_lpx_set_mat_row
 0.140     0.140     memcpy
 0.130     0.360     add_char
 0.120     0.120     glp_lpx_order_matrix
 0.120     0.120     strchr
 0.100     0.100     getc
 0.100     0.851     scan_token
 0.090     0.090     memcmp
 0.070     0.070     analyze_row
 0.070     1.121     glp_avl_find_by_key
 0.070     0.160     glp_dmp_get_atom
 0.070     0.070     glp_spx_eval_xn_j
 0.060     0.130     glp_lpp_add_aij
 0.060     0.060     glp_lpx_get_mat_row
 0.060     0.060     glp_luf_f_solve
 0.060     2.111     parse_linear_form
 0.050     0.080     __inrange_double
 0.050     1.121     compare_names
 0.050     1.271     glp_lpx_find_col
 0.050     0.050     glp_spx_prim_chuzr
 0.050     0.050     process_col_sngton2
 0.040     0.040     eliminate
 0.040     0.050     eq_scal
 0.040     0.040     glp_dmp_free_atom
 0.040     0.050     glp_inv_update
 0.040     0.040     glp_lpx_get_col_type
 0.040     0.040     glp_luf_v_solve
 0.040     0.040     string_to_decimal
 0.030     0.030     glp_inv_h_solve
 0.030     0.180     glp_lib_str2dbl
 0.030     0.030     glp_lpx_get_mat_col
 0.020     0.020     __set_ieee_flags
 0.020     0.030     glp_clear_str
 0.020     0.110     glp_lpp_build_prob
 0.020     0.030     glp_spx_update_bbar
 0.020     0.040     process_fixed_col
 0.020     0.020     strlen
 0.020     0.150     strtod
 0.020     0.100     triang
 0.010     0.010     __digits_to_double
 0.010     0.010     _brk_unlocked
 0.010     0.010     _return_zero
 0.010     0.010     build_v_cols
 0.010     0.090     decimal_to_double
 0.010     0.010     fabs
 0.010     0.010     fgetc
 0.010     0.010     glp_avl_find_prev_node
 0.010     0.090     glp_inv_ftran
 0.010     0.010     glp_lpp_add_col
 0.010     0.010     glp_lpx_add_cols
 0.010     0.050     glp_lpx_get_col_bnds
 0.010     0.010     glp_lpx_get_col_stat
 0.010     0.010     glp_lpx_get_obj_coef
 0.010     0.010     glp_lpx_get_rii
 0.010     0.010     glp_luf_enlarge_row
 0.010     0.010     glp_spx_eval_pi
 0.010     0.060     glp_spx_eval_rho
 0.010     0.010     glp_spx_update_pi
 0.010     0.020     initialize
 0.010     0.010     jday
 0.010     0.080     mat
 0.010     0.010     process_col_sngton1
 0.010     0.010     recover_fixed_col

And here is the time spent in each subroutine for steepest edge pricing:
14.830    14.830     <Total>
 6.344     6.404     glp_spx_update_gvec
 3.512     3.512     glp_spx_eval_row
 0.570     0.570     glp_spx_update_cbar
 0.550     0.560     glp_spx_prim_chuzc
 0.410     0.881     glp_compare_str
 0.250     0.340     read_char
 0.240     0.240     memset
 0.230     0.230     memcpy
 0.170     0.941     scan_token
 0.150     0.150     glp_spx_eval_cbar
 0.140     0.400     add_char
 0.140     0.140     glp_lpx_order_matrix
 0.130     0.150     glp_lpx_set_mat_row
 0.120     1.051     glp_avl_find_by_key
 0.090     0.971     compare_names
 0.080     0.080     analyze_row
 0.080     0.090     getc
 0.080     0.080     glp_lpx_get_mat_row
 0.070     0.100     _doprnt
 0.070     0.070     glp_lpx_get_sjj
 0.070     0.070     memcmp
 0.070     0.070     strchr
 0.060     0.210     glp_lib_str2dbl
 0.060     0.060     glp_lpx_get_mat_col
 0.060     0.060     glp_luf_v_solve
 0.050     0.100     glp_dmp_get_atom
 0.050     0.070     glp_lpp_add_aij
 0.050     0.050     string_to_decimal
 0.040     0.040     glp_inv_update
 0.040     0.080     glp_lpp_build_prob
 0.040     0.120     glp_lpp_load_orig
 0.040     1.211     glp_lpx_find_col
 0.040     0.040     glp_lpx_get_col_type
 0.040     0.040     glp_luf_f_solve
 0.030     0.070     decimal_to_double
 0.030     0.030     glp_clear_str
 0.030     0.030     glp_lpx_get_row_dual
 0.030     2.121     parse_linear_form
 0.030     0.030     process_col_sngton1
 0.030     0.030     process_col_sngton2
 0.020     0.020     __get_ieee_flags
 0.020     0.040     __inrange_double
 0.020     0.050     eq_scal
 0.020     0.020     glp_lpp_enque_row
 0.020     0.200     glp_lpx_check_kkt
 0.020     0.020     glp_lpx_get_col_prim
 0.020     0.080     glp_set_str
 0.020     0.020     glp_spx_check_bbar
 0.020     0.050     process_fixed_col
 0.020     0.150     strtod
 0.010     0.010     <static>@0xbe4dc
 0.010     0.010     _QgetRD
 0.010     0.010     __four_digits_quick
 0.010     0.010     __quorem10000
 0.010     0.010     _brk_unlocked
 0.010     0.020     _morecore
 0.010     0.010     _read
 0.010     0.010     eliminate
 0.010     0.010     fgetc
 0.010     0.110     fprintf
 0.010     0.010     glp_avl_find_prev_node
 0.010     0.060     glp_avl_insert_by_key
 0.010     0.030     glp_create_str
 0.010     0.040     glp_delete_str
 0.010     0.010     glp_dmp_free_atom
 0.010     0.010     glp_inv_h_solve
 0.010     0.200     glp_lpp_presolve
 0.010     0.030     glp_lpx_get_col_info
 0.010     0.010     glp_lpx_get_obj_coef
 0.010     0.010     glp_lpx_get_rii
 0.010     0.040     glp_lpx_get_row_info
 0.010     0.010     glp_lpx_put_lp_basis
 0.010     0.010     glp_lpx_put_solution
 0.010     0.010     glp_lpx_set_col_bnds
 0.010     0.010     glp_lpx_set_col_stat
 0.010     0.010     glp_lpx_set_obj_coef
 0.010     0.050     glp_spx_change_basis
 0.010     0.030     mat
 0.010     0.090     mat
 0.010     0.150     parse_bounds
 0.010     0.010     recover_fixed_col

If you are not an intended recipient of this e-mail, please notify the sender, delete it and do not read, act upon, print, disclose, copy, retain or redistribute it. Click here for important additional terms relating to this e-mail.     http://www.ml.com/email_terms/
reply via email to
[Prev in Thread] Current Thread [Next in Thread]