A Reference Direction Algorithm for Solving Multiple Objective Integer Linear Programming Problems

In this paper, we propose a reference direction approach and an interactive algorithm to solve the general multiple objective integer linear programming problem. At each iteration, only one mixed integer linear programming problem is solved to find an (weak) efficient solution. Each intermediate solution is integer. The decision maker has to provide only the reference point at each iteration. No special software is required to implement the proposed algorithm. The algorithm is illustrated with an example.     

Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems

The satisfiability problem in forms such as maximum satisfiability (MAX-SAT) remains a hard problem. The most successful approaches for solving such problems use a form of systematic tree search. This paper describes the use of a hybrid algorithm, combining genetic algorithms and integer programming branch and bound approaches, to solve MAX-SAT problems. Such problems are formulated as integer programs and solved by a hybrid algorithm implemented within standard mathematical programming software. Computational testing of the algorithm, which mixes heuristic and exact approaches, is described.     

整数规划的一类填充函数算法

填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。     

Minimizing the total completion time on a single machine with the learning effect and multiple availability constraints

This paper considers a single machine scheduling problem with the learning effect and multiple availability constraints that minimizes the total completion time. To solve this problem, a new binary integer programming model is presented, and a branch-and-bound algorithm is also developed for solving the given problem optimally. Since the problem is strongly NP-hard, to find the near-optimal solution for large-sized problems within a reasonable time, two meta-heuristics; namely, genetic algorithm and simulated annealing are developed. Finally, the computational results are provided to compare the result of the binary integer programming, branch-and-bound algorithm, genetic algorithm and simulated annealing. Then, the efficiency of the proposed algorithms is discussed.     

A Simultaneous Enumeration Approach to the Traveling Salesman Problem

The solution procedure proposed in this paper uses certain principles of analog computers. The idea of using analog rather than digital computers to solve mathematical programming problems is not new—various methods have been proposed to solve linear programming, network flows, as well as shortest path problems (Dennis, 1959; Stern, 1965). These problems can be more efficiently solved with digital computers. To find a solution to the traveling salesman problem as well as other integer programming problems is difficult with existing hardware, especially if the number of variables is large. The question thus arises whether different hardware configurations make it possible to solve integer problems more efficiently. One such configuration is proposed below for the traveling salesman problem.     

On the prize-collecting generalized minimum spanning tree problem

The prize-collecting generalized minimum spanning tree problem (PC-GMSTP), is a generalization of the generalized minimum spanning tree problem (GMSTP) and belongs to the hard core of -hard problems. We describe an exact exponential time algorithm for the problem, as well we present several mixed integer and integer programming formulations of the PC-GMSTP. Moreover, we establish relationships between the polytopes corresponding to their linear relaxations and present an efficient solution procedure that finds the optimal solution of the PC-GMSTP for graphs with up 240 nodes.     

A partitioning algorithm for the network loading problem

This paper proposes a Benders-like partitioning algorithm to solve the network loading problem. The approach is an iterative method in which the integer programming solver is not used to produce the best integer point in the polyhedral relaxation of the set of feasible capacities. Rather, it selects an integer solution that is closest to the best known integer solution. Contrary to previous approaches, the method does not exploit the original mixed integer programming formulation of the problem. The effort of computing integer solutions is entirely left to a pure integer programming solver while valid inequalities are generated by solving standard nonlinear multicommodity flow problems. The method is compared to alternative approaches proposed in the literature and appears to be efficient for computing good upper bounds.     

Extensions of Dinkelbach's algorithm for solving non-linear fractional programming problems

Dinkelbach's algorithm was developed to solve convex fractinal programming. This method achieves the optimal solution of the optimisation problem by means of solving a sequence of non-linear convex programming subproblems defined by a parameter. In this paper it is shown that Dinkelbach's algorithm can be used to solve general fractional programming. The applicability of the algorithm will depend on the possibility of solving the subproblems. Dinkelbach's extended algorithm is a framework to describe several algorithms which have been proposed to solve linear fractional programming, integer linear fractional programming, convex fractional programming and to generate new algorithms. The applicability of new cases as nondifferentiable fractional programming and quadratic fractional programming has been studied. We have proposed two modifications to improve the speed-up of Dinkelbachs algorithm. One is to use interpolation formulae to update the parameter which defined the subproblem and another truncates the solution of the suproblem. We give sufficient conditions for the convergence of these modifications. Computational experiments in linear fractional programming, integer linear fractional programming and non-linear fractional programming to evaluate the efficiency of these methods have been carried out.     

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

求解中大规模复杂凸二次整数规划问题的新型分枝定界算法

针对现有分枝定界算法在求解高维复杂二次整数规划问题时所存在的诸多不足，本文通过充分挖掘二次整数规划问题的结构特性来设计选择分枝变量与分枝方向的新方法，并将HNF算法与原问题松弛问题的求解相结合来寻求较好的初始整数可行解，由此导出可用于有效求解中大规模复杂二次整数规划问题的改进型分枝定界算法．数值试验结果表明所给算法大大改进了已有相关的分枝定界算法，并具有较好的稳定性与广泛的适用性．     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

An linear programming based lower bound for the simple assembly line balancing problem

The simple assembly line balancing problem is a classical integer programming problem in operations research. A set of tasks, each one being an indivisible amount of work requiring a number of time units, must be assigned to workstations without exceeding the cycle time. We present a new lower bound, namely the LP relaxation of an integer programming formulation based on Dantzig–Wolfe decomposition. We propose a column generation algorithm to solve the formulation. Therefore, we develop a branch-and-bound algorithm to exactly solve the pricing problem. We assess the quality of the lower bound by comparing it with other lower bounds and the best-known solution of the various instances from the literature. Computational results show that the lower bound is equal to the best-known objective function value for the majority of the instances. Moreover, the new LP based lower bound is able to prove optimality for an open problem.     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

A heuristic decomposition approach to optimal control in a water supply model

The optimal pump control problem in a water supply system can be formulated as a mixed integer programming problem. In general, this problem is very difficult to solve by conventional integer programming algorithms, because the number of decision variables is as large as the total number of combinations of pump stations and control periods. However, it possesses a certain block triangular structure, which offers an attractive computational scheme. Taking advantage of this structure, this paper proposes a heuristic decomposition algorithm for finding a good feasible solution to this type of mixed integer programming problems. Numerical results for an actual pump control problem are also reported.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

A Metaheuristic to Solve a Location-Routing Problem with Non-Linear Costs

The paper deals with a location-routing problem with non-linear cost functions. To the best of our knowledge, a mixed integer linear programming formulation for the addressed problem is proposed here for the first time. Since the problem is NP-hard exact algorithms are able to solve only particular cases, thus to solve more general versions heuristics are needed. The algorithm proposed in this paper is a combination of a p-median approach to find an initial feasible solution and a metaheuristic to improve the solution. It is a hybrid metaheuristic merging Variable Neighborhood Search (VNS) and Tabu Search (TS) principles and exploiting the synergies between the two. Computational results and conclusions close the paper.     

Comparison of two algorithms for solving a two‐stage bilinear stochastic programming problem with quantile criterion

The paper is devoted to solving the two‐stage problem of stochastic programming with quantile criterion. It is assumed that the loss function is bilinear in random parameters and strategies, and the random vector has a normal distribution. Two algorithms are suggested to solve the problem, and they are compared. The first algorithm is based on the reduction of the original stochastic problem to a mixed integer linear programming problem. The second algorithm is based on the reduction of the problem to a sequence of convex programming problems. Performance characteristics of both the algorithms are illustrated by an example. A modification of both the algorithms is suggested to reduce the computing time. The new algorithm uses the solution obtained by the second algorithm as a starting point for the first algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

Minimizing total weighted late work in the resource-constrained project scheduling problem

This paper deals with resource-constrained project scheduling problem under the weighted late work criterion. Late work objective functions estimate the quality of a schedule based on durations of late parts of activities, not taking into account the amount of delay for fully late activities. It is assume that a project contains activities interrelated by finish-to-start type precedence relations with time lag of zero, which require one or more constrained renewable resources. The objective is to schedule each activity such that the total weighted late work is minimized. The problem has been formulated using a linear integer programming model and solved by the CPLEX. Also, a set of priority rules have been designed to quickly generate a set of initial solutions. In order to solve the problem optimally, a depth-first branch-and-bound algorithm is applied based on idea of minimal delaying alternatives. The branching order of nodes that belong to the same level of the search tree is determined on the basis of the developed priority rules. This results in generation six different versions of the branch-and-bound algorithm. Computational results on randomly generated problem sets are provided to analyze the efficiency of the priority rules and the branch-and-bound algorithm.     

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 branch and bound method for the solution of multiparametric mixed integer linear programming problems

In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch and bound strategy that involves the solution of a multiparametric linear programming sub-problem at leaf nodes and appropriate comparison procedures to update the tree. McCormick relaxation procedures are employed to overcome the presence of bilinear terms in the model. The algorithm generates an envelope of parametric profiles, containing the optimal solution of the mp-MILP problem. The parameter space is partitioned into polyhedral convex critical regions. Two examples are presented to illustrate the steps of the proposed algorithm.