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, threads, and tryint.
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.
Starting point
HiGHS can try to find a feasible solution for a MIP based on values given by the user for all or some of the variables. The values need to be specified as variable levels in the GAMS model. If the solution is not feasible or incomplete, HiGHS fixes all given values for discrete variables and solves the remaining problem. If that is a MIP, the effort spend is controlled by option mip_max_start_nodes. For which variables the level values are passed from GAMS to HiGHS is controlled by the parameter mipstart. The parameter values have the following meaning:
- 0: do not pass any variable values to HiGHS
- 1: pass values for all binary and integer variables to HiGHS and let HiGHS try to find a feasible solution for the remaining variables
- 2 (default): if the solution is feasible, pass values for all variables to HiGHS
- 3: pass values for all variables to HiGHS and let HiGHS try to find a feasible solution if it is not feasible
- 4: pass values for all binary and integer variables to HiGHS which fractionality is at most the value of GAMS option tryint (thus, with default tryint=0, only for variables with integral values, the value is passed to HiGHS) and let HiGHS try to find a feasible solution for the the remaining variables; the values passed on to HiGHS are rounded
Note that choices 1 and 3 currently behave equivalently if the solution passed on is not feasible. Also note that HiGHS treats fractional values for discrete variables as if no value has been provided.
Finding an Irreducible Inconsistent Subsystem (IIS) of Constraints
If an LP is infeasible, HiGHS has the capability to identify a subset of the constraints that are infeasible and become feasible once any one of them is eliminated. Option iis can be used to enable finding an IIS.
As an example, consider a GAMS model containing
Positive Variables x, y;
Equation e1;
e1.. x + y =l= -1;
The corresponding HiGHS output when iis has been set to 1 will look like
...
Presolving model
Problem status detected on presolve: Infeasible
Model status : Infeasible
Objective value : 0.0000000000e+00
HiGHS run time : 0.00
Starting Irreducible Inconsistent Subsystem (IIS) computation...
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [1e+00, 1e+00]
Bound [0e+00, 0e+00]
RHS [1e+00, 1e+00]
Presolving model
0 rows, 0 cols, 0 nonzeros 0.000160s
0 rows, 0 cols, 0 nonzeros 0.000189s
Presolve : Reductions: rows 0(-1); columns 0(-4); elements 0(-4) - Reduced to empty
Solving the original LP from the solution after postsolve
Model status : Optimal
Objective value : 1.0000000000e+00
Relative P-D gap : 0.0000000000e+00
HiGHS run time : 0.00
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [1e+00, 1e+00]
Bound [0e+00, 0e+00]
RHS [1e+00, 1e+00]
Solving LP without presolve, or with basis, or unconstrained
Using EKK dual simplex solver - serial
Iteration Objective Infeasibilities num(sum)
0 1.0000000000e+00 Pr: 1(1) 0.00056099892s
0 1.0000000000e+00 0.00058293343s
Model status : Infeasible
Objective value : 1.0000000000e+00
Relative P-D gap : 3.5460523407e-13
HiGHS run time : 0.00
Elasticity filter after 0 passes enforces bounds on 0 cols and 1 rows
Row 0 has status Upper
Col 0 has status Lower
Col 1 has status Lower
Col 2 has status Lower
3 cols, 1 rows, 5 LPs solved (min / average / max) iteration count ( 1 / 1.6 / 2) and time ( 0.00 / 0.00 / 0.00)
IIS found.
Number of equations in IIS: 1
Upper: e1 <= -1
Number of variables in IIS: 3
Lower: x >= 0
Lower: y >= 0
That is, HiGHS finds the problem infeasible. Then the IIS computation is started and an IIS is found. The IIS is then printed to the log and listing file. It consists of the lower bounds of variables x and y and equation e1. This suggests that the entire model can be made feasible by lowering the lower bound of x or y or by increasing the right-hand side of e1.
If one knows in advance that the problem is infeasible, then option iis can be set to 2 to skip the initial solve.
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 |
| iis | whether to compute an irreducible infeasible subset of an LP Set to 1 to compute IIS after solve if infeasible, or to 2 to compute IIS without solving original problem. Range: {0, ..., 2} | 0 |
| iis_strategy | Strategy for IIS calculation: Prioritise rows (default) / Prioritise columns (0/1) Range: {0, ..., 1} | 0 |
| 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_max_start_nodes | MIP solver max number of nodes when completing a partial MIP start Range: {0, ..., ∞} | 500 |
| 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 and how to pass initial level values as starting point to MIP solver See section Starting point for details. Range: {0, ..., 4} | 2 |
| 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, ..., 255} | 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_remove_slacks | Remove slacks after presolve Range: boolean | 0 |
| 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 |