Hybrid approaches for the two‐scenario max–min knapsack problem

In this paper, we deal with the two‐scenario max–min knapsack (MNK) problem. First, we consider several formulations of MNK as a mixed integer programming problem. Then, we propose a hybrid method as an alternative to solve the MNK exactly. The approach combines relaxation technique and the temporary setting of variables to improve iteratively two sequences of upper and lower bounds. More precisely, pseudo‐cuts are added to the problem to strengthen the bounds and reduce the gap between the best lower bound and the best upper bound. The algorithm stops when the proof of the optimality of the best solution is found. We also use a reduction technique to set some variables definitively at their optimal values. Numerical experiments demonstrate the robustness of the approach. In particular, our algorithm is efficient to solve large and correlated instances of MNK.     

A continuous analysis framework for the solution of location–allocation problems with dense demand

Location–allocation problems arise in several contexts, including supply chain and data mining. In its most common interpretation, the basic problem consists of optimally locating facilities and allocating customers to facilities so as to minimize the total cost. The standard approach to solving location–allocation problems is to model alternative location sites and customers as discrete entities. Many problem instances in practice involve dense demand data and uncertainties about the cost and locations of the potential sites. The use of discrete models is often inappropriate in such cases. This paper presents an alternative methodology where the market demand is modeled as a continuous density function and the resulting formulation is solved by means of calculus techniques. The methodology prioritizes the allocation decisions rather than location decisions, which is the common practice in the location literature. The solution algorithm proposed in this framework is a local search heuristic (steepest-descent algorithm) and is applicable to problems where the allocation decisions are in the form of polygons, e.g., with Euclidean distances. Extensive computational experiments confirm the efficiency of the proposed methodology.     

Parallel matheuristics for the discrete unit commitment problem with min‐stop ramping constraints

The discrete unit commitment problem with min‐stop ramping constraints optimizes the daily production of thermal power plants, subject to an operational reactivity of thermal units in a 30‐minute delay. Previously, mixed integer programming (MIP) formulations aimed at an exact optimization approach. This paper derives matheuristics to face the short time limit imposed by the operational constraints. Continuous relaxations guide the search for feasible solutions exploiting tailored variable fixing strategies. Parallel matheuristics are derived considering complementary strategies in parallel. Tests were performed on more than 600 real‐life instances. Our parallel matheuristic provides high‐quality solutions and outperforms the MIP approach in the time limits imposed by the industrial application. This paper illustrates a special interest for matheuristics in industrial highly constrained problems: many tailored neighborhood searches can be derived from an MIP formulation, and their combination in a parallel scheme improves the solution quality as well as the consistency of the heuristic.     

不确定条件下应急资源布局的鲁棒双层优化模型

针对非常规突发事件中应急资源布局问题,在受灾点需求不确定和应急救援过程分为多个阶段的情景下,建立了省市两级应急储备仓库定位和物资配置的鲁棒双层规划模型。运用相对鲁棒优化方法,将上述具有不确定性系数的双层规划模型转化为从者无关联的确定性线性双层规划,提出了一种混合遗传算法进行求解,实现了省市两级应急资源布局的协同优化。通过实例验证了模型及算法的可行性和有效性。     

基于混合逻辑动态模型的混杂系统预测控制

针对过程工业控制对象的混杂特性，采用基于混合逻辑动态模型的预测控制策略。给出混杂系统的建模方法，并对其稳定性进行分析。仿真结果表明基于混合逻辑动态模型的预测控制能使混杂系统跟踪设定值并满足操作约束，为研究新一代复杂工业控制系统提供了新的思路。     

Sensor allocation with guaranteed exponential stability for linear multi‐rate sampled‐data systems

This paper addresses sensor allocation with guaranteed exponential stability for linear multi‐rate sampled‐data systems. It is assumed that a continuous‐time linear plant is exponentially stabilized by a continuous‐time linear controller. Given sensors with incommensurate sampling rates, the objective is to allocate each state to a sensor such that the resulting multi‐rate sampled‐data system remains exponentially stable. The main contributions of this paper are twofold. First, we propose sufficient Krasovskii‐based conditions to partition the state vector among sensors such that exponential stability of the closed‐loop system is guaranteed. Second, the problem of finding a partition that guarantees exponential stability is cast as a mixed integer program subject to linear matrix inequalities. The theoretical results are successfully applied to two robotic problems: path‐following in unicycles and hovering in quadrotors. Copyright © 2015 John Wiley & Sons, Ltd.     

An integer program and a hybrid genetic algorithm for the university timetabling problem

The university timetabling problem (UTP) has been studied by numerous research groups for decades. In addition to addressing hard and soft constraints, we extend the UTP by considering consecutiveness and periodicity constraints of multi-session lectures, which are common in many eastern Asian universities. Because schedulers can decide the consecutiveness and periodicity constraints for the multi-session lectures within a limited ratio, we consider these novel decision variables in our model. We develop a mixed integer linear program for the UTP. For the analysis, we convert the UTP into the three-dimensional container packing problem (3DCPP) and create a hybrid genetic algorithm (HGA), which has been shown to be efficient in solving the 3DCPP. We also develop a tabu search algorithm based on the existing UTP literature and compare the findings with that of our HGA. The results show that our HGA obtains a better solution than the tabu search algorithm in a reasonable amount of time.     

Model and algorithm for bilevel multisized terminal location‐routing problem for the last mile delivery

The last mile delivery is regarded as one of the most expensive but least efficient stretches in the business‐to‐customer supply chain. Designing the last mile delivery system in a lean way is crucial to serve customers efficiently and economically. To address this issue, we propose a bilevel multisized terminal location‐routing problem (BL‐MSTLRP) with simultaneous home delivery and customer's pickup services. The solution method is proposed by combining genetic algorithm (GA) and simulated annealing (SA), called self‐adaptive SGA. Studies for designing the last mile delivery system in a real‐world environment indicate the validity of the proposed model based on the comparison of different scenarios. Numerical experiments are also conducted to evaluate the performance of the presented SGA. Computational results show that the hybrid approach efficiently solves the BL‐MSTLRP.     

有配送能力限制的易腐农产品配送中心选址方法

为提高物流管理绩效,考虑到农产品的易腐败特征和配送中心的配送能力限制,建立了易腐农产品配送中心选址问题的0-1整数非线性规划模型。利用该模型可以确定配送中心的开设位置、各配送中心与用户之间的配送关系,以及配送途中的农产品损耗量。为求解该模型,提出了嵌入改进表上作业法的混合遗传算法,给出了算法的实现步骤。最后通过算例,验证了模型和算法的有效性。     

基于剩余装载能力的蚁群算法求解同时送取货车辆路径问题

建立了带车辆最大行程约束的同时送取货车辆路径问题的混合整数规划模型; 采用了基于排序的蚂蚁系统和最大最小蚂蚁系统的信息素更新策略; 设计了基于车辆剩余装载能力的启发信息策略, 可在满足车辆负载的限制下, 提高车辆的负载利用率; 并在改进阶段使用了节点交换的局部搜索策略,以提高算法收敛速度. 仿真结果表明本文算法能够在可接受的计算时间内得到满意解.     

模糊环境下多周期多决策生鲜闭环物流网络

针对生鲜品因易腐易损性而产生的高频次物流配送及不确定需求与退货量的问题，提出了模糊环境下多周期生鲜闭环物流网络系统，以实现最小系统成本、最优设施选址与最佳配送路径的多决策安排。为求解系统对应的模糊混合整数线性规划（FMILP）模型，首先将生鲜需求量和退货量设定为三角模糊值，其次运用模糊机会约束规划方法将模糊约束等价变换为清晰式，最后利用遗传算法（GA）和粒子群优化（PSO）算法搜索案例的最优解。实验结果表明，多周期闭环系统比单周期更能兼顾多决策规划，同时三角模糊量的置信水平变化对企业最优运作有着显著影响，进而为相关决策者提供借鉴。     

Improved dynamic programming and approximation results for the knapsack problem with setups

In this paper, we consider the 0–1 knapsack problem with setups. Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm that performs much better than a previous dynamic program and turns out to be also a valid alternative to an exact approach based on the use of an Integer Linear Programming (ILP) solver. Then we present a general inapproximability result. Furthermore, we investigate several relevant special cases that still permit fully polynomial‐time approximation schemes and others where the problem remains hard to approximate.     

Utility max–min fair resource allocation for communication networks with multipath routing

This paper considers the flow control and resource allocation problem as applied to the generic multipath communication networks with heterogeneous applications. We propose a novel distributed algorithm, show and prove that among all the sources with positive increasing and bounded utilities (no need to be concave) in steady state, the utility max–min fairness is achieved, which is essential for balancing Quality of Service (QoS) for different applications. By combining the first order Lagrangian method and filtering mechanism, the adopted approach eliminates typical oscillation behavior in multipath networks and possesses a rapid convergence property. In addition, the algorithm is capable of deciding the optimal routing strategy and distributing the total traffic evenly out of the available paths. The performance of our utility max–min fair flow control algorithm is evaluated through simulations under two representative case studies, as well as the real implementation issues are addressed deliberately for the practical purpose.     

Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes

Membrane systems are biologically motivated theoretical models of distributed and parallel computing. In this paper, we present a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem.     

Task allocation and trajectory planning for multiple agents in the presence of obstacle and connectivity constraints with mixed‐integer linear programming

This article addresses the problem of maneuvering multiple agents that must visit a number of target sets, while enforcing connectivity constraints and avoiding obstacle as well as interagent collisions. The tool to cope with the problem is a formulation of model predictive control including binary decision variables. In this regard, two mixed‐integer linear programming formulations are presented, considering a trade‐off between optimality and scalability between them. Simulation results are also shown to illustrate the main features of the proposed approaches.     

Energy‐efficient task allocation with quality of service provisioning for concurrent applications in multi‐functional wireless sensor network systems

Multi‐functional wireless sensor network (WSN) system is a new design trend of WSNs, which are evolving from dedicated application‐specific systems to an integrated infrastructure that supports the execution of multiple concurrent applications. Such system offers inherent advantages in terms of cost and flexibility because it allows the effective utilization of available sensors and resource sharing among multiple applications. However, sensor nodes are very constrained in resources, mainly regarding their energy. Therefore, the usage of such resources needs to be carefully managed, and the sharing with several applications imposes new challenges in achieving energy efficiency in these networks. In order to exploit the full potential of multi‐functional WSN systems, it is crucial to design mechanisms that effectively allocate tasks onto sensors so that the entire system lifetime is maximized while meeting various application requirements. However, it is likely that the requirements of different applications cannot be simultaneously met. In this paper, we present the Multi‐Application Requirements Aware and Energy Efficiency algorithm as a new resource allocation heuristic for multi‐functional WSN system to maximize system lifetime subject to various application requirements. The heuristic effectively deals with different quality of service parameters (possibly conflicting) trading those parameters and exploiting heterogeneity of multiple WSNs. Copyright © 2013 John Wiley & Sons, Ltd.     

Multiobjective model for solving resource‐leveling problem with discounted cash flows

Nowadays, executers are struggling to improve the economic and scheduling situation of projects. Construction scheduling techniques often produce schedules that cause undesirable resource fluctuations that are inefficient and costly to implement on site. The objective of the resource‐leveling problem is to reduce resource fluctuation related costs (hiring and firing costs) without violating the project deadline. In this article, minimizing the discounted costs of resource fluctuations and minimizing the project makespan are considered in a multiobjective model. The problem is formulated as an integer nonlinear programming model, and since the optimization problem is NP‐hard, we propose multiobjective evolutionary algorithms, namely nondominated sorting genetic algorithm‐II (NSGA‐II), strength Pareto evolutionary algorithm‐II (SPEA‐II), and multiobjective particle swarm optimization (MOPSO) to solve our suggested model. To evaluate the performance of the algorithms, experimental performance analysis on various instances is presented. Furthermore, in order to study the performance of these algorithms, three criteria are proposed and compared with each other to demonstrate the strengths of each applied algorithm. To validate the results obtained for the suggested model, we compared the results of the first objective function with a well‐tuned genetic algorithm and differential algorithm, and we also compared the makespan results with one of the popular algorithms for the resource constraints project scheduling problem. Finally, we can observe that the NSGA‐II algorithm presents better solutions than the other two algorithms on average.     

Bounded consensus tracking for sampled‐data second‐order multi‐agent systems with fixed and Markovian switching topology

This paper studies the bounded consensus tracking problems of second‐order multi‐agent systems with fixed and Markovian switching topology in a sampling setting. It is assumed that all the agents can only obtain the approximative value of the leader's acceleration instead of the actual value. Moreover, only a portion of agents can have the access to the leader and obtain the leader's position and velocity directly. By virtue of matrix analysis and perturbation theory, we present necessary and sufficient conditions for boundedness of tracking error system and show the ultimate bound of tracking errors under fixed and Markovian switching topology, respectively. Finally, a simulation example is given to illustrate the effectiveness of the results. Copyright © 2013 John Wiley & Sons, Ltd.     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.     

Global maximum principle for the forward–backward stochastic optimal control problem with poisson jumps

This paper is concerned with the forward–backward stochastic optimal control problem with Poisson jumps. A necessary condition of optimality in the form of a global maximum principle as well as a sufficient condition of optimality are presented under the assumption that the diffusion and jump coefficients do not contain the control variable, and the control domain need not be convex. The case where there are some state constraints is also discussed. A financial example is discussed to illustrate the application of our result. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society