A column generation approach to the heterogeneous fleet vehicle routing problem

We consider a vehicle routing problem with a heterogeneous fleet of vehicles having various capacities, fixed costs and variable costs. An approach based on column generation (CG) is applied for its solution, hitherto successful only in the vehicle routing problem with time windows. A tight integer programming model is presented, the linear programming relaxation of which is solved by the CG technique. A couple of dynamic programming schemes developed for the classical vehicle routing problem are emulated with some modifications to efficiently generate feasible columns. With the tight lower bounds thereby obtained, the branch-and-bound procedure is activated to obtain an integer solution. Computational experience with the benchmark test instances confirms that our approach outperforms all the existing algorithms both in terms of the quality of solutions generated and the solution time.     

A method for decomposing mixed-integer linear programs with staircase structure

An algorithm is presented for solving mixed-integer linear programs with a staircase structure. The basic idea of the algorithm is to decompose the original problem into a series form of small-scale mixed-integer problems. For each problem decomposed, the solution is obtained by the conventional branch-and-bound method. In this algorithm the feasibility of the solution is always assured, but in order to save computation time the optimality condition is checked restrictedly for the solution obtained. The difference between the optimal objective value and the objective value obtained can be estimated. By examining numerical results, it is observed that the algorithm is efficient, requiring less computation time than other methods.     

A nonisolated optimal solution of general linear multiplicative programming problems

This article presents a finite branch-and-bound algorithm for globally solving general linear multiplicative programming problems (GLMP). The proposed algorithm is based on the recently developed theory of monotonic optimization. The proposed algorithm provides a nonisolated global optimal solution, and it turns out that such an optimal solution is adequately guaranteed to be feasible and to be close to the actual optimal solution. It can be shown by the numerical results that the proposed algorithm is effective and the computational results can be gained in short time.     

Generalized disjunctive constraint propagation for solving the job shop problem with time lags

This paper addresses the job-shop scheduling problem with time-lags. We propose an insertion heuristic and generalized resource constraint propagation mechanisms. Our propositions are embedded in a branch-and-bound algorithm to provide an experimental evaluation on some benchmark instances. The results obtained conclude that our heuristic achieves the best solutions on the instances, especially when problems involve tightened time lags. The results also prove the interest of the constraint propagation generalization when time lags are considered.     

A self-adaptive linear evolutionary algorithm for solving constrained optimization problems

In many real-world applications of evolutionary algorithms, the fitness of an individual requires a quantitative measure. This paper proposes a self-adaptive linear evolutionary algorithm (ALEA) in which we introduce a novel strategy for evaluating individual’s relative strengths and weaknesses. Based on this strategy, searching space of constrained optimization problems with high dimensions for design variables is compressed into two-dimensional performance space in which it is possible to quickly identify ‘good’ individuals of the performance for a multiobjective optimization application, regardless of original space complexity. This is considered as our main contribution. In addition, the proposed new evolutionary algorithm combines two basic operators with modification in reproduction phase, namely, crossover and mutation. Simulation results over a comprehensive set of benchmark functions show that the proposed strategy is feasible and effective, and provides good performance in terms of uniformity and diversity of solutions.     

Yet harder knapsack problems

Already 30 years ago, Chvátal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules. We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution.     

A computational analysis of LCP methods for bilinear and concave quadratic programming

The use of a sequential linear complementarity problem (SLCP) algorithm for finding a global minimum of bilinear programming problem (BLP) or a concave quadratic program (CQP) is examined. The algorithm consists of solving a sequence of linear complementarity problems (LCP). A branch-and-bound method is also considered in this study. This algorithm is based on the reformulation of a BLP into an LCP with a linear function to minimize. Computational experience with small and medium scale BLPs and CQPs indicates that the SLCP algorithm is quite efficient in finding a global minimum (or at least a solution that is quite near the optimum), but it is, in general, unable to establish that such a solution has been found. An algorithm to find a lower-bound for the BLP can overcome this drawback in some cases. Furthermore the SLCP algorithm is shown to be robust and compares favorably with the branch-and-bound method and another alternative technique.     

Some results and experiments in programming techniques for propositional logic

We provide some results which relate mathematical programming techniques for treating propositional logic to theorem-proving techniques for this logic. We show that the branch-and-bound method, applied to the usual linear representation of clauses, is very similar to an implementation of Loveland's (generally stronger) form of the algorithm of Davis and Putnam. However, branch-and-bound does not include the fixing of monotone variables, while it does have the incumbent-finding feature which is lacking in the Davis-Putnam procedure.We also provide a linear-time algorithm for achieving a clausal form equivalent to a given proposition, in some additional atomic letters. Experimental results are included.     

An efficient search direction for linear programming problems

In this paper, we present an auxiliary algorithm, in terms of the speed of obtaining the optimal solution, that is effective in helping the simplex method for commencing a better initial basic feasible solution. The idea of choosing a direction towards an optimal point presented in this paper is new and easily implemented. From our experiments, the algorithm will release a corner point of the feasible region within few iterative steps, independent of the starting point. The computational results show that after the auxiliary algorithm is adopted as phase I process, the simplex method consistently reduce the number of required iterations by about 40%.Scope and purposeRecent progress in the implementations of simplex and interior point methods as well as advances in computer hardware has extended the capability of linear programming with today's computing technology. It is well known that the solution times for the interior point method improve with problem size. But, experimental evidence suggests that interior point methods dominate simplex-based methods only in the solution of very large scale linear programs. If the problem size is medium, how to combine the best features of these two methods to produce an effective algorithm for solving linear programming problems is still an interesting problem. In this research we present a new effective ε-optimality search direction based on the interior point method to start an initial basic feasible solution near the optimal point for the simplex method.     

基于内部罚函数的进化算法求解约束优化问题

为解决现有约束处理方法可行解的适应度函数不包含约束条件的问题,提出了一种内部罚函数候选解筛选规则.该候选解筛选规则分别对可行解和不可行解采用内部罚函数和约束违反度进行筛选,从而达到平衡最小化目标函数和满足约束条件的目的.以进化策略算法为基础,给出了基于内部罚函数候选解筛选规则的进化算法的一个实现.进一步地,从理论和实验角度分别验证了内部罚函数候选解筛选规则的有效性:以(1+1)进化算法为例,从进化成功率方面验证了内部罚函数候选解筛选规则的理论有效性;通过13个测试问题的数值实验,从进化成功率、候选解后代是可行解的比例、进化步长和收敛速度方面验证了内部罚函数候选解筛选规则的实验有效性.     

一种自适应多策略行为粒子群优化算法

针对粒子群优化算法收敛速度慢、局部搜索能力差等缺点,提出一种自适应多策略行为粒子群优化算法.算法中每个粒子拥有4种行为进化策略,在迭代过程中通过计算每种进化策略的立即价值、未来价值和综合奖励来决定粒子的进化行为,并通过策略行为概率变异算法提升个体寻优速度或避免陷入局部最优解.在经典的基准测试函数上,对新算法与其他7个群智能进化算法的测试结果进行比较分析,结果表明所提出算法具有很好的求解精度和收敛速度,尤其适合应用于一些高维优化问题.     

EDHMoR: Evolutionary designer of heterogeneous modular robots

This paper is devoted to the problem of automatically designing feasible and manufacturable robots made up of heterogeneous modules. Specifically, the coevolution of morphology and control in robots is analyzed and a particular strategy to address this problem is contemplated. To this end, the main issues of this approach such as encoding, evaluation or transfer to reality are studied through the use of heterogeneous modular structures with distributed control. We also propose a constructive evolutionary algorithm based on tree-like representations of the morphology that can intrinsically provide for a type of generative evolutionary approach. The algorithm introduces some new elements to smooth the search space and make finding solutions much easier. The evaluation of the individuals is carried out in simulations and then transferred to real robots assembled from the modules considered. To this end, the extension of the principles proposed by classical authors in traditional evolutionary robotics to brain–body evolution regarding how simulations should be set up so that robust behaviors that can be transferred to reality are obtained is considered here. All these issues are analyzed by means of an evolutionary design system called EDHMoR (Evolutionary Designer of Heterogeneous Modular Robots) that contains all the elements involved in this process. To show practical evidences of the conclusions that have been extracted with this work, two benchmark problems in modular robotics are considered and EDHMoR is tested over them. The first one is focused on solving a linear robot motion mission and the second one on a static task of the robot that does not require displacements.     

A System to Generate Test Data and Symbolically Execute Programs

This paper describes a system that attempts to generate test data for programs written in ANSI Fortran. Given a path, the system symbolically executes the path and creates a set of constraints on the program's input variables. If the set of constraints is linear, linear programming techniques are employed to obtain a solution. A solution to the set of constraints is test data that will drive execution down the given path. If it can be determined that the set of constraints is inconsistent, then the given path is shown to be nonexecutable. To increase the chance of detecting some of the more common programming errors, artificial constraints are temporarily created that simulate error conditions and then an attempt is made to solve each augmented set of constraints. A symbolic representation of the program's output variables in terms of the program's input variables is also created. The symbolic representation is in a human readable form that facilitates error detection as well as being a possible aid in assertion generation and automatic program documentation.     

Efficient algorithms for the uncapacitated single allocation p-hub median problem

We present a new LP formulation for the single allocation p-hub median problem, which requires fewer variables and constraints than those traditionally used in the literature. We develop a good heuristic algorithm for its solution based on simulated annealing (SA). We use the SA upper bound to develop an LP-based branch-and-bound solution method. We present computational results for well-known problems from the literature which show that exact solutions can be found in a reasonable amount of computational time. We also benchmark our new solution approach on a new data set. This data set, which includes problems that are larger than those used in the literature, is based on a postal delivery network.     

Multiple-model based predictive control of nonlinear hybrid systems based on global optimization using the Bernstein polynomial approach

In this paper, we propose a Bernstein polynomial based global optimization algorithm for the optimal feedback control of nonlinear hybrid systems using a multiple-model approach. Specifically, we solve at every sampling instant a polynomial mixed-integer nonlinear programming problem arising in the model predictive control strategy. The proposed algorithm uses the Bernstein polynomial form in a branch-and-bound framework, with new ingredients such as branching for integer decision variables and fathoming for each subproblem in the branch-and-bound tree. The performance of the proposed algorithm is tested and compared with existing algorithms on a benchmark three-spherical tank system. The test results show the superior performance of the proposed algorithm.     

一种求解约束优化问题的线性进化算法

提出一种基于实数编码处理约束优化问题的线性算法,并对其复杂度和收敛性进行分析.该算法将约束优化问题的高维搜索空间通过线性变换映射到二维空间,在二维空间中探索原优化问题的解,从数学分析的角度给出一种线性适应度函数.算法中融入一种基于密度函数的交叉算子和变异算法,采用基于分级聚类的平均联接方式以维持Pareto最优解集个体数目.3组典型优化问题的测试表明,该算法是可行和有效的,解集分布的均匀性与多样性均较理想.     

Operational planning of combined heat and power plants through genetic algorithms for mixed 0–1 nonlinear programming

This paper is concerned with short-term (up to 24 h) operational planning in combined heat and power plants for district energy applications. In such applications, heat and power demands fluctuate on an hourly basis due to changing weather conditions, time-of-day factors and consumer requirements. Plant energy efficiency is highly dependent on ambient temperature and operating load since equipment efficiencies are nonlinear functions of these parameters. In operational planning strategies, nonlinear equipment characteristics are seldom taken into account, resulting in plants being operated at sub-par efficiencies. In order to operate plants at highest possible efficiencies, scheduling strategies which take into account nonlinear equipment characteristics need to be developed. For such strategies, a mixed 0–1 nonlinear programming formulation is proposed. The problem is nonconvex and hence global optimality conditions are unknown. Classical techniques like branch-and-bound may not produce integer feasible solutions, may cut off the global optima and have an exponential increase in CPU time for a linear increase in planning horizon size. As an alternative, a solution method through genetic algorithms is proposed in which genetic search is applied only on 0–1 variables and gradient search is applied on continuous variables. The proposed method is a nonlinear extension of the one originally developed by Sakawa et al. [Sakawa M, Kato K, Ushiro S. Operational planning of district heating and cooling plants through genetic algorithms for mixed 0–1 linear programming. Eur J Operat Res 2002;137(3):677–87]. Numerical experiments show the proposed genetic algorithm method is more consistent in finding integer feasible solutions, finds solutions with lower optimality gaps and has reasonable CPU time as compared to branch-and-bound. From an application perspective, the proposed scheduling strategy results in 5–11% increase in plant energy efficiency.     

Branch-and-bound algorithm for the maximum triangle packing problem

This work addresses the problem of finding the maximum number of unweighted vertex-disjoint triangles in an undirected graph G. It is a challenging NP-hard combinatorial problem and it is well-known to be APX-hard. A branch-and-bound algorithm which uses a lower bound based on neighborhood degree is presented. A naive upper bound is proposed as well as another one based on a surrogate relaxation of the related integer linear program which is analogous to a multidimensional knapsack problem. Further, a Greedy Search algorithm and a genetic algorithm are described to improve the lower bound. A computational comparison of lower bounds, branch-and-bound algorithm and CPLEX solver is provided using randomly generated benchmarks and well-known DIMACS implementation challenges. The empirical study shows that the branch-and-bound finds the optimal triangle packing solution for small randomly generated MTP instances (up to 100 vertices and 200 triangles) and some DIMACS graphs. For some larger instances and DIMACS challenges graphs, we remark that our lower bound outperforms CPLEX solver regarding the triangle packing solution and the computation time.     

Stability analysis of efficient solutions in multiobjective integer programming: A case study in load management

This paper presents a multiobjective linear integer programming model for supporting the choice of remote load control strategies in electric distribution network management. The model takes into account the main concerns in load management, considering three objective functions: minimization of the peak demand as perceived by the distribution network dispatch center, maximization of the utility profit associated with the energy services delivered by the controlled loads and minimization of the discomfort caused to consumers. The problem was analyzed using an interactive reference point method for multiobjective integer (and mixed-integer) linear programming. This approach exploits the use of the branch-and-bound algorithm for solving the reference point scalarizing programs through which efficient solutions are computed. Post-optimality techniques enable a stability analysis of the efficient solutions by means of computing and displaying graphically sets of reference points that correspond to the same solution.     

Assessment of a non-adaptive deterministic global optimization algorithm for problems with low-dimensional non-convex subspaces

The optimum and at least one optimizing point for convex nonlinear programs can be approximated well by the solution to a linear program (a fact long used in branch and bound algorithms). In more general problems, we can identify subspaces of ‘non-convex variables’ such that, if these variables have sufficiently small ranges, the optimum and at least one optimizing point can be approximated well by the solution of a single linear program. If these subspaces are low-dimensional, this suggests subdividing the variables in the subspace a priori, then producing and solving a fixed, known number of linear programs to obtain an approximation to the solution. The total amount of computation is much more predictable than that required to complete a branch and bound algorithm, and the scheme is ‘embarrassingly parallel’, with little need for either communication or load balancing. We compare such a non-adaptive scheme experimentally to our GlobSol branch and bound implementation, on those problems from the COCONUT project Lib1 test set with non-convex subspaces of dimension four or less, and we discuss potential alterations to both the non-adaptive scheme and our branch and bound process that might change the scope of applicability.