HiGHS
HiGHS is an optimization package for solving continuous and mixed-integer linear programming problems (LPs and MIPs) using simplex, interior-point, and branch-and-cut algorithms. HiGHS is developed by the Edinburgh Research Group in Optimization.
For more detailed information on the implemented simplex method, we refer to [97].
HiGHS also includes the first-order LP solver cuPDLP-C. However, note that feasibility and optimality tolerances may not be satisfied, as cuPDLP-C applies these to the scaled problem only. Further, log output is always passed to standard output, the solve cannot be interrupted (e.g., Ctrl+C), and a timelimit is not obeyed.
Usage
The following statement can be used inside your GAMS program to specify using HiGHS
Option MIP = HIGHS; { or LP or RMIP }
The above statement should appear before the Solve statement. If HiGHS was specified as the default solver during GAMS installation, the above statement is not necessary.
Specification of HiGHS Options
GAMS/HiGHS supports the GAMS parameters reslim, iterlim, nodlim. optca, optcr, cutoff, and threads.
Options can be specified by a HiGHS options file. A HiGHS options file consists of one option or comment per line. A pound sign (#) at the beginning of a line causes the entire line to be ignored. Otherwise, the line will be interpreted as an option name and value separated by an equal sign (=) and any amount of white space (blanks or tabs).
A small example for a highs.opt file is:
solver = ipm ipm_optimality_tolerance = 1e-6 run_crossover = off
It causes HiGHS to use an interior point solver for an LP solve, increases the optimality tolerance to \(10^{-6}\), and turns off crossover to a basis solution.
List of HiGHS Options
In the following, we give a detailed list of all HiGHS options.
| Option | Description | Default |
|---|---|---|
| dual_feasibility_tolerance | Dual feasibility tolerance Range: [1e-10, ∞] | 1e-07 |
| infinite_bound | Limit on |constraint bound|: values greater than or equal to this will be treated as infinite Range: [1e+15, ∞] | 1e+20 |
| infinite_cost | Limit on |cost coefficient|: values greater than or equal to this will be treated as infinite Range: [1e+15, ∞] | 1e+20 |
| ipm_iteration_limit | Iteration limit for IPM solver Range: {0, ..., ∞} | GAMS iterlim |
| ipm_optimality_tolerance | IPM optimality tolerance Range: [1e-12, ∞] | 1e-08 |
| large_matrix_value | Upper limit on |matrix entries|: values greater than or equal to this will be treated as infinite Range: [1, ∞] | 1e+15 |
| mip_abs_gap | Tolerance on absolute gap of MIP, |ub-lb|, to determine whether optimality has been reached for a MIP instance Range: [0, ∞] | GAMS optca |
| mip_allow_restart | Whether MIP restart is permitted Range: boolean | 1 |
| mip_detect_symmetry | Whether MIP symmetry should be detected Range: boolean | 1 |
| mip_feasibility_tolerance | MIP feasibility tolerance Range: [1e-10, ∞] | 1e-06 |
| mip_heuristic_effort | Effort spent for MIP heuristics Range: [0, 1] | 0.05 |
| mip_lp_age_limit | Maximal age of dynamic LP rows before they are removed from the LP relaxation in the MIP solver Range: {0, ..., 32767} | 10 |
| mip_max_improving_sols | Limit on the number of improving solutions found to stop the MIP solver prematurely Range: {1, ..., ∞} | ∞ |
| mip_max_leaves | MIP solver max number of leaf nodes Range: {0, ..., ∞} | ∞ |
| mip_max_nodes | MIP solver max number of nodes Range: {0, ..., ∞} | GAMS nodlim, if > 0, ∞ otherwise |
| mip_max_stall_nodes | MIP solver max number of nodes where estimate is above cutoff bound Range: {0, ..., ∞} | ∞ |
| mip_min_cliquetable_entries_for_parallelism | Minimal number of entries in the MIP solver cliquetable before neighbourhood queries of the conflict graph use parallel processing Range: {0, ..., ∞} | 100000 |
| mip_min_logging_interval | MIP minimum logging interval Range: [0, ∞] | 5 |
| mip_pool_age_limit | Maximal age of rows in the MIP solver cutpool before they are deleted Range: {0, ..., 1000} | 30 |
| mip_pool_soft_limit | Soft limit on the number of rows in the MIP solver cutpool for dynamic age adjustment Range: {1, ..., ∞} | 10000 |
| mip_pscost_minreliable | Minimal number of observations before MIP solver pseudo costs are considered reliable Range: {0, ..., ∞} | 8 |
| mip_rel_gap | Tolerance on relative gap, |ub-lb|/|ub|, to determine whether optimality has been reached for a MIP instance Range: [0, ∞] | GAMS optcr |
| mipstart | Whether to pass initial level values as starting point to MIP solver If the solution is not feasible, HiGHS will solve the LP obtained from fixing all discrete variables to their initial level values. Range: boolean | 0 |
| objective_bound | Objective bound for termination of the dual simplex solver Range: real | GAMS cutoff |
| objective_target | Objective target for termination of the MIP solver Range: real | -∞ |
| output_flag | Enables or disables solver output Range: boolean | 0, if GAMS logoption = 0, otherwise 1 |
| parallel | Parallel option: "off", "choose" or "on" Range: string | choose |
| pdlp_d_gap_tol | Duality gap tolerance for PDLP solver: Default = 1e-4 Range: [1e-12, ∞] | 0.0001 |
| pdlp_iteration_limit | Iteration limit for PDLP solver Range: {0, ..., ∞} | GAMS iterlim |
| pdlp_native_termination | Use native termination for PDLP solver: Default = false Range: boolean | 0 |
| pdlp_scaling | Scaling option for PDLP solver: Default = true Range: boolean | 1 |
| presolve | Presolve option: "off", "choose" or "on" Range: string | choose |
| primal_feasibility_tolerance | Primal feasibility tolerance Range: [1e-10, ∞] | 1e-07 |
| random_seed | Random seed used in HiGHS Range: {0, ..., ∞} | 0 |
| run_crossover | Run IPM crossover: "off", "choose" or "on" Range: string | on |
| sensitivity | Whether to run sensitivity analysis after solving an LP with a simplex method Range: boolean | 0 |
| simplex_dual_edge_weight_strategy | Strategy for simplex dual edge weights: Choose / Dantzig / Devex / Steepest Edge (-1/0/1/2) Range: {-1, ..., 2} | -1 |
| simplex_iteration_limit | Iteration limit for simplex solver when solving LPs, but not subproblems in the MIP solver Range: {0, ..., ∞} | GAMS iterlim |
| simplex_max_concurrency | Maximum level of concurrency in parallel simplex Range: {1, ..., 8} | 8 |
| simplex_primal_edge_weight_strategy | Strategy for simplex primal edge weights: Choose / Dantzig / Devex / Steepest Edge (-1/0/1/2) Range: {-1, ..., 2} | -1 |
| simplex_scale_strategy | Simplex scaling strategy: off / choose / equilibration / forced equilibration / max value 0 / max value 1 (0/1/2/3/4/5) Range: {0, ..., 5} | 1 |
| simplex_strategy | Strategy for simplex solver 0 => Choose; 1 => Dual (serial); 2 => Dual (PAMI); 3 => Dual (SIP); 4 => Primal Range: {0, ..., 4} | 1 |
| simplex_update_limit | Limit on the number of simplex UPDATE operations Range: {0, ..., ∞} | 5000 |
| small_matrix_value | Lower limit on |matrix entries|: values less than or equal to this will be treated as zero Range: [1e-12, ∞] | 1e-09 |
| solution_file | Solution file Range: string | <inputname>.sol |
| solver | LP algorithm to run: "simplex", "choose", "ipm", or "pdlp"; ignored for MIP Range: string | choose |
| solvetrace | Name of file for writing solving progress information during MIP solve Range: string | |
| solvetracenodefreq | Frequency in number of nodes for writing to solve trace file Range: {0, ..., ∞} | 100 |
| solvetracetimefreq | Frequency in seconds for writing to solve trace file Range: [0, ∞] | 5 |
| threads | Number of threads used by HiGHS (0: automatic) Range: {0, ..., ∞} | GAMS threads |
| time_limit | Time limit (seconds) Range: [0, ∞] | GAMS reslim |
| write_model_file | Write model file Range: string | <inputname>.lp |
| write_model_to_file | Write the model to a file Range: boolean | 0 |
| write_solution_style | Style of solution file (raw = computer-readable, pretty = human-readable): -1 => HiGHS old raw (deprecated); 0 => HiGHS raw; 1 => HiGHS pretty; 2 => Glpsol raw; 3 => Glpsol pretty; 4 => HiGHS sparse raw Range: {-1, ..., 4} | 0 |
| write_solution_to_file | Write the primal and dual solution to a file Range: boolean | 0 |
| Options for expert users | ||
| allow_unbounded_or_infeasible | whether to spend extra effort to distinguish unboundedness and infeasibility if necessary Range: boolean | 0 |
| allowed_cost_scale_factor | Largest power-of-two factor permitted when scaling the costs Range: {0, ..., 20} | 0 |
| allowed_matrix_scale_factor | Largest power-of-two factor permitted when scaling the constraint matrix Range: {0, ..., 30} | 20 |
| centring_ratio_tolerance | Centring stops when the ratio max(x_j*s_j) / min(x_j*s_j) is below this tolerance (default = 100) Range: [0, ∞] | 100 |
| cost_scale_factor | Scaling factor for costs Range: {-20, ..., 20} | 0 |
| dual_residual_tolerance | Dual residual tolerance Range: [1e-10, ∞] | 1e-07 |
| dual_simplex_cost_perturbation_multiplier | Dual simplex cost perturbation multiplier: 0 => no perturbation Range: [0, ∞] | 1 |
| dual_simplex_pivot_growth_tolerance | Dual simplex pivot growth tolerance Range: [1e-12, ∞] | 1e-09 |
| dual_steepest_edge_weight_error_tolerance | Tolerance on dual steepest edge weight errors Range: [0, ∞] | ∞ |
| dual_steepest_edge_weight_log_error_threshold | Threshold on dual steepest edge weight errors for Devex switch Range: [1, ∞] | 10 |
| factor_pivot_threshold | Matrix factorization pivot threshold Range: [0.0008, 0.5] | 0.1 |
| factor_pivot_tolerance | Matrix factorization pivot tolerance Range: [0, 1] | 1e-10 |
| highs_analysis_level | Analysis level in HiGHS Range: {0, ..., 63} | 0 |
| highs_debug_level | Debugging level in HiGHS Range: {0, ..., 3} | 0 |
| icrash | Run iCrash Range: boolean | 0 |
| icrash_approx_iter | iCrash approximate minimization iterations Range: {0, ..., 100} | 50 |
| icrash_breakpoints | Exact subproblem solution for iCrash Range: boolean | 0 |
| icrash_dualize | Dualize strategy for iCrash Range: boolean | 0 |
| icrash_exact | Exact subproblem solution for iCrash Range: boolean | 0 |
| icrash_iterations | iCrash iterations Range: {0, ..., 200} | 30 |
| icrash_starting_weight | iCrash starting weight Range: [1e-10, 1e+50] | 0.001 |
| icrash_strategy | Strategy for iCrash Range: string | ICA |
| ipx_dualize_strategy | Strategy for dualizing before IPX Range: {-1, ..., 3} | 2 |
| less_infeasible_DSE_check | Check whether LP is candidate for LiDSE Range: boolean | 1 |
| less_infeasible_DSE_choose_row | Use LiDSE if LP has right properties Range: boolean | 1 |
| log_dev_level | Output development messages: 0 => none; 1 => info; 2 => verbose Range: {0, ..., 3} | 0 |
| lp_presolve_requires_basis_postsolve | Prevents LP presolve steps for which postsolve cannot maintain a basis Range: boolean | 1 |
| max_centring_steps | Maximum number of steps to use (default = 5) when computing the analytic centre Range: {0, ..., ∞} | 5 |
| max_dual_simplex_cleanup_level | Max level of dual simplex cleanup Range: {0, ..., ∞} | 1 |
| max_dual_simplex_phase1_cleanup_level | Max level of dual simplex phase 1 cleanup Range: {0, ..., ∞} | 2 |
| mip_report_level | MIP solver reporting level Range: {0, ..., 2} | 1 |
| no_unnecessary_rebuild_refactor | No unnecessary refactorization on simplex rebuild Range: boolean | 1 |
| presolve_pivot_threshold | Matrix factorization pivot threshold for substitutions in presolve Range: [0.0008, 0.5] | 0.01 |
| presolve_reduction_limit | Limit on number of presolve reductions -1 => no limit Range: {-1, ..., ∞} | -1 |
| presolve_rule_logging | Log effectiveness of presolve rules for LP Range: boolean | 0 |
| presolve_rule_off | Bit mask of presolve rules that are not allowed Range: {0, ..., ∞} | 0 |
| presolve_substitution_maxfillin | Maximal fillin allowed for substitutions in presolve Range: {0, ..., ∞} | 10 |
| primal_residual_tolerance | Primal residual tolerance Range: [1e-10, ∞] | 1e-07 |
| primal_simplex_bound_perturbation_multiplier | Primal simplex bound perturbation multiplier: 0 => no perturbation Range: [0, ∞] | 1 |
| rebuild_refactor_solution_error_tolerance | Tolerance on solution error when considering refactorization on simplex rebuild Range: real | 1e-08 |
| restart_presolve_reduction_limit | Limit on number of further presolve reductions on restart in MIP solver -1 => no limit, otherwise, must be positive Range: {-1, ..., ∞} | -1 |
| run_centring | Perform centring steps or not Range: boolean | 0 |
| simplex_crash_strategy | Strategy for simplex crash: off / LTSSF / Bixby (0/1/2) Range: {0, ..., 9} | 0 |
| simplex_dualize_strategy | Strategy for dualizing before simplex Range: {-1, ..., 1} | -1 |
| simplex_initial_condition_check | Perform initial basis condition check in simplex Range: boolean | 1 |
| simplex_initial_condition_tolerance | Tolerance on initial basis condition in simplex Range: [1, ∞] | 1e+14 |
| simplex_min_concurrency | Minimum level of concurrency in parallel simplex Range: {1, ..., 8} | 1 |
| simplex_permute_strategy | Strategy for permuting before simplex Range: {-1, ..., 1} | -1 |
| simplex_price_strategy | Strategy for PRICE in simplex Range: {0, ..., 3} | 3 |
| simplex_unscaled_solution_strategy | Strategy for solving unscaled LP in simplex Range: {0, ..., 2} | 1 |
| start_crossover_tolerance | Tolerance to be satisfied before IPM crossover will start Range: [1e-12, ∞] | 1e-08 |
| use_implied_bounds_from_presolve | Use relaxed implied bounds from presolve Range: boolean | 0 |
| use_original_HFactor_logic | Use original HFactor logic for sparse vs hyper-sparse TRANs Range: boolean | 1 |