mixed integer programming is inherently involved in solving a significant number of practical problems. This paper focuses on mixed integer programming, where the objective function is the summation of N functions, an...
详细信息
mixed integer programming is inherently involved in solving a significant number of practical problems. This paper focuses on mixed integer programming, where the objective function is the summation of N functions, and the constraints include both scalar coupling and set constraints. Given the potentially large scale of these problems, the goal of this work is to propose a distributed method to solve large-scale problems more efficiently. The right-hand side allocation decomposition approach is employed to address the large-scale mixed integer programming problem. Algorithms are then proposed for solving these problems,based on the analysis of the continuity, differentiability, and local convexity properties of the decomposed subproblems. Simulation experiments with randomly generated coefficients demonstrate the superior performance of the proposed algorithms compared to the Gurobi solver, offering higher solution accuracy and faster processing time for large-scale mixed integer programming problems with nonlinear objective and constraint functions.
This paper presents a linearized polynomial mixed-integerprogramming model (PMIPM) for the integration of process planning and scheduling problem. First, the integration problem is modeled as a PMIPM in which some of...
详细信息
This paper presents a linearized polynomial mixed-integerprogramming model (PMIPM) for the integration of process planning and scheduling problem. First, the integration problem is modeled as a PMIPM in which some of the terms are of products of up to three variables, of both binary and continuous in nature. Then, an equivalent linearized model is derived from the polynomial model by applying certain linearization techniques. Although the linearized models have more variables and constraints than their polynomial counterparts, they are potentially solvable to the optimum in comparison to their equivalent polynomial models. Experiments show that the linearized model possesses certain characteristics that are absent from other models in the literature, and provides a fundamental framework for further research in this area.
Several mixed integer programming approaches to the multiple-group statistical classification problem are examined. Many papers have investigated conditions under which a degenerate solution occurs in linear programmi...
详细信息
Several mixed integer programming approaches to the multiple-group statistical classification problem are examined. Many papers have investigated conditions under which a degenerate solution occurs in linear programming approaches to the two-group discriminant problem. Very little research has been conducted in the multiple-group case. We investigate conditions under which a degenerate solution can occur in mixed integer programming approaches to the multiple-group classification problem. A multiple-group 'minimize the sum of deviations' model is presented. This model is similar in structure to the general single function classification model. Also, a two-goal approach to the multiple-group classification problem is discussed.
The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods. To advance techniques of solving this class of problems, t...
详细信息
The capacitated multi-level lot sizing problem is to schedule a number of different items with a bill-of-materials structure over a horizon of finite periods. To advance techniques of solving this class of problems, this paper proposes a new mixed integer programming formulation. Theoretical proofs and computational tests are provided to show that this formulation is able to provide better linear programming relaxation lower bounds than a previously-proposed strong mixed integer programming formulation. Based on the new strong formulation, a progressively stochastic search approach is proposed for solving the problem. Computational results showed that the approach generates high quality solutions, especially for problems of large sizes.
We have developed a methodology for allocating operating room capacity to specialties. Our methodology consists of a finite-horizon mixed integer programming (MIP) model which determines a weekly operating room alloca...
详细信息
We have developed a methodology for allocating operating room capacity to specialties. Our methodology consists of a finite-horizon mixed integer programming (MIP) model which determines a weekly operating room allocation template that minimizes inpatients' cost measured as their length of stay. A number of patient type priority (eg emergency over non-emergency patient) and clinical constraints (eg maximum number of hours allocated to each specialty, surgeon, and staff availability) are included in the formulation. The optimal solution from the analytical model is inputted into a simulation model that captures some of the randomness of the processes (eg surgery time, demand, arrival time, and no-show rate of the outpatients) and non-linearities (eg the MIP assumes proportional allocation of demand satisfaction (output) with room allocation (input)). The simulation model outputs the average length of stay for each specialty and the room utilization. On a case example of a Los Angeles County Hospital, we show how the hospital length of stay pertaining to surgery can be reduced.
A parallel implementation of a disjunctive cutting-plane algorithm in a distributed memory environment is described. Guided by a selection of difficult instances from MIPLIB and real instances obtained from brain-tumo...
详细信息
A parallel implementation of a disjunctive cutting-plane algorithm in a distributed memory environment is described. Guided by a selection of difficult instances from MIPLIB and real instances obtained from brain-tumor research, various strategies of cut synchronization are considered, and their influence on speedup, communication overhead, load balance, and effectiveness in closing the integrality gap are studied. The parallel cutting-plane algorithm is coupled with an LP-based heuristic to assist in returning a good quality integer feasible solution upon termination of the parallel process. The parallel implementation is sufficiently coarse-grained to yield an average of less than 6% of the total time performing tasks associated with communication overhead, and it provides reasonable speedup when executing in parallel. Noticeable differences in load-balance scores are observed, depending on the number of processors used, the synchronization scheme used, and the structure of the MIP problem instance. Nevertheless, the synergism of the combined collection of cuts generated locally on each processor is effective in closing the integrality gap in all cases, and there is minimal variability in the amount of the gap closed as the number of processors varies. In particular, the degree of decentralization, as governed by the synchronization schemes, has little effect on the overall quality of the cuts generated.
Many real problems with uncertain parameters can be modeled as two-stage robust mixed integer programming problems (RMIPs). Due to the complex nature of this kind of problems, this paper focuses on the two-stage RMIPs...
详细信息
Many real problems with uncertain parameters can be modeled as two-stage robust mixed integer programming problems (RMIPs). Due to the complex nature of this kind of problems, this paper focuses on the two-stage RMIPs with objective uncertainty. Based on the results that the augmented Lagrangian is a strong dual for integerprogramming Boland and Eberhard (Math Program 150(2):491-509, 2015), we present the upper and lower bounds. In a special case, we show that the two-stage RMIPs can be equivalently reformulated as a solvable minimax problem.
This paper describes an approach for scheduling a nuclear reactor that irradiates samples as required by customers. The environment involves a flowshop that consists of two stations, each composed of a set of parallel...
详细信息
This paper describes an approach for scheduling a nuclear reactor that irradiates samples as required by customers. The environment involves a flowshop that consists of two stations, each composed of a set of parallel machines. Some jobs may be preempted, while others may not. Some jobs have deadlines, while others have due-dates. Some jobs require special tooling, while others do not. The problem is modeled as a time-indexed, mixedinteger program with the objective of minimizing weighted tardiness. Pre-processing eliminates unnecessary variables and five solution strategies - four optimizing and one heuristic - are devised to utilize the options provided by a commercial solver. The strategies are compared on a set of 25 ten-job test instances. Jobs were selected randomly from a database of 103 actual jobs. One particular optimizing strategy worked especially well - it optimized 80% of the test problems within a predetermined time limit and did so with an average run-time of less than 1 min. (C) 2001 Elsevier Science Ltd. All rights reserved.
This paper proposes a deterministic two-phase mixed integer programming (TPMIP) approach to solve the non-convex economic dispatch (ED) problem considering ramp rate constraints, valve-point effect (VPE), prohibited o...
详细信息
This paper proposes a deterministic two-phase mixed integer programming (TPMIP) approach to solve the non-convex economic dispatch (ED) problem considering ramp rate constraints, valve-point effect (VPE), prohibited operating zones (POZs), transmission loss, and spinning reserve constraints. In the first phase, the non-smooth cost function induced by VPE is piecewise linearized and the POZs constraints are formulated as a set of mathematical formulas via a mixedinteger encoding technique. Then, the non-convex ED problem is converted to a mixed integer programming (MIP) problem and can be solved by commercial optimization solvers. In the second phase, based on the solution obtained in the first phase, the range of the power output of each unit is compressed and then solve the MIP problem again to make a further exploitation for an optimal solution in the subspace of the whole solution domain. To demonstrate the effectiveness of TPMIP, it is applied to eight test systems and the simulation results are compared with those obtained by the existing methods cited in this paper. Numerical simulations have verified that the proposed method provides a comprehensive framework in solving the non-convex ED problem. (C) 2016 Elsevier B.V. All rights reserved.
This paper deals with the cyclic robotic flowshop scheduling problem with time window constraints, where parts are processed successively on multiple machines with upper and lower bounds on processing times and the tr...
详细信息
This paper deals with the cyclic robotic flowshop scheduling problem with time window constraints, where parts are processed successively on multiple machines with upper and lower bounds on processing times and the transportation of parts among the machines is executed by a robot. in contrast with most previous studies, we consider the multi-cyclic scheduling problem in which two or more identical parts enter and leave the robotic flowshop during each cycle. We present the first mixed integer programming (MIP) model for the multi-cyclic robotic flowshop scheduling problem based on the description and analysis of the problem. We solve the model using commercial software CPLEX. Computational experiment on benchmark and randomly generated instances indicates that the proposed MIP approach can effectively solve real-life scheduling problems. (C) 2011 Elsevier Inc. All rights reserved.
暂无评论