Search

Power distribution networks should strive for reliable delivery of energy. In this paper, we support this endeavor by addressing the Maintenance Resources Allocation Problem (MRAP). This problem consists of scheduling preventive maintenance plans on the equipment of distribution networks for a planning horizon, seeking the best trade-offs between system reliability and maintenance budgets. We propose a novel integer linear programming (ILP) formulation to effectively model and solve the MRAP for a single distribution network. The formulation also enables flexibility to suit new developments, such as different reliability metrics and smart-grid innovations. Then we develop a straightforward ILP formulation to address the MRAP for several distribution networks which takes the advantages of exchanging maintenance information between local agents and upper management. Using a general-purpose ILP solver, we performed computational experiments to assess the performance of the proposed approaches. Optimal maintenance trade-offs were achieved with the new formulations for real-scale distribution networks within short running times. To the best of our knowledge, this is the first time that the MRAP is optimally solved using ILP, for single or multiple distribution networks. [ABSTRACT FROM AUTHOR]

The multi-objective integer programming problem often occurs in multi-criteria decision-making situations, where the decision variables are integers. In the present paper, we have discussed an algorithm for finding all efficient solutions of a multi-objective integer quadratic programming problem. The proposed algorithm is based on the aspect that efficient solutions of a multi-objective integer quadratic programming problem can be obtained by enumerating ranked solutions of an integer quadratic programming problem. For determining ranked solutions of an integer quadratic programming problem, we have constructed a related integer linear programming problem and from ranked solutions of this integer linear programming problem, ranked solutions of the original integer quadratic programming problem are generated. Theoretically, we have shown that the developed method generates the set of all efficient solutions in a finite number of steps, and numerically we have elaborated the working of our algorithm and compared our results with existing algorithms. Further, we have analyzed that the developed method is efficient for solving a multi-objective integer quadratic programming problem with a large number of constraints, variables and objectives. [ABSTRACT FROM AUTHOR]

For daily airport operations, the insufficient number and the improper scheduling of ground support vehicles are the main causes of flight delays. In this paper, a novel network model is proposed to complement the optimal scheduling of ferry vehicles for the flight ground support service. In the process of model construction, we first innovatively construct a ferry vehicle capacity network by having the introduced virtual flights and the ferry vehicle depot as nodes, in which the directed edges indicate that the two nodes associated may be consecutively served by the same ferry vehicle. Based on the capacity network, a mixed integer programming model is constructed to minimize the number of ferry vehicles needed. In addition, this paper shows that the mixed integer programming is equivalent to a linear programming when the service start time of each flight is fixed, which makes the solving process more efficient, and the linear programming model can be applied to solve the minimum node-disjoint path cover of directed acyclic graphs. The efficiency and accuracy of the method are validated by the actual flight data obtained from Beijing Capital International Airport. This study will provide a methodological reference for the optimal scheduling of airport ferry vehicles. [ABSTRACT FROM AUTHOR]

The Weapon-Target Assignment (WTA) problem aims to assign a set of weapons to a number of assets (targets), such that the expected value of survived targets is minimized. The WTA problem is a nonlinear combinatorial optimization problem known to be NP-hard. This paper applies several existing techniques to linearize the WTA problem. One linearization technique (Camm et al. in Oper Res 50(6):946–955, 2002) approximates the nonlinear terms of the WTA problem via convex piecewise linear functions and provides heuristic solutions to the WTA problem. Such approximation problems are, though, relatively easy to solve from the computational point of view even for large-scale problem instances. Another approach proposed by O'Hanley et al. (Eur J Oper Res 230(1):63–75, 2013) linearizes the WTA problem exactly at the expense of incorporating a significant number of additional variables and constraints, which makes many large-scale problem instances intractable. Motivated by the results of computational experiments with these existing solution approaches, a specialized new exact solution approach is developed, which is called branch-and-adjust. The proposed solution approach involves the compact piecewise linear convex under-approximation of the WTA objective function and solves the WTA problem exactly. The algorithm builds on top of any existing branch-and-cut or branch-and-bound algorithm and can be implemented using the tools provided by state-of-the-art mixed integer linear programming solvers. Numerical experiments demonstrate that the proposed specialized algorithm is capable of handling very large scale problem instances with up to 1500 weapons and 1000 targets, obtaining solutions with optimality gaps of up to 2.0 % within 2 h of computational runtime. [ABSTRACT FROM AUTHOR]

In this paper we propose a two-phase approach to solve the shift and break design problem using integer linear programming. In the first phase we create the shifts, while heuristically taking the breaks into account. In the second phase we assign breaks to each occurrence of any shift, one by one, repeating this until no improvement is found. On a set of benchmark instances, composed by both randomly-generated and real-life ones, this approach obtains better results than the current best known method for shift and break design problem. [ABSTRACT FROM AUTHOR]

The problem of optimizing a linear plus linear fractional function is an important field of search, it is a difficult problem since the linear plus linear fractional function doesn't possess any convexity propriety. In this paper, we propose a method that generates the set of the efficient solutions of multiobjective integer linear plus linear fractional programming problem. Our method consists in Branch-and-Bound exploration combined with cutting plane technique that allows to remove from search inefficient solutions. The cutting plane technique takes into account the inefficiency of a solution in another problem that implies the inefficiency of that solution in our problem and uses this link to reduce the exploration's domain. [ABSTRACT FROM AUTHOR]

The problem of dividing political territories in electoral process is a very important factor which contributes to the development of democracy in modern political systems. The most significant criteria for fairness of electoral process are demographic, geographic and political. Demographic criterion in the first place refers to the population equality, while the geographic one is mostly represented by compactness, contiguity and integrity. In this paper we propose a new integer linear programming formulation for the problem of political districting. The model is based on the graph representation of political territory, where territorial units are vertices and direct links between them are edges. The correctness of integer linear programming formulation is mathematically proven. In contrast to the most of the previous formulations, all three major criteria, population equality, compactness and contiguity, are completely taken into consideration. There are two models, one which deals with afore mentioned criteria where compactness is taken as an objective function, and the other one which takes into account interests of the decision maker, i.e. the political ruling body which organizes elections. Several numerical examples for the presented models are given which illustrate general aspects of the problem. The experimental results are obtained using CPLEX solver. [ABSTRACT FROM AUTHOR]

In this paper, we provide a model which optimizes the allocation of electricity generation systems, in terms of their number and location, in a disaster relief camp. The objectives that this model takes into account are minimization of the total cost of the project and prioritization of those generation systems that perform favourably. Energy and specifically electricity plays an important role in the provision of essential needs like lighting, water purification, heating, ventilation and medical care for displaced people. Disaster relief camps are commonly considered as off-grid projects, so individual generation and control systems are the main means of electrification. To support decision makers in electrification planning for temporary and semi-temporary camps, we propose a bi-objective integer linear programming model. The performance evaluation of technologies such as fuel generators, wind turbines and solar panels is conducted with an MCDM (VIKOR) approach. The model is applied on a hypothetical but realistic map site with data regarding commercially available equipment. The better performance of solar panels regarding the evaluation criteria have made them the dominant applied source of renewable electricity generation system and together with application of micro-grids in the model they have proven to reduce the cost of generation significantly. However, installing fuel generators have been found necessary for facilities which can cause a remarkable damage in case of electricity interruption. The model is promising in helping relief aid agencies to design an electrification project with minimum cost and maximum utility. [ABSTRACT FROM AUTHOR]

A large number of real-world optimization problems can be formulated as Mixed Integer Linear Programs (MILP). MILP solvers expose numerous configuration parameters to control their internal algorithms. Solutions, and their associated costs or runtimes, are significantly affected by the choice of the configuration parameters, even when problem instances have the same number of decision variables and constraints. On one hand, using the default solver configuration leads to suboptimal solutions. On the other hand, searching and evaluating a large number of configurations for every problem instance is time-consuming and, in some cases, infeasible. In this study, we aim to predict configuration parameters for unseen problem instances that yield lower-cost solutions without the time overhead of searching-and-evaluating configurations at the solving time. Toward that goal, we first investigate the cost correlation of MILP problem instances that come from the same distribution when solved using different configurations. We show that instances that have similar costs using one solver configuration also have similar costs using another solver configuration in the same runtime environment. After that, we present a methodology based on Deep Metric Learning to learn MILP similarities that correlate with their final solutions' costs. At inference time, given a new problem instance, it is first projected into the learned metric space using the trained model, and configuration parameters are instantly predicted using previously-explored configurations from the nearest neighbor instance in the learned embedding space. Empirical results on real-world problem benchmarks show that our method predicts configuration parameters that improve solutions' costs by up to 38% compared to existing approaches. [ABSTRACT FROM AUTHOR]

In this paper we present two mixed-integer programming formulations for the curriculum based course timetabling problem (CTT). We show that the formulations contain underlying network structures by dividing the CTT into two separate models and then connect the two models using flow formulation techniques. The first mixed-integer programming formulation is based on an underlying minimum cost flow problem, which decreases the number of integer variables significantly and improves the performance compared to an intuitive mixed-integer programming formulation. The second formulation is based on a multi-commodity flow problem which in general is NP-hard, however, we prove that it suffices to solve the linear programming relaxation of the model. The formulations show competitiveness with other approaches based on mixed-integer programming from the literature and improve the currently best known lower bound on one data instance in the benchmark data set from the second international timetabling competition. Regarding upper bounds, the formulation based on the minimum cost flow problem performs better on average than other mixed integer programming approaches for the CTT. [ABSTRACT FROM AUTHOR]

In this paper, the multi-product facility location problem in a two-stage supply chain is investigated. In this problem, the locations of depots (distribution centres) need to be determined along with their corresponding capacities. Moreover, the product flows from the plants to depots and onto customers must also be optimised. Here, plants have a production limit whereas potential depots have several possible capacity levels to choose from, which are defined as multilevel capacities. Plants must serve customer demands via depots. Two integer linear programming (ILP) models are introduced to solve the problem in order to minimise the fixed costs of opening depots and transportation costs. In the first model, the depot capacity is based on the maximum number of each product that can be stored whereas in the second one, the capacity is determined by the size (volume) of the depot. For large problems, the models are very difficult to solve using an exact method. Therefore, a matheuristic approach based on an aggregation approach and an exact method (ILP) is proposed in order to solve such problems. The methods are assessed using randomly generated data sets and existing data sets taken from the literature. The solutions obtained from the computational study confirm the effectiveness of the proposed matheuristic approach which outperforms the exact method. In addition, a case study arising from the wind energy sector in the UK is presented. [ABSTRACT FROM AUTHOR]

In this paper we present the solution to a weekly log-truck scheduling problem (LTSP) integrating the routing and scheduling of trucks where all goods are transported in full truckloads. We must take into account pick-up and delivery requirements, multiple products, inventory levels, and lunch breaks. The objective is to minimize the overall transportation cost including wait times and the empty and loaded distance traveled. Our solution is based on a two-phase approach. The first phase involves an integer linear program that determines the destinations of full truckloads. The second phase uses an implicit integer linear program based on an arc formulation to ensure that the trucks are routed and scheduled at a minimum cost. Experiments have been conducted using Cplex 12.4.0, and almost all instances were solved within six hours with a reasonable gap. [ABSTRACT FROM AUTHOR]

Airplane deicing is a safety measure to eliminate/prevent icing on airplanes that can lead to airflow disruption and emergency conditions. Aircraft deicing/anti-icing fluids (ADF) are high in glycol content. At Dallas Fort Worth International Airport (DFW), the major aircraft deicing activities are conducted at designated deicing pads called Source Isolation Deicing Sites, where ADF run-off can be captured and conveyed into the airport’s glycol collection system. A portion of ADF drips from the aircraft during taxiing and shears off the aircraft during take-off, entering nearby waterways without treatment. Glycol acts as a nutrient for bacteria in the airport’s receiving waterways, resulting in an increase in bacterial growth and a subsequent reduction in dissolved oxygen (DO), potentially endangering aquatic life. This paper proposes a prototype data-driven deicing activities management framework for DFW to address the complexity of airport deicing operations and its impacts. The proposed framework uses stochastic dynamic programming (SDP) to assign airplanes in each hour to deicing pad locations, so as to maximize DO in the receiving waters, subject to airport constraints. Some data were artificially generated using the available knowledge of airport operations. The state transition equations in SDP were estimated. The proposed framework was demonstrated using three cases during major deicing events. Improvements in DO compared with actual DO recorded in the data were mixed; however, the results motivated DFW to implement a new data collection process to replace the artificially-generated data, so that a more accurate optimization could be conducted in the future. [ABSTRACT FROM AUTHOR]

It is commonly assumed in the optimal auction design literature that valuations of buyers are independently drawn from a unique distribution. In this paper we study auctions under ambiguity, that is, in an environment where valuation distribution is uncertain itself, and present a linear programming approach to robust auction design problem with a discrete type space. We develop an algorithm that gives the optimal solution to the problem under certain assumptions when the seller is ambiguity averse with a finite prior set $${\mathcal {P}}$$ and the buyers are ambiguity neutral with a prior $$f\in {\mathcal {P}}$$ . We also consider the case where all parties, the buyers and the seller, are ambiguity averse, and formulate this problem as a mixed integer programming problem. Then, we propose a hybrid algorithm that enables to compute an optimal solution for the problem in reduced time. [ABSTRACT FROM AUTHOR]

This paper deals with uncapacitated single and multiple allocation p-hub maximal covering problems (USApHMCP and UMApHMCP) with binary and partial covering criteria. We present new mixed-integer programming formulations of the considered problems, which are valid for both binary and partial coverage cases. The efficiency of the proposed formulations is evaluated through computational experiments on smaller-size instances, and compared with the state-of-the art models from the literature. The obtained results indicate that the new UMApHMCP formulation outperforms the existing one for both coverage criteria in the sense of solutions' quality and running times. In order to solve instances of larger problem dimension, we develop two heuristic methods based on variable neighborhood search: general VNS (GVNS) for USApHMCP and basic VNS (BVNS) for UMApHMCP. The proposed GVNS and BVNS involve the same shaking procedure in order to hopefully escape local minima traps, while local search phases in GVNS and BVNS use different neighborhood structures in accordance with applied allocation schemes. Computational experiments conducted on smaller-size instances showed that both GVNS and BVNS almost instantly reach all known optimal solutions. In addition, the proposed GVNS and BVNS showed to be very efficient when solving large and large-scale hub instances with up to 1000 nodes, which were not previously considered as test instances for the considered problems. Both GVNS and BVNS provided best solutions on challenging USApHMCP and UMApHMCP instances for both coverage cases in short running times, which indicates their potential to be applied to similar problems. [ABSTRACT FROM AUTHOR]

This paper addresses a variant of the Orienteering Problem taking into account mandatory visits and exclusionary constraints (conflicts among nodes). Five mixed integer linear formulations are adapted from the Traveling Salesman Problem literature in order to provide a robust formulation for this problem. The main difference among these formulations lies in the way they deal with the subtour elimination constraints. The performance of the proposed formulations is evaluated over a large set of instances. Computational results reveal that the model that avoids subtours by means of a single-commodity flow formulation allows to solve to optimality more instances than the other formulations, within a time limit of 1 h. [ABSTRACT FROM AUTHOR]

In this paper, we develop an interactive algorithm that finds the most preferred solution of a decision maker (DM) for multi-objective integer programming problems. We assume that the DM's preferences are consistent with a quasiconcave value function unknown to us. Based on the properties of quasiconcave value functions and pairwise preference information obtained from the DM, we generate constraints to restrict the implied inferior regions. The algorithm continues iteratively and guarantees to find the most preferred solution for integer programs. We test the performance of the algorithm on multi-objective assignment, knapsack, and shortest path problems and show that it works well. [ABSTRACT FROM AUTHOR]

This paper investigates the two-dimensional strip packing problem considering the case in which items should be arranged to form a physically stable packing satisfying a predefined item unloading order from the top of the strip. The packing stability analysis is based on conditions for the static equilibrium of rigid bodies, differing from others strategies which are based on area and percentage of support. We consider an integer linear programming model for the strip packing problem with the order constraint, and a cutting plane algorithm to handle stability, leading to a branch-and-cut approach. We also present two heuristics: the first is based on a stack building algorithm; and, the last is a slight modification of the branch-and-cut approach. The computational experiments show that the branch-and-cut model can handle small and medium-sized instances, whereas the heuristics found almost optimal solutions quickly for several instances. With the combination of heuristics and the branch-and-cut algorithm, many instances are solved to near optimality in a few seconds. [ABSTRACT FROM AUTHOR]

In the regular work process of peer review, editors have to read and understand the entire set of submissions to choose appropriate reviewers. However, due to a large number of submissions, to select reviewers manually becomes error-prone and time-consuming. In this research, a framework that considers different indispensable aspects such as topical relevance, topical authority and research interest is presented and, an integer linear programming problem is formulated with practical considerations to recommend reviewers for a group of submissions. Specifically, the topical relevance and the topical authority are utilized to recommend relevant and accredited candidates in submission-related topics, while the research interest is to exam the willingness of candidates to review a submission. To evaluate the effectiveness of the proposed approach, categories of comparative experiments were conducted on two large scholarly datasets. Experimental results demonstrate that, compared with benchmark approaches, the proposed approach is capable to capture the research interest of reviewer candidates without a significant loss in different evaluation metrics. Our work can be helpful for editors to invite matching experts in peer review and highlight the necessity to uncover valuable information from big scholarly data for expert selection. [ABSTRACT FROM AUTHOR]

The civilian nuclear fuel cycle is an industrial process that produces electrical power from the nuclear fission of uranium. Using a measurement system to accurately account for possibly dangerous nuclear material, such as uranium, in a fuel cycle is important because of its possible loss or diversion. A measurement system is defined by a set of measurement methods, or "devices," used to account for material flows and inventory values at specific locations at facilities in the fuel cycle. We develop a simulation-optimization algorithm and an integer-programming model to find the best, or near-best, resource-limited measurement system with a high degree of confidence. The simulation-optimization algorithm minimizes a weighted sum of false positive and false negative diversion-detection probabilities while accounting for material quantities and measurement errors across a finite, discrete time horizon in hypothetical non-diversion and diversion contexts. In each time period, the estimated cumulative material unaccounted for is compared to a fixed or an optimized threshold value to assess if a "significant amount of material" is lost from a measurement system. The integer-programming model minimizes the population variance of the estimated material loss, i.e., material unaccounted for, in a measurement system. We analyze three potential problems in nuclear fuel cycle measurement systems: (i) given location-dependent device precisions, find the configuration of n devices at n locations (n=3) that provides the lowest corresponding objective values using the simulation-optimization algorithm and integer-programming model, (ii) find the location at which improving device precision reduces objective values the most using the simulation-optimization algorithm (given the device accuracy is 100%), and (iii) determine the effect of measurement frequency on measurement system configurations and objective values using the simulation-optimization algorithm. We obtain comparable results for each problem at least an order of magnitude faster than existing methods do. Using an optimized, rather than a fixed, detection threshold in the simulation-optimization algorithm reduces the weighted sum of false positive and false negative probabilities. [ABSTRACT FROM AUTHOR]

This study considers a combination of strategic and tactical levels of operating room planning where two types of full-day and half-day blocks are considered. Constraints on available beds in hospital wards and different durations of stay for elective patients in the ward are the main assumptions of the problem. The aim is to minimize overtime and idleness of operating rooms, maximize surgeons' satisfaction and minimize the number of unscheduled surgeries in the master surgery schedule. We propose a mixed integer programming model as well as a novel heuristic algorithm by combining simulated annealing meta-heuristic and linear programming models. Real data from a teaching-educational hospital with 20 operating rooms and 47 surgeons' groups as well as some random problem instances are used in the experiments. The results indicate high performance of the proposed heuristic algorithm in generating near-optimal Pareto solutions compared with the mathematical model and a local search algorithm from the literature. Sensitivity analysis is done on some parameters of the problem like overtime cost of operating rooms, maximum allowable overtime, available beds in the ward, and the number of attendance days preferred by each surgeon. The results from our case study show that 6% of operating room costs are related to the fact that some surgeons are unwilling to perform surgeries on some days of a week. Also, adding 20% to the capacity of ward beds results in 3% and 10% decrease in unscheduled surgeries and operating rooms idleness, respectively. [ABSTRACT FROM AUTHOR]

In this article we introduce robustness measures in the context of multi-objective integer linear programming problems. The proposed measures are in line with the concept of decision robustness, which considers the uncertainty with respect to the implementation of a specific solution. An efficient solution is considered to be decision robust if many solutions in its neighborhood are efficient as well. This rather new area of research differs from robustness concepts dealing with imperfect knowledge of data parameters. Our approach implies a two-phase procedure, where in the first phase the set of all efficient solutions is computed, and in the second phase the neighborhood of each one of the solutions is determined. The indicators we propose are based on the knowledge of these neighborhoods. We discuss consistency properties for the indicators, present some numerical evaluations for specific problem classes and show potential fields of application. [ABSTRACT FROM AUTHOR]

The drainage area maximization problem for an unconventional hydrocarbon field is addressed with the objective of designing a development plan that optimizes total production while satisfying environmental and operating constraints. The various characteristics of the problem are presented and a solution approach is developed around an integer linear programming model applied to a discretisation of the field's geographical area. Computational experiments show that the approach provides a practical response to the problem, generating solutions that comply with all of the constraints. The algorithm implemented under this approach has been incorporated into a software tool for planning and managing unconventional hydrocarbon operations and has been used since 2018 by two leading petroleum companies in Argentina to improve unconventional development plans for the country's "Vaca Muerta" geological formation. [ABSTRACT FROM AUTHOR]

The top two divisions of the Argentinean professional basketball system have since 2014–2015 used a season schedule format similar to that used by the NBA in which games are played all through the week, replacing the previous setup where all games were scheduled on weekends. This change has confronted the Argentinean league organizers with new scheduling challenges, one of which is the assignment of referees to games. The present article addresses this assignment problem using a tool based on an integer linear programming model. The objective is to minimize the total cost of trips made by the referees while also satisfying a series of other conditions. The problem is broken down into a series of relatively small subproblems representing successive periods of the season, and the solution is obtained using a rolling horizon heuristic. The approach was tested by applying it to the First Division's 2015–2016 season, the last one before introducing the approach presented in this article, when referees were still assigned using manual methods. The travel costs simulated by the model were 26% lower than the total travel costs actually incurred under the manual assignments, and all of the restrictions that had been requested by league officials were satisfied. The model was used by the First Division for the 2016–2017 and 2017–2018 seasons and in 2017–2018 also by the Second Division. [ABSTRACT FROM AUTHOR]

This work presents guillotine constraints for two- and three-dimensional cutting problems. These problems look for a subset of rectangular items of maximum value that can be cut from a single rectangular container. Guillotine constraints seek to ensure that items are arranged in such a way that cuts from one edge of the container to the opposite edge completely separate them. In particular, we consider the possibility of 2, 3, and 4 cutting stages in a predefined sequence. These constraints are considered within a two-level iterative approach that combines the resolution of integer linear programming and constraint programming models. Experiments with instances of the literature are carried out, and the results show that the proposed approach can solve in less than 500 s approximately 60% and 50% of the instances for the two- and three-dimensional cases, respectively. For the two-dimensional case, in comparison with the recent literature, it was possible to improve the upper bound for 16% of the instances. [ABSTRACT FROM AUTHOR]

Phylogenetic trees are leaf-labelled trees used to model the evolution of species. Here we explore the practical impact of kernelization (i.e. data reduction) on the NP-hard problem of computing the TBR distance between two unrooted binary phylogenetic trees. This problem is better-known in the literature as the maximum agreement forest problem, where the goal is to partition the two trees into a minimum number of common, non-overlapping subtrees. We have implemented two well-known reduction rules, the subtree and chain reduction, and five more recent, theoretically stronger reduction rules, and compare the reduction achieved with and without the stronger rules. We find that the new rules yield smaller reduced instances and thus have clear practical added value. In many cases they also cause the TBR distance to decrease in a controlled fashion, which can further facilitate solving the problem in practice. Next, we compare the achieved reduction to the known worst-case theoretical bounds of 15 k - 9 and 11 k - 9 respectively, on the number of leaves of the two reduced trees, where k is the TBR distance, observing in both cases a far larger reduction in practice. As a by-product of our experimental framework we obtain a number of new insights into the actual computation of TBR distance. We find, for example, that very strong lower bounds on TBR distance can be obtained efficiently by randomly sampling certain carefully constructed partitions of the leaf labels, and identify instances which seem particularly challenging to solve exactly. The reduction rules have been implemented within our new solver Tubro which combines kernelization with an Integer Linear Programming (ILP) approach. Tubro also incorporates a number of additional features, such as a cluster reduction and a practical upper-bounding heuristic, and it can leverage combinatorial insights emerging from the proofs of correctness of the reduction rules to simplify the ILP. [ABSTRACT FROM AUTHOR]

Political districting (PD) is a wide studied topic in the literature since the 60s. It typically requires a multi-criteria approach, and mathematical programs are frequently suggested to model the many aspects of this difficult problem. This implies that exact models cannot be solved to optimality when the size of the territory is too large. In spite of this, an exact formulation can also be exploited in a heuristic framework to find at least a sub-optimal solution for large size problem instances. We study the design of electoral districts in Mexico, where the population is characterized by the presence of minority groups ("indigenous community") who have a special right to be represented in the Parliament. For this, the Mexican electoral law prescribes that a fixed number of districts must be designed to support the representation of the indigenous community. We formulate mixed integer linear programs (MILP) following these two principles, but also including the basic PD criteria of contiguity and population balance. The district map is obtained in two stages: first we produce the fixed number of indigenous districts established by the Law; then we complete the district map by forming the non-indigenous districts. This two-phase approach has two advantages: a dedicated objective function can be formulated in Phase 1 to form indigenous districts at best; in the second phase the instance size is reduced (both in the number of territorial units and in the number of districts) so that the computational effort to solve the problem is reduced as well. We test our procedure on the territory of Chiapas in Mexico and on some fictitious problem instances in which the territory is represented by a grid graph. We also compare our district map with the Institutional one currently adopted in Chiapas. [ABSTRACT FROM AUTHOR]

In this note we have discussed that a simplex like algorithm to solve a indefinite quadratic fractional programming problem proposed by Mekhilef et al. (Ann Oper Res, 2019. https://doi.org/10.1007/s10479-019-03178-2) fails to find its optimal solution and so it may not generate the actual set of efficient points of the corresponding multi-objective integer indefinite quadratic fractional programs. A counter example in support of this argument is also given. [ABSTRACT FROM AUTHOR]

Based on the sociometric analysis of social networks, we introduce the sociotechnical teams formation problem (STFP). Given a group of individuals with different skill-sets and a social network that captures the mutual affinity between them, the problem consists in finding a set of pairwise disjoint teams, as harmonious as possible, with a minimum specified number of individuals per team per skill. We prove that STFP is NP -hard and propose an integer linear programming formulation. We show several classes of facet-inducing inequalities for the corresponding polytope. Computational experiments performed on a set of 120 test instances attest the efficiency of a solution method based on the formulation strengthened by valid inequalities and on a simulated annealing algorithm used to provide good initial feasible solutions. [ABSTRACT FROM AUTHOR]

A cutting-plane approach is developed for the problem of optimally scheduling jobs with arbitrary precedence constraints on unrelated parallel machines to minimize weighted completion time. While the single machine version of this problem has attracted much research efforts, enabling solving problems with up to 100 jobs, not much has been done on the multiple machines case. A novel mixed-integer programming model is presented for the problem with multiple machines. For this model, many classes of valid inequalities that cut off fractional linear programming solutions are developed. This leads to an increase of the linear programming lower bound from 89.3 to 94.6% of the corresponding optimal solution, and a substantial reduction in the computational time of an optimal branch-and-bound algorithm for this problem. This enables us to report optimal solutions for problem instances with up to 25 jobs and 5 machines, which is more than twice the size of problems for which optimal solutions have been reported in the literature thus far. For a special case of the problem—that of minimizing makespan—application of our model helps solve 18 of 27 previously unsolved problem instances to optimality. [ABSTRACT FROM AUTHOR]

Incineration plants produce heat and power from waste, reduce waste disposal to landfills, and discharge harmful emissions and bottom ash. The objective of the incineration plant is to maximize desirable outputs (heat and power) and minimize undesirable outputs (emissions and bottom ash). Therefore, studying the overall impact of incineration plants in a region so as to maximize the benefits and minimize the environmental impact is significant. Majority of prior works focus on plant specific decision making issues including performance analysis. This study proposes a hybrid data envelopment analysis (DEA), goal programming (GP) and mixed integer linear programming (MILP) model to assess the performance of incineration plants, in a specific region, to enhance overall power production, consumption of waste and reduction of emissions. This model not only helps the plant operators to evaluate the effectiveness of incineration but also facilitates the policy makers to plan for overall waste management of the region through decision-making on adding and closing plants on the basis of their efficiency. Majority of prior studies on incineration plants emphasize on how to improve their performance on heat and power production and neglect the waste management aspects. Additionally, optimizing benefits and minimizing negative outputs through fixing targets in order to make decision on shutting down the suboptimal plants has not been modeled in prior research. This research combines both the aspects and addresses the overall performance enhancement of incineration plants within a region from both policy makers and plant operators’ perspectives. The proposed combined DEA, GP and MILP model enables to optimize incineration plants performance within a region by deriving efficiency of each plant and identifying plants to close down on the basis of their performance. The proposed model has been applied to a group of 22 incineration plants in the UK using secondary data in order to demonstrate the effectiveness of the model. [ABSTRACT FROM AUTHOR]

In this article, a new exact method is proposed to solve a problem, say (ILFP)E, of maximizing a linear fractional function over the integer efficient set of multi-objective integer linear programming problem (MOILP). The method is developed through the branch and cut technique and the continuous linear fractional programming, to come up with an integer optimal solution for problem (ILFP)E without having to explicitly list all efficient solutions of problem (MOILP). The branching process is strengthened by an efficient cut as well as an efficiency test so that a large number of non-efficient feasible solutions can be avoided. Illustrative example and an experimental study are reported to show the merit of this new approach. [ABSTRACT FROM AUTHOR]

A mixed integer linear programming (MILP) for the detailed production planning of multiproduct batch plants is presented in this work. New timing decisions are incorporated to the model taking into account that an operation mode based in campaigns is adopted. This operation mode assures a more efficient production management adjusted to the specific context conditions of the considered time horizon. In addition, special considerations as sequence-dependent changeover times and different unit sizes for parallel units in each stage are taken into account. The problem consists of determining the amount of each product to be produced, stored and sold over the given time horizon, the composition of the production campaign (number of batches and their sizes), the assignment, sequencing and timing of batches, and the number of repetitions of the campaign, for a given plant with known product recipes. The objective is to maximize the net profit fulfilling the minimum and maximum product demands. The proposed model provides a useful tool for solving the optimal campaign planning of installed facilities in reasonable computation time, taking different decisions about the operations management. [ABSTRACT FROM AUTHOR]

We consider a timetabling and rostering problem involving periodic retraining of large numbers of employees at an Australian electricity distributor. This problem is different from traditional high school and university timetabling problems studied in the literature in several aspects. We propose a three-stage heuristic consisting of timetable generation, timetable improvement, and trainer rostering. Large-scale integer linear programming models for both the timetabling and the rostering components are proposed, and several unique operational constraints are discussed. We show that this solution approach is able to produce good solutions in practically acceptable time. [ABSTRACT FROM AUTHOR]