A new hyperplanes intersection simulated annealing (HISA) algorithm, based on a discrete representation of the search space as a combinatorial set of hyperplanes intersections, is developed for maximum score estimation of the binary choice model. As a prerequisite of the discrete space simulated annealing algorithm, also, a multi-start hyperplanes intersection local search algorithm (HILS) is devised. The implementation of the local search and simulated annealing algorithms searches the space of hyperplanes intersections combinations formulated by the regression's observations. A set of attributes that are equivalent to the hyperplanes whose intersections define potential maxima is selected as the solution representation. A swap move is introduced so that starting from an arbitrary set of attributes, nearby sets of attributes are generated and evaluated either using the steepest ascent or the Metropolis criterion. Applications include a work-trip mode choice application, for which the global optimum is known, and two labour force participation datasets with unknown global optima. Comparison is made to leading heuristic and metaheuristic approaches as well as to Mixed Integer Programming. Results show that multi-start HILS and especially HISA offer the best results for the two labour force participation datasets, and also discover the global optimum in the work-trip mode choice application.
