Although most methods for solving mixed-integer optimization problems compute a single optimal solution, a diverse set of near-optimal solutions can often lead to improved outcomes. We present a new method for finding a set of diverse solutions by emphasizing diversity within the search for near-optimal solutions. Specifically, within a branch-and-bound framework, we investigated parameterized node selection rules that explicitly consider diversity. Our results indicate that our approach significantly increases the diversity of the final solution set. When compared with two existing methods, our method runs with similar runtime as regular node selection methods and gives a diversity improvement between 12% and 190%. In contrast, popular node selection rules, such as best-first search, in some instances performed worse than state-of-the-art methods by more than 35% and gave an improvement of no more than 130%. Furthermore, we find that our method is most effective when diversity in node selection is continuously emphasized after reaching a minimal depth in the tree and when the solution set has grown sufficiently large. Our method can be easily incorporated into integer programming solvers and has the potential to significantly increase the diversity of solution sets. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: This work was supported by the Army Research Office [Grant W911NF-21-1-0079]. The views expressed in this study do not represent those of the U.S. Government, the U.S. Department of Defense, or the U.S. Army. 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.2022.0164 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0164 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

We consider integer optimization models for finding stable solutions to many-to-one, utility-weighted matching problems with incomplete preference lists and ties. Whereas traditional algorithmic approaches for the stable many-to-one matching problem, such as the deferred acceptance algorithm, offer efficient performance for the strict problem setting, adaptation to alternative settings often requires careful customization. Optimization-based approaches are free of the need to create customized algorithms for each unique context and can readily accommodate such extensions as (incomplete) preference lists with ties, alternative and nontraditional objective functions, and side constraints including those that ensure stable matching outcomes free of waste. We explore the flexibility of optimization-based approaches in several ways. First, we introduce four new constraint sets that prevent justified envy and a new system of constraints that prevents waste; taken together, they jointly ensure stable matching outcomes. Second, we create two algorithms to accelerate the generation of our proposed constraints. Third, we construct aggregate objective functions to reflect multiple hierarchical emphases by imposing a strict lexicographical order on the individual components. Fourth, we conduct comprehensive experiments to study the computational performance of our proposed optimization models and compare them with models from the extant literature under a variety of problem attributes. Our experiments reveal the circumstances under which each stability representation excels in terms of optimality criteria and computational efficiency on a variety of real and synthetic data sets. One such setting in which our proposed stability representations excel includes the important context of when sufficient seats exist for applicants, such as school choice problems and hospital residency matching. 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 Supplementary Information [ https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.1237 ] or is available from the IJOC GitHub software repository ( https://github.com/INFORMSJoC ) at [ http://dx.doi.org/10.5281/zenodo.6892615 ].

Employment outcomes of resettled refugees depend strongly on where they are placed inside the host country. While the United States sets refugee capacities for communities on an annual basis, refugees arrive and must be placed over the course of the year. We introduce a dynamic allocation system based on two-stage stochastic programming to improve employment outcomes. Our algorithm is able to achieve over 98 percent of the hindsight-optimal employment compared to under 90 percent of current greedy-like approaches. This dramatic improvement persists even when we incorporate a vast array of practical features of the refugee resettlement process including indivisible families, batching, and uncertainty with respect to the number of future arrivals. Our algorithm is now part of the Annie™? MOORE optimization software used by a leading American refugee resettlement agency. The full version of this paper is available at https://arxiv.org/pdf/2105.14388.pdf.

Existing approaches to identify multiple solutions to combinatorial problems in practice are at best limited in their ability to simultaneously incorporate both diversity among generated solutions and problem-specific desires that may only be discovered or articulated by the user after further analysis of solver output. We propose a general framework for problems of a combinatorial nature that can generate a set of of multiple (near-)optimal, diverse solutions that are further infused with desirable features. We call our approach solution engineering. A key novelty is that desirable solution properties need not be explicitly modeled in advance. We customize the framework to both the mathematical programming and constraint programming technologies, and we subsequently demonstrate its practicality by implementing and then conducting computational experiments on existing test instances from the literature. Our computational results confirm the very real possibility of generating sets of solutions infused with features that might otherwise remain undiscovered.

Eye tracking is an increasingly common technology with a variety of practical uses. Eye-tracking data, or gaze data, can be categorized into two main events: fixations represent focused eye movement, indicative of awareness and attention, whereas saccades are higher-velocity movements that occur between fixation events. Common methods to identify fixations in gaze data can lack sensitivity to peripheral points and may misrepresent positional and durational properties of fixations. To address these shortcomings, we introduce the notion of inner density for fixation identification, which concerns both the duration of the fixation and the proximity of its constituent gaze points. Moreover, we demonstrate how to identify fixations in a sequence of gaze data by optimizing for inner density. After decomposing the clustering of a temporal gaze data sequence into successive regions (chunks), we use nonlinear and linear 0–1 optimization formulations to identify the densest fixations within a given data chunk. Our approach is parametrized by a unique constant that adjusts the degree of desired density, allowing decision makers to have fine-tuned control over density during the process. Computational experiments on real data sets demonstrate the efficiency of our approach and its effectiveness in identifying fixations with greater density than existing methods, thereby enabling the refinement of key gaze metrics such as fixation duration and fixation center.

The fast pace of global urbanization is drastically changing the population distributions over the world, which leads to significant changes in geographical population densities. Such changes in turn alter the underlying geographical power demand over time, and drive power substations to become over-supplied (demand z capacity) or under-supplied (demand ≈ capacity). In this paper, we make the first attempt to investigate the problem of power substation-user assignment by analyzing large-scale power grid data. We develop a Scalable Power User Assignment (SPUA) framework, that takes large-scale spatial power user/substation distribution data and temporal user power consumption data as input, and control the assignments between users and substations, in a manner that minimizes the maximum substation utilization among all substations. To evaluate the performance of our SPUA framework, we conduct evaluations on real power consumption data and user/substation location data collected from a northwestern province in China for 35 days in 2015. The evaluation results demonstrate that our SPUA framework can achieve a 20-65 percent reduction on the maximum substation utilization, and 2 to 3.7 times reduction on total transmission loss over other baseline methods.

The fast pace of global urbanization is drastically changing the population distributions over the world, which leads to significant changes in geographical population densities. Such changes in turn alter the underlying geographical power demand over time, and drive power substations to become over-supplied (demand << capacity) or under-supplied (demand ≈ capacity). In this paper, we make the first attempt to investigate the problem of power substation-user assignment by analyzing large-scale power grid data. We develop a Scalable Power User Assignment (SPUA) framework, that takes large-scale spatial power user/substation distribution data and temporal user power consumption data as input, and assigns users to substations, in a manner that minimizes the maximum substation utilization among all substations. To evaluate the performance of our SPUA framework, we conduct evaluations on real power consumption data and user/substation location data collected from a province in China for 35 days in 2015. The evaluation results demonstrate that our SPUA framework can achieve a 20%--65% reduction on the maximum substation utilization, and 2 to 3.7 times reduction on total transmission loss over other baseline methods.

MOTIVATION: A major limitation in modeling protein interactions is the difficulty of assessing the over-fitting of the training set. Recently, an experimentally based approach that integrates crystallographic information of C2H2 zinc finger-DNA complexes with binding data from 11 mutants, 7 from EGR finger I, was used to define an improved interaction code (no optimization). Here, we present a novel mixed integer programming (MIP)-based method that transforms this type of data into an optimized code, demonstrating both the advantages of the mathematical formulation to minimize over- and under-fitting and the robustness of the underlying physical parameters mapped by the code. RESULTS: Based on the structural models of feasible interaction networks for 35 mutants of EGR-DNA complexes, the MIP method minimizes the cumulative binding energy over all complexes for a general set of fundamental protein-DNA interactions. To guard against over-fitting, we use the scalability of the method to probe against the elimination of related interactions. From an initial set of 12 parameters (six hydrogen bonds, five desolvation penalties and a water factor), we proceed to eliminate five of them with only a marginal reduction of the correlation coefficient to 0.9983. Further reduction of parameters negatively impacts the performance of the code (under-fitting). Besides accurately predicting the change in binding affinity of validation sets, the code identifies possible context-dependent effects in the definition of the interaction networks. Yet, the approach of constraining predictions to within a pre-selected set of interactions limits the impact of these potential errors to related low-affinity complexes. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

In this paper we consider the order-preserving submatrix (OPSM) problem. This problem is known to be NP-hard. Although in recent years some heuristic methods have been presented to find OPSMs, they lack the guarantee of optimality. We present exact solution approaches based on linear mixed 0–1 programming formulations and develop algorithmic enhancements to aid in solvability. Encouraging computational results are reported both for synthetic and real biological data. In addition, we discuss theoretical computational complexity issues related to finding fixed patterns in matrices.