多周期多种设备公用工程系统优化模型的改进及应用

本文提出了多周期多种设备公用工程系统改进的混合整数双线性优化模型,它含有两种优化变量和系统运行过程的离散动态约束,期望系统总设备投资(含设备折旧)与全周期运行操作费用之和最小。针对改进优化模型求解上的困难,给出将改进优化模型分解成有限多个关于连续变量的线性规划。论述了改进优化模型与分解模型的等价性以及两种模型的主要数学性质,并在此基础上提出了求解策略。最后将改进优化模型应用于某石化企业的蒸汽动力系统最优设计与运行优化集成实例。     

Fleet assignment and routing with schedule synchronization constraints

This paper introduces a new type of constraints, related to schedule synchronization, in the problem formulation of aircraft fleet assignment and routing problems and it proposes an optimal solution approach. This approach is based on Dantzig–Wolfe decomposition/column generation. The resulting master problem consists of flight covering constraints, as in usual applications, and of schedule synchronization constraints. The corresponding subproblem is a shortest path problem with time windows and linear costs on the time variables and it is solved by an optimal dynamic programming algorithm. This column generation procedure is embedded into a branch and bound scheme to obtain integer solutions. A dedicated branching scheme was devised in this paper where the branching decisions are imposed on the time variables. Computational experiments were conducted using weekly fleet routing and scheduling problem data coming from an European airline. The test problems are solved to optimality. A detailed result analysis highlights the advantages of this approach: an extremely short subproblem solution time and, after several improvements, a very efficient master problem solution time.     

Parallel distributed block coordinate descent methods based on pairwise comparison oracle

The aim of this paper is to find the global solutions of uncertain optimization problems having a quadratic objective function and quadratic inequality constraints. The bounded epistemic uncertainties in the constraint coefficients are represented using either universal or existential quantified parameters and interval parameter domains. This approach allows to model non-controlled uncertainties by using universally quantified parameters and controlled uncertainties by using existentially quantified ones. While existentially quantified parameters could be equivalently considered as additional variables, keeping them as parameters allows maintaining the quadratic problem structure, which is essential for the proposed algorithm. The branch and bound algorithm presented in the paper handles both universally and existentially quantified parameters in a homogeneous way, without branching on their domains, and uses some dedicated numerical constraint programming techniques for finding a robust, global solution. Several examples clarify the theoretical parts and the tests demonstrate the usefulness of the proposed method.     

SICOpt: Solution Approach for Nonlinear Integer Stochastic Programming Problems

We propose a novel solution approach for the class of two-stage nonlinear integer stochastic programming models. These problems are characterized by large scale dimensions, as the number of constraints and variables depend on the number of realizations (scenarios) used to capture the underlying distributions of the random data. In addition, the integrality constraints on the decision variables make the solution process even much more difficult preventing the application of general purpose solvers. The proposed solution approach integrates the branch-and-bound framework with the interior point method. The main advantage of this choice is the effective exploitation of the specific structure exhibited by the different subproblems at each node of the search tree. A specifically designed warm start procedure and an early branching technique improve the overall efficiency. Our contribution is well founded from a theoretical point of view and is characterized by good computational efficiency, without any loss in terms of effectiveness. Some preliminary numerical results, obtained by solving a challenging real-life problem, prove the robustness and the efficiency of the proposed approach.     

Active-constraint variable ordering for faster feasibility of mixed integer linear programs

The selection of the branching variable can greatly affect the speed of the branch and bound solution of a mixed-integer or integer linear program. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We present a new approach that relies on estimating the impact of the candidate variables on the active constraints in the current LP relaxation. We apply this method to the problem of finding the first feasible solution as quickly as possible. Empirical experiments demonstrate a significant improvement compared to a state-of-the art commercial MIP solver.     

Cost optimal allocation of rail passenger lines

We consider the problem of cost optimal railway line allocation for passenger trains for the Dutch railway system. At present, the allocation of passenger lines by Dutch Railways is based on maximizing the number of direct travelers. This paper develops an alternative approach that takes operating costs into account. A mathematical programming model is developed which minimizes the operating costs subject to service constraints and capacity requirements. The model optimizes on lines, line types, routes, frequencies and train lengths. First, the line allocation model is formulated as an integer nonlinear programming model. This model is transformed into an integer linear programming model with binary decision variables. An algorithm is presented which solves the problem to optimality. The algorithm is based upon constraint satisfaction and a Branch and Bound procedure. The algorithm is applied to a subnetwork of the Dutch railway system for which it shows a substantial cost reduction. Further application and extension seem promising.     

Discrete time model and algorithms for container yard crane scheduling

Container terminal (CT) operations are often bottlenecked by slow YC (yard crane) movements. PM (prime mover) queues in front of the YCs are common. Hence, efficient YC scheduling to reduce the PM waiting time is critical in increasing a CT’s throughput. We develop an efficient model for YC scheduling by taking into account realistic operational constraints such as inter-crane interference, fixed YC separation distances and simultaneous container storage/retrievals. Among them, only inter-crane interference has ever been considered in the literature. The model requires far fewer integer variables than the literature by using bi-index decision variables. We show how the model can be solved quickly using heuristics and rolling-horizon algorithm, yielding close to optimal solutions in seconds. The solution quality and solution time are both better than the literature even with additional constraints considered. The proposed formulations and algorithms can be extended to other problems with time windows and space constraints.     

带能力限制的混合形专用线非直达车流取送问题优化

针对铁路枢纽地方货物流小运转作业系统,研究一类带能力限制的混合形专用线非直达车流取送优化问题。以在站停留车小时费用和调机取送成本之和最小化为目标,考虑装卸站装卸能力、调机牵引能力、瓶颈区段能力、调机日走行时长等能力限制条件,构建问题模型。鉴于模型直接求解较为困难且效率低下,故设计三阶段综合优化策略。该策略首先利用基于作业编码、顺序调整与批次划分的TPA过程完成初始取送作业方案生成,进而基于迭代寻优思路设计FPUA更新过程完成取送作业方案的优化,最后考虑批次时间窗、空闲原则与调机走行利用EAA过程完成调机分配。设计实验场景,对所提出的方法进行过程验证,并设计不同规模问题,对算法进行测试对比与性能评估。     

A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality

Production lot sizing models are often used to decide the best lot size to minimize operation cost, inventory cost, and setup cost. Cellular manufacturing analyses mainly address how machines should be grouped and parts be produced. In this paper, a mathematical programming model is developed following an integrated approach for cell configuration and lot sizing in a dynamic manufacturing environment. The model development also considers the impact of lot sizes on product quality. Solution of the mathematical model is to minimize both production and quality related costs. The proposed model, with nonlinear terms and integer variables, cannot be solved for real size problems efficiently due to its NP-complexity. To solve the model for practical purposes, a linear programming embedded genetic algorithm was developed. The algorithm searches over the integer variables and for each integer solution visited the corresponding values of the continuous variables are determined by solving a linear programming subproblem using the simplex algorithm. Numerical examples showed that the proposed method is efficient and effective in searching for near optimal solutions.     

On Compact Formulations for Integer Programs Solved by Column Generation

Column generation has become a powerful tool in solving large scale integer programs. It is well known that most of the often reported compatibility issues between pricing subproblem and branching rule disappear when branching decisions are based on imposing constraints on the subproblem's variables. This can be generalized to branching on variables of a so-called compact formulation. We constructively show that such a formulation always exists under mild assumptions. It has a block diagonal structure with identical subproblems, each of which contributes only one column in an integer solution. This construction has an interpretation as reversing a Dantzig-Wolfe decomposition. Our proposal opens the way for the development of branching rules adapted to the subproblem's structure and to the linking constraints.     

Symbolic integration of logic in MILP branch and bound methods for the synthesis of process networks

This paper deals with the branch and bound solution of process synthesis problems that are modelled as mixed-integer linear programming (MILP) problems. The symbolic integration of logic relations between potential units in a process network is proposed in the LP based branch and bound method to expedite the search for the optimal solution. The objective of this integration is to reduce the number of nodes that must be enumerated by using the logic to decide on the branching of variables and to determine by symbolic inference whether additional variables can be fixed at each node. The important feature of this approach is that it does not require additional constraints in the MILP and the logic can be systematically generated for process networks. Strategies for performing the integration are proposed that use the disjunctive and conjunctive normal form representations of the logic, respectively. Computational results will be presented to illustrate that substantial savings can be achieved.     

Branch-and-cut for linear programs with overlapping SOS1 constraints

SOS1 constraints require that at most one of a given set of variables is nonzero. In this article, we investigate a branch-and-cut algorithm to solve linear programs with SOS1 constraints. We focus on the case in which the SOS1 constraints overlap. The corresponding conflict graph can algorithmically be exploited, for instance, for improved branching rules, preprocessing, primal heuristics, and cutting planes. In an extensive computational study, we evaluate the components of our implementation on instances for three different applications. We also demonstrate the effectiveness of this approach by comparing it to the solution of a mixed-integer programming formulation, if the variables appearing in SOS1 constraints ar bounded.     

BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0–1 problems

We present an exact algorithmic framework, so-called BFC-MSMIP, for optimizing multistage stochastic mixed 0–1 problems with complete recourse. The uncertainty is represented by using a scenario tree and lies anywhere in the model. The problem is modeled by a splitting variable representation of the Deterministic Equivalent Model of the stochastic problem, where the 0–1 variables and the continuous variables appear at any stage. The approach uses the Twin Node Family concept within the algorithmic framework, so-called Branch-and-Fix Coordination, for satisfying the nonanticipativity constraints in the 0–1 variables. Some blocks of additional strategies are used in order to show the performance of the proposed approach. The blocks are related to the scenario clustering, the starting branching and the branching order strategies, among others. Some computational experience is reported. It shows that the new approach obtains the optimal solution in all instances under consideration.      

Integrated supply chain planning under uncertainty using an improved stochastic approach

This paper proposes an integrated model and a modified solution method for solving supply chain network design problems under uncertainty. The stochastic supply chain network design model is provided as a two-stage stochastic program where the two stages in the decision-making process correspond to the strategic and tactical decisions. The uncertainties are mostly found in the tactical stage because most tactical parameters are not fully known when the strategic decisions have to be made. The main uncertain parameters are the operational costs, the customer demand and capacity of the facilities. In the improved solution method, the sample average approximation technique is integrated with the accelerated Benders’ decomposition approach to improvement of the mixed integer linear programming solution phase. The surrogate constraints method will be utilized to acceleration of the decomposition algorithm. A computational study on randomly generated data sets is presented to highlight the efficiency of the proposed solution method. The computational results show that the modified sample average approximation method effectively expedites the computational procedure in comparison with the original approach.     

An evolutionary programming approach to mixed-variable optimization problems

Many engineering optimization problems frequently encounter discrete variables as well as continuous variables and the presence of nonlinear discrete variables considerably adds to the solution complexity. Very few of the existing methods can find a globally optimal solution when the objective functions are non-convex and non-differentiable. In this paper, we present a mixed-variable evolutionary programming (MVEP) technique for solving these nonlinear optimization problems which contain integer, discrete, zero-one and continuous variables. The MVEP provides an improvement in global search reliability in a mixed-variable space and converges steadily to a good solution. An approach to handle various kinds of variables and constraints is discussed. Some examples of mixed-variable optimization problems in the literature are tested, which demonstrate that the proposed approach is superior to current methods for finding the best solution, in terms of both solution quality and algorithm robustness.     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.     

Bounding,filtering and diversification in CP-based local branching

Local branching is a general purpose heuristic method which searches locally around the best known solution by employing tree search. It has been successfully used in Mixed-Integer Programming where local branching constraints are used to model the neighborhood of an incumbent solution and improve the bound. We propose the integration of local branching in Constraint Programming (CP). This integration is not simply a matter of implementation, but requires a number of significant extensions. The original contributions of this paper are: the definition of an efficient and incremental bound computation for the neighborhood, a cost-based filtering algorithm for the local branching constraint and a novel diversification strategy that can explore arbitrarily far regions of the search tree w.r.t. the already found solutions. We demonstrate the practical value of local branching in CP by providing an extensive experimental evaluation on the hard instances of the Asymmetric Traveling Salesman Problem with Time Windows.     

Solving continuous min max problem for single period portfolio selection with discrete constraints by DCA

In this article, we consider the application of a continuous min–max model with cardinality constraints to worst-case portfolio selection with multiple scenarios of risk, where the return forecast of each asset belongs to an interval. The problem can be formulated as minimizing a convex function under mixed integer variables with additional complementarity constraints. We first prove that the complementarity constraints can be eliminated and then use Difference of Convex functions (DC) programming and DC Algorithm (DCA), an innovative approach in non-convex programming frameworks, to solve the resulting problem. We reformulate it as a DC program and then show how to apply DCA to solve it. Numerical experiments on several test problems are reported that demonstrate the accuracy of the proposed algorithm.     

The Express heuristic for probabilistically constrained integer problems

Integer problems under joint probabilistic constraints with random coefficients in both sides of the constraints are extremely hard from a computational standpoint since two different sources of complexity are merged. The first one is related to the challenging presence of probabilistic constraints which assure the satisfaction of the stochastic constraints with a given probability, whereas the second one is due to the integer nature of the decision variables. In this paper we present a tailored heuristic approach based on alternating phases of exploration and feasibility repairing which we call Express (Explore and Repair Stochastic Solution) heuristic. The exploration is carried out by the iterative solution of simplified reduced integer problems in which probabilistic constraints are discarded and deterministic additional constraints are adjoined. Feasibility is restored through a penalty approach. Computational results, collected on a probabilistically constrained version of the classical 0–1 multiknapsack problem, show that the proposed heuristic is able to determine good quality solutions in a limited amount of time.