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 contrast to methods of parametric linear programming which were developed soon after the invention of the simplex algorithm and are easily included as an extension of that method, techniques for parametric analysis on integer programs are not well known and require considerable effort to append them to an integer programming solution algorithm. The paper reviews some of the theory employed in parametric integer programming, then discusses algorithmic work in this area over the last 15 years when integer programs are solved by different methods. A summary of applications is included and the article concludes that parametric integer programming is a valuable tool of analysis awaiting further popularization. [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 purpose of this paper is to use mathematical programming, including linear programming, dynamic programming, integer programming and goal programming to verify rule-based knowledge. We investigate both domain independent verification, exploiting the general structure of rules, and domain dependent verification, exploiting structure in the domain. Mathematical programming software is readily available and is very efficient. As a result, verification using mathematical programming can be very efficient at finding errors. Mathematical programming can be used to more than just find errors in knowledge representation. Once an error has been found, mathematical programming can be used to ‘recommend’ an alternative. The recommendation can take into account the previous verified knowledge to mitigate the potential introduction of redundant knowledge and to help guide the choice process. Normally the development of recommendations to fix errors has been ignored in the verification literature, and treated as a separate knowledge acquisition task. Accordingly, this paper also extends the verification effort by providing a recommendation on how to fix errors. [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]

We present some personal reflections on the developments in integer and mixed-integer programming from 1968 up to around 1980. [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 formulating a combinatorial optimisation problem (COP) using Discrete or Integer Programming (IP) modelling techniques, the modeller is restricted to use only certain predefined discrete variables and sets which are linked by sets of linear equality and inequality constraints. Definition of many COPs includes restrictions in which the use of dis-equality (DI) constraints in their mathematical representation is inevitable. To represent this type of constraint a number of binary variables and extra constraints are usually introduced, which lead to an increase in the size of the model in terms of variables and constraints. In this paper, we introduce a new class of discrete variables which enables the modeller to represent DI constraints more efficiently in the mathematical formulation of a combinatorial optimisation problem. We have also introduced a new branching scheme to the conventional simplex based Branch and Bound (B&B) algorithm in order to deal with this type of variables. To study the effect of these variables, we modelled and solved a set of five classic problems, first using conventional MP variables and second, exploiting the new proposed variables, and compared the results. The empirical results show a promising improvement on the performance of the B&B algorithm. The contribution of this paper is (1) the introduction of a new class of discrete variables which can help to build smaller models, and (2) new branching schemes on these variables that can improve the B&B performance. [ABSTRACT FROM AUTHOR]

In a dynamic manufacturing environment, manufacturing cell configurations based on current part mix and production process may need to be revised once the part mix or the production process has changed. However, machine and equipment moving costs make frequent reconfiguration uneconomical and sometimes impossible. Designing a sustainable cellular manufacturing system in a dynamic environment is studied in this paper. An integer programming model is developed to minimize material handling and machine costs as well as cell reconfiguration cost for a planning horizon of multiple time periods. Solving this integer programming problem is NP-complete. A decomposition approach is developed so that the decomposed subproblems can be solved with less computational effort. Dynamic programming is then employed to find a solution of the original problem. Numerical examples are presented to illustrate the model and the solution technique developed in this paper. [ABSTRACT FROM AUTHOR]

In this paper some results on stability and sensitivity analysis in multiobjective nonlinear programming are surveyed. Given a family of parametrized multiobjective programming problems, the perturbation map is defined as the set-valued map which associates to each parameter value the set of minimal points of the perturbed feasible set with respect to an ordering convex cone. The behavior of the perturbation map is analyzed both qualitatively and quantitatively. First, some sufficient conditions which guarantee the upper and lower semicontinuity of the perturbation map are provided. The contingent derivatives of the perturbation map are also studied. Moreover, it is shown that the results can be refined in the convex case. [ABSTRACT FROM AUTHOR]

This paper illustrates how the application of integer programming to logic can reveal parallels between logic and mathematics and lead to new algorithms for inference in knowledge-based systems. If logical clauses (stating that at least one of a set of literals is true) are written as inequalities, then the resolvent of two clauses corresponds to a certain cutting plane in integer programming. By properly enlarging the class of cutting planes to cover clauses that state that at least a specified number of literals are true, we obtain a generalization of resolution that involves both cancellation-type and circulant-type sums. We show its completeness by proving that it generates all prime implications, generalizing an early result by Quine. This leads to a cutting-plane algorithm as well as a generalized resolution algorithm for checking whether a set of propositions, perhaps representing a knowledge base, logically implies a given proposition. The paper is intended to be readable by persons with either an operations research or an artificial intelligence background. [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]

In this paper, we consider the well-known resource-constrained project scheduling problem. We give some arguments that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. We prove that there exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(log n), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(log n), and the calculation of this bound is an NP-hard problem. In addition, we give a proof that there exists a type of instances for which known approximation algorithms with polynomial time complexity have an approximation ratio of at least equal to $O(\sqrt{n})$, and known lower bounds have a relative error of at least equal to O(log n). This type of instances corresponds to the single machine parallel-batch scheduling problem 1| p− batch, b=∞| C. [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]

The article looks at the operational use of integer linear programming (ILP) models. It is apparent that ILP has reached a level of maturity that enables live management decision problems to be routinely solved. It notes that it has been achieved by an enormous increase in computing power, major improvements to the ILP solution codes and a greater understanding of the importance of a good formulation, and a finer knowledge of the mathematical structure of some common formulation constructs.

The author offers an overview of the history of the lift-and-project. The first implementation of the lift-and-project cuts was using LINDO. He built a rather rudimentary cutting plane algorithm that worked reasonably well for small problems. He analyzed the relationship of the procedure to the Reformulation and Linearization Technique. The project helped change the mood of the community as it related to the reluctance of using generic integer cuts to solve generic mixed-integer programs.

This paper develops a mathematical model for project time compression problems in CPM/PERT type networks. It is noted this formulation of the problem will be an adequate approximation for solving the time compression problem with any continuous and non-increasing time-cost curve. The kind of this model is Mixed Integer Linear Program (MILP) with zero-one variables, and the Benders' decomposition procedure for analyzing this model has been developed. Then this paper proposes a new approach based on the surrogating method for solving these problems. In addition, the required computer programs have been prepared by the author to execute the algorithm. An illustrative example solved by the new algorithm, and two methods are compared by several numerical examples. Computational experience with these data shows the superiority of the new approach. [ABSTRACT FROM AUTHOR]

Many combinatorial problems can be modeled as 0/1 integer linear programs. Problems expressed in this form are usually solved by Operations Research algorithms, but good results have also been obtained using generalised SAT algorithms based on backtracking or local search, after transformation to pseudo-Boolean form. A third class of SAT algorithm uses non-systematic backtracking to combine constraint propagation with local search-like scalability, at the cost of completeness. This paper describes such an algorithm for pseudo-Boolean models. Experimental results on a variety of problems are encouraging, in some cases yielding improved solutions or performance compared to previous algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present a study of the polytope associated to a classic linear integer programming formulation of the graph coloring problem. We determine some families of facets. This is the initial step for the development of a branch-and-cut algorithm to solve large instances of the graph coloring problem. [ABSTRACT FROM AUTHOR]

In this paper, discrete mathematical programming approaches are used to solve the frequency allocation and cell site selection problem in an integrated setup. Both CDMA (code division multiple access) and FD/TDMA (frequency/time division multiple access) technologies will be important for 3rd generation mobile systems. If all users share the same bandwidth, base transmitter stations should be placed such that a maximum of traffic can be carried at low interference rates. The expected traffic is represented by spatially scattered weighted nodes. The problem to select an optimal set of base station locations from a given pool of configurations is formulated as an integer linear program and solved by combinatorial optimization methods. For systems which employ FD/TDMA schemes, the cell site optimization process depends on the assignment of channels. We suggest an integrated linear programming approach to solve both objectives in a single planning step. Because of the problems' tremendous complexity, special branch-and-bound procedures are developed as exact and approximate solution methods. An examples is given for a typical urban scenario with base transmitters below roof tops. [ABSTRACT FROM AUTHOR]

In this paper, we present an efficient approach for solving capacitated single allocation hub location problems. We use a modified version of a previous mixed integer linear programming formulation developed by us for p-hub median problems. This formulation requires fewer variables and constraints than those traditionally used in the literature. We develop good heuristic algorithms for its solution based on simulated annealing (SA) and random descent (RDH). We use the upper bound to develop an LP-based branch and bound solution method. The problem, as we define it, finds applications in the design of postal delivery networks, particularly in the location of capacitated mail sorting and distribution centres. We test our algorithms on data obtained from this application. To the best of our knowledge, this problem has not been solved in the literature. Computational results are presented indicating the usefulness of our approach. [ABSTRACT FROM AUTHOR]

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem m which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints generalized subtour elimination constraints, and chain baring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations. [ABSTRACT FROM AUTHOR]

In this paper, we discuss modeling with the specific purpose of solving the models with different decomposition techniques. We first briefly describe the basic primal, dual and primal-dual decomposition techniques, where a master problem is constructed by very specific modeling. The main part of the paper contains a discussion of variables and constraint duplication techniques, used to create a structure which can be used in decomposition methods, i.e. enabling decomposition by modeling. We mainly treat linear mixed integer programming problems with several sets of variables and/or constraints. We propose several ways of incorporating variable and/or constraint duplication techniques in cross decomposition. In some cases, the constraints corresponding to the Lagrange multipliers that are needed as input to the Lagrangian relaxation are not present in the primal subproblem. Despite this, we show how to determine these multipliers optimally. In some combinations, the input to a subproblem is not unique, and we discuss how to handle this non-uniqueness in an advantageous way. An application to the capacitated facility location problem is described. [ABSTRACT FROM AUTHOR]

This paper presents a two-stage multi-period decision model for allocation of the individual's savings into several investment plans. Although the U.S. economy is used as the background, the modelling methods are general enough to accommodate any tax law. The first stage of the model uses an asset-allocation method based on the single-index model. Because this method is static and does not provide for tax considerations and other constraints, it alone is not enough. The output of this optimal selection is used as exogenous parameters and controls for the second stage of the model which is an integer program. The IP includes fixed charges, statutory and budgetary constraints, a discount rate, and the risk level. We provide an example of this approach to illustrate how an individual can achieve his goals of terminal accumulations while maintaining the risk level, measured by the aggregate beta, he prefers. A linear programming relaxation of the IP model is utilized for sensitivity analysis to examine whether future adjustments in investment strategies are required. The model remains tractable enough for implementation by individuals who may not be experts in mathematical programming and financial planning. [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 market sharing problem was proposed by M. Dawande and G. Cornuéjols (INFORMS J. Comput. 11, ) to compare the performance of linear integer programming algorithms. Haibo Wang (Manuscript No. 251, Annuals of Operations Research, ) examined some hard instances of these problems and reported the results he obtained with the commercially available program CPLEX. This paper first describes a model, which allows to embed integer programs with inequalities into a lattice and then reports the progress with Wang's instances, by using a lattice based algorithm which employs a new heuristical sieving procedure. These results are compared to recent CPLEX 12.0 benchmarks. [ABSTRACT FROM AUTHOR]

In this paper, we investigate DEA with interval input-output data. First we show various extensions of efficiency and that 25 of them are essential. Second we formulate the efficiency test problems as mixed integer programming problems. We prove that 14 among 25 problems can be reduced to linear programming problems and that the other 11 efficiencies can be tested by solving a finite sequence of linear programming problems. Third, in order to obtain efficiency scores, we extend SBM model to interval input-output data. Fourth, to moderate a possible positive overassessment by DEA, we introduce the inverted DEA model with interval input-output data. Using efficiency and inefficiency scores, we propose a classification of DMUs. Finally, we apply the proposed approach to Japanese Bank Data and demonstrate its advantages. [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]

the end of the seventies, Soyster et al. (Eur. J. Oper. Res. 2:195-201, ) proposed a convergent algorithm that solves a series of small sub-problems generated by exploiting information obtained through a series of linear programming relaxations. This process is suitable for the 0-1 mixed integer programming problems when the number of constraints is relatively smaller when compared to the number of variables. In this paper, we first revisit this algorithm, once again presenting it and some of its properties, including new proofs of finite convergence. This algorithm can, in practice, be used as a heuristic if the number of iterations is limited. We propose some improvements in which dominance properties are emphasized in order to reduce the number of sub problems to be solved optimally. We also add constraints to these sub-problems to speed up the process and integrate adaptive memory. Our results show the efficiency of the proposed improvements for the 0-1 multidimensional knapsack problem. [ABSTRACT FROM AUTHOR]

For many problems in scheduling and timetabling, the choice of a mathematical programming formulation is determined by the formulation of the graph colouring component. This paper briefly surveys seven known integer programming formulations of vertex colouring and introduces a new approach using “supernodes”. In the definition of George and McIntyre (SIAM J. Numer. Anal. 15(1):90–112, ), a “supernode” is a complete subgraph, within which every pair of vertices have the same neighbourhood outside of the subgraph. A polynomial-time algorithm for obtaining the best possible partition of an arbitrary graph into supernodes is given. This makes it possible to use any formulation of vertex multicolouring to encode vertex colouring. Results of empirical tests on benchmark instances in graph colouring (DIMACS) and timetabling (Udine Course Timetabling) are also provided and discussed. [ABSTRACT FROM AUTHOR]

Retail shelf space allocation problem is well known in literature. In this paper, we make three contributions to retail shelf space allocation problem considering space elasticity (SSAPSE). First, we reformulate an existing nonlinear model for SSAPSE to an integer programming (IP) model using piecewise linearization. Second, we show that the linear programming relaxation of the proposed IP model produces tight upper bound. Third, we develop a heuristic that consistently produces near optimal solutions for randomly generated instances of problems with size (products, shelves) varying from (25, 5) to (200, 50) within a minute of CPU time. [ABSTRACT FROM AUTHOR]

In this paper, we present an improved Partial Enumeration Algorithm for Integer Programming Problems by developing a special algorithm, named PE_SPEEDUP (partial enumeration speedup), to use whatever explicit linear constraints are present to speedup the search for a solution. The method is easy to understand and implement, yet very effective in dealing with many integer programming problems, including knapsack problems, reliability optimization, and spare allocation problems. The algorithm is based on monotonicity properties of the problem functions, and uses function values only; it does not require continuity or differentiability of the problem functions. This allows its use on problems whose functions cannot be expressed in closed algebraic form. The reliability and efficiency of the proposed PE_SPEEDUP algorithm has been demonstrated on some integer optimization problems taken from the literature. [ABSTRACT FROM AUTHOR]

In this paper we consider solution methods for multiobjective integer programming (MOIP) problems based on scalarization. We define the MOIP, discuss some common scalarizations, and provide a general formulation that encompasses most scalarizations that have been applied in the MOIP context as special cases. We show that these methods suffer some drawbacks by either only being able to find supported efficient solutions or introducing constraints that can make the computational effort to solve the scalarization prohibitive. We show that Lagrangian duality applied to the general scalarization does not remedy the situation. We also introduce a new scalarization technique, the method of elastic constraints, which is shown to be able to find all efficient solutions and overcome the computational burden of the scalarizations that use constraints on objective values. Finally, we present some results from an application in airline crew scheduling as evidence. [ABSTRACT FROM AUTHOR]

The problem of rerostering service schedules is very common in organizations that work shifts around the clock every day of the year with a set number of employees. Whenever one or more workers announce that they will not be able to attend to tasks previously assigned in their schedule, those tasks must be performed at the expense of alterations in the schedules of other workers. These changes should not conflict with the rules laid down by the administration and employment contracts and should affect the previous schedules as little as possible. This is a difficult real problem calling for a computational tool to cope with it easily. In the paper the issue is described in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. A heuristic was implemented as a first approach to solving the problem. Subsequently the integer linear programming formulation of the multicommodity flow model and two linear relaxations were tested using CPLEX [2] optimizers. The computational results reported regard real instances from a Lisbon state hospital. Satisfactory rosters were obtained within acceptable computational times in all instances tested, either with the integer optimizer, or with the heuristic. This being so, refinements will be undertaken to embed these methodologies in a decision support system that may assist the head nurse in her daily rerostering activities. [ABSTRACT FROM AUTHOR]

The original Markowitz model of portfolio selection has received a widespread theoretical acceptance and it has been the basis for various portfolio selection techniques. Nevertheless, this normative model has found relatively little application in practice when some additional features, such as fixed costs and minimum transaction lots, are relevant in the portfolio selection problem. In this paper different mixed-integer linear programming models dealing with fixed costs and possibly minimum lots are introduced. Due to the high computational complexity of the models, heuristic procedures, based on the construction and optimal solution of mixed integer subproblems, are proposed. Computational results obtained using data from the Milan Stock Exchange show how the proposed heuristics yield very good solutions in a short computational time and make possible some interesting financial conclusions on the impact of fixed costs and minimum lots on portfolio composition. [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]

This paper represents an integration of Mixed Integer Programming (MIP) and Constraint Logic Programming (CLP) which, like MIP, tightens bounds rather than adding constraints during search. The integrated system combines components of the CLP system ECLiPSe [7] and the MIP system CPLEX [5], in which constraints can be handled by either one or both components. Our approach is introduced in three stages. Firstly, we present an automatic transformation which maps CLP programs onto such CLP programs that any disjunction is eliminated in favour of auxiliary binary variables. Secondly, we present improvements of this mapping by using a committed choice operator and translations of pre-defined nonlinear constraints. Thirdly, we introduce a new hybrid algorithm which reduces the solution space of the problem progressively by calling finite domain propagation of ECLiPSe as well as dual simplex of CPLEX. The advantages of this integration are illustrated by efficiently solving difficult optimisation problems like the Hoist Scheduling Problem [23] and the Progressive Party Problem [27]. [ABSTRACT FROM AUTHOR]

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem m which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints generalized subtour elimination constraints, and chain baring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations [ABSTRACT FROM AUTHOR]