This paper presents a framework for classifying and comparing instances of integer linear programs (ILPs) based on their mathematical structure. It has long been observed that the structure of ILPs can play an important role in determining the effectiveness of certain solution techniques; those that work well for one class of ILPs are often found to be effective in solving similarly structured problems. In this work, the structure of a given ILP instance is captured via a graph-based representation, where decision variables and constraints are described by nodes, and edges denote the presence of decision variables in certain constraints. Using machine learning techniques for graph-structured data, we introduce two approaches for leveraging the graph representations for relating ILPs. In the first approach, a graph convolutional network (GCN) is used to classify ILP graphs as having come from one of a known number of problem classes. The second approach makes use of latent features learned by the GCN to compare ILP graphs to one another directly. As part of the latter approach, we introduce a formal measure of graph-based structural similarity. A series of empirical studies indicate strong performance for both the classification and comparison procedures. Additional properties of ILP graphs, namely, losslessness and permutation invariance, are also explored via computational experiments. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0255 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0255 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question: Can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are used to detect latent structural features therein. The resulting feature vectors are used to measure similarity between images and, consequently, MIPs. An introductory analysis examines a subset of the instances from strIPlib and MIPLIB 2017, two online repositories for MIP instances. Results indicate that structure-based comparisons may allow for relationships to be identified between MIPs from disparate application areas. Additionally, image-based comparisons reveal that ostensibly similar variations of an MIP model may yield instances with markedly different mathematical structures. Summary of Contribution: This paper presents a methodology for comparing mixed integer programs (MIPs) from any research domain based on the structure of the constraint coefficient matrices for one or more instances of a model. Specifically, computer vision and deep learning techniques are used to extract structural features and measure the similarity between these images. This process is agnostic to application area and instead focuses solely on mathematical structure. As a result, this methodology offers a fundamentally new way for operations researchers to view MIP similarity and highlights similarities between research problems that may have previously been viewed as unrelated.

The visual search process is modeled as a sequence of fixations which may or may not partially overlap in coverage of the search field. A single expression is derived for the probability of search success which covers all overlap cases. Making the further assumption that search strategy is chosen so as to maximize expected value, yields the result that each point on the search field must be fixated an integral number of times. In an experiment where visual lobe size and fixation duration were controlled, human subjects behaved in a manner close to that predicted by the optimization model. It is concluded that further development of the model using less restrictive assumptions is warranted.

Orienteering is a sport in which a competitor selects a path from a start to a destination, visiting control points along the path. Each control point has an associated score, and the travel between control points involves a certain cost. The problem is to select a set of control points to visit, so that the total score is maximized subject to a budget constraint on total cost. Several versions of this problem exist. In the version considered in this research, the start and the destination are the same, and the problem is to construct a subtour of the set of control points. The orienteering problem is a variant of the traveling salesman problem, and arises in vehicle routing and production scheduling situations. This problem has been shown to be NP-hard in the literature. We develop an optimal algorithm to solve this problem, using Lagrangean relaxation within a branch-and-bound framework. The Lagrangean relaxation is solved by a degree-constrained spanning tree procedure. Characteristics of the Lagrangean relaxation are studied, and several implementation features to improve the performance of the algorithm are presented. Detailed computational results for problems having up to 150 control points are presented. The results show that the proposed approach is viable for solving problems of medium to large size. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

An efficient interactive solution framework for bicriteria integer programming is developed. The proposed methodology follows the implicit utility maximization approach. The decision maker's underlying utility function is assumed to be pseudoconcave and nondecreasing, and the problem is solved using an interactive branch-and-bound methodology. Several new concepts on bicriteria integer programming that offer great efficiency in the solution process are developed. The framework has been tested extensively, and results with problems having up to 80 variables and 40 constraints are presented. The results show that the methodology is an effective approach to solving practical bicriteria problems.>

An earlier paper by the authors (see ibid., vol.SMC-17, no.3, p.455-64, May/Jun. 1987) described an optimization model of self-paced tracking that could mimic human performance on linear courses. In the present paper, it has been extended to cover circular courses. The literature shows that as the curvature of the track increases (smaller radius) so the performance decreases. The model was able to predict this effect, both from the literature and from an experiment performed using six subjects. The absolute magnitudes of the speeds and error rates were predicted accurately by the model, as were the effects of track width. However, the model predictions underestimated the size of the radius effect somewhat, probably due to the specific biomechanics of the experimental equipment.>

An optimization model of human motor control in a laterally constrained self-paced path control task (e. g., driving) is proposed. The model structures the task as intermittent control with Begg's relationship used to describe the growth of lateral error with distance traveled during the sampling interval. Rewards and penalties are explicitly present in the objective function to be optimized. The path geometry is used with nonlinear optimization to solve the model and show that it has the expected reactions to payoff changes. Tests of the model against existing data in the literature and directly against the data from laboratory subjects showed a very close correspondence in form and numerical values between the model's prediction and human subject's performance.

An approach is presented for solving a discrete-multiple-criteria problem. The approach asks pairwise comparisons of a decision-maker. Under mild assumptions, the method obtains the most preferred alternative. The required number of pairwise comparisons is generally modest. The authors' experience with the method indicates that for reasonable underlying utility functions, a heuristic stopping rule generally yields the most preferred alternative after several comparisons, usually fewer than 20.