|
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
[Prev in Thread] | Current Thread | [Next in Thread] |