Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance

In this paper, we study the 1-maximin problem with rectilinear distance. We locate a single undesirable facility in a continuous planar region while considering the interaction between the facility and existing demand points. The distance between facility and demand points is measured in the rectilinear metric. The objective is to maximize the distance of the facility from the closest demand point. The 1-maximin problem has been formulated as an MIP model in the literature. We suggest new bounding schemes to increase the solution efficiency of the model as well as improved branch and bound strategies for implementation. Moreover, we simplify the model by eliminating some redundant integer variables. We propose an efficient solution algorithm called cut and prune method, which splits the feasible region into four equal subregions at each iteration and tries to eliminate subregions depending on the comparison of upper and lower bounds. When the sidelengths of the subregions are smaller than a predetermined value, the improved MIP model is solved to obtain the optimal solution. Computational experiments demonstrate that the solution time of the original MIP model is reduced substantially by the proposed solution approach.     

解带有二次约束非凸二次规划问题的一个分枝缩减方法

在这篇论文里,有机地把外逼近方法与分枝定界技术结合起来,提出了解带有二次约束非凸二次规划问题的一个分枝缩减方法;给出了原问题的一个新的线性规划松弛,以便确定它在超矩形上全局最优值的一个下界;利用超矩形的一个深度二级剖分方法,以及超矩形的缩减和删除技术,提高算法的收敛速度;证明了在知道原问题可行点的条件下,该算法在有限步里就可以获得原问题的一个全局最优化解,并且用一个例子说明了该算法是有效的.     

Exploring relaxation induced neighborhoods to improve MIP solutions

Given a feasible solution to a Mixed Integer Programming (MIP) model, a natural question is whether that solution can be improved using local search techniques. Local search has been applied very successfully in a variety of other combinatorial optimization domains. Unfortunately, local search relies extensively on the notion of a solution neighborhood, and this neighborhood is almost always tailored to the structure of the particular problem being solved. A MIP model typically conveys little information about the underlying problem structure. This paper considers two new approaches to exploring interesting, domain-independent neighborhoods in MIP. The more effective of the two, which we call Relaxation Induced Neighborhood Search (RINS), constructs a promising neighborhood using information contained in the continuous relaxation of the MIP model. Neighborhood exploration is then formulated as a MIP model itself and solved recursively. The second, which we call guided dives, is a simple modification of the MIP tree traversal order. Loosely speaking, it guides the search towards nodes that are close neighbors of the best known feasible solution. Extensive computational experiments on very difficult MIP models show that both approaches outperform default CPLEX MIP and a previously described approach for exploring MIP neighborhoods (local branching) with respect to several different metrics. The metrics we consider are quality of the best integer solution produced within a time limit, ability to improve a given integer solution (of both good and poor quality), and time required to diversify the search in order to find a new solution.Mathematics Subject Classification (2000):20E28, 20G40, 20C20Acknowledgement We wish to thank the two anonymous referees for their helpful comments.     

A mathematical programming-based scheduling framework for multitasking environments

A new paradigm along with a mixed (binary) integer-linear programming model is developed for scheduling tasks in multitasking environments, for which the number of completed tasks is not a good measure. One special case falls into the realm of deteriorating jobs. Polynomial time optimal solution algorithms are presented for this and one other special case. As the complexity of the original problem is believed to be strongly NP-hard, an efficient solution algorithm, based on tabu search, is developed to solve the problem. Small, medium, and large size problems are solved, and the solution obtained from the algorithm is compared with that of the optimal solution or the upper bound found from using the Lagrangian relaxation. Where it was measurable, the search algorithm gave quantifiably good quality solutions, and in all cases it had a much better time efficiency than the branch-and-bound enumeration method. A detailed statistical experiment, based on the split-plot design, is developed to identify the characteristics of the tabu search algorithm, thus guaranteeing a solution that is significantly better in quality. A conjecturing technique is introduced for problems with very large planning horizons. This technique had remarkable time efficiency with no apparent loss of quality.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

An improved Lagrangian relaxation and dual ascent approach to facility location problems

The literature knows semi-Lagrangian relaxation as a particular way of applying Lagrangian relaxation to certain linear mixed integer programs such that no duality gap results. The resulting Lagrangian subproblem usually can substantially be reduced in size. The method may thus be more efficient in finding an optimal solution to a mixed integer program than a “solver” applied to the initial MIP formulation, provided that “small” optimal multiplier values can be found in a few iterations. Recently, a simplification of the semi-Lagrangian relaxation scheme has been suggested in the literature. This “simplified” approach is actually to apply ordinary Lagrangian relaxation to a reformulated problem and still does not show a duality gap, but the Lagrangian dual reduces to a one-dimensional optimization problem. The expense of this simplification is, however, that the Lagrangian subproblem usually can not be reduced to the same extent as in the case of ordinary semi-Lagrangian relaxation. Hence, an effective method for optimizing the Lagrangian dual function is of utmost importance for obtaining a computational advantage from the simplified Lagrangian dual function. In this paper, we suggest a new dual ascent method for optimizing both the semi-Lagrangian dual function as well as its simplified form for the case of a generic discrete facility location problem and apply the method to the uncapacitated facility location problem. Our computational results show that the method generally only requires a very few iterations for computing optimal multipliers. Moreover, we give an interesting economic interpretation of the semi-Lagrangian multiplier(s).     

Solving the Unit Commitment Problem by a Unit Decommitment Method

In this paper, we present a unified decommitment method to solve the unit commitment problem. This method starts with a solution having all available units online at all hours in the planning horizon and determines an optimal strategy for decommitting units one at a time. We show that the proposed method may be viewed as an approximate implementation of the Lagrangian relaxation approach and that the number of iterations is bounded by the number of units. Numerical tests suggest that the proposed method is a reliable, efficient, and robust approach for solving the unit commitment problem.     

Bike sharing systems: Solving the static rebalancing problem

This paper deals with a new problem that is a generalization of the many to many pickup and delivery problem and which is motivated by operating self-service bike sharing systems. There is only one commodity, initially distributed among the vertices of a graph, and a capacitated single vehicle aims to redistribute the commodity in order to reach a target distribution. Each vertex can be visited several times and also can be used as a buffer in which the commodity is stored for a later visit. This problem is NP-hard, since it contains several NP-hard problems as special cases (the TSP being maybe the most obvious one). Even finding a tractable exact formulation remains problematic.This paper presents efficient algorithms for solving instances of reasonable size, and contains several theoretical results related to these algorithms. A branch-and-cut algorithm is proposed for solving a relaxation of the problem. An upper bound of the optimal solution of the problem is obtained by a tabu search, which is based on some theoretical properties of the solution, once fixed the sequence of the visited vertices. The possibility of using the information provided by the relaxation receives a special attention, both from a theoretical and a practical point of view. It is proven that to build a feasible solution of the problem by using the one obtained by the relaxation is an NP-hard problem. Nevertheless, a tabu search initialized with the optimal solution of the relaxation often shows that it is the optimal one.The algorithms have been tested on a set of instances coming from the literature, proving their effectiveness.     

An outcome space algorithm for optimization over the weakly efficient set of a multiple objective nonlinear programming problem

This article presents for the first time an algorithm specifically designed for globally minimizing a finite, convex function over the weakly efficient set of a multiple objective nonlinear programming problem (V1) that has both nonlinear objective functions and a convex, nonpolyhedral feasible region. The algorithm uses a branch and bound search in the outcome space of problem (V1), rather than in the decision space of the problem, to find a global optimal solution. Since the dimension of the outcome space is usually much smaller than the dimension of the decision space, often by one or more orders of magnitude, this approach can be expected to considerably shorten the search. In addition, the algorithm can be easily modified to obtain an approximate global optimal weakly efficient solution after a finite number of iterations. Furthermore, all of the subproblems that the algorithm must solve can be easily solved, since they are all convex programming problems. The key, and sometimes quite interesting, convergence properties of the algorithm are proven, and an example problem is solved.     

A Lagrangian relaxation approach to large-scale flow interception problems

The paper presents a tight Lagrangian bound and an efficient dual heuristic for the flow interception problem. The proposed Lagrangian relaxation decomposes the problem into two subproblems that are easy to solve. Information from one of the subproblems is used within a dual heuristic to construct feasible solutions and is used to generate valid cuts that strengthen the relaxation. Both the heuristic and the relaxation are integrated into a cutting plane method where the Lagrangian bound is calculated using a subgradient algorithm. In the course of the algorithm, a valid cut is added and integrated efficiently in the second subproblem and is updated whenever the heuristic solution improves. The algorithm is tested on randomly generated test problems with up to 500 vertices, 12,483 paths, and 43 facilities. The algorithm finds a proven optimal solution in more than 75% of the cases, while the feasible solution is on average within 0.06% from the upper bound.     

An exact feature selection algorithm based on rough set theory

Feature reduction based on rough set theory is an effective feature selection method in pattern recognition applications. Finding a minimal subset of the original features is inherent in rough set approach to feature selection. As feature reduction is a Nondeterministic Polynomial‐time‐hard problem, it is necessary to develop fast optimal or near‐optimal feature selection algorithms. This article aims to propose an exact feature selection algorithm in rough set that is efficient in terms of computation time. The proposed algorithm begins the examination of a solution tree by a breadth‐first strategy. The pruned nodes are held in a version of the trie data structure. Based on the monotonic property of dependency degree, all subsets of the pruned nodes cannot be optimal solutions. Thus, by detecting these subsets in trie, it is not necessary to calculate their dependency degree. The search on the tree continues until the optimal solution is found. This algorithm is improved by selecting an initial search level determined by the hill‐climbing method instead of searching the tree from the level below the root. The length of the minimal reduct and the size of data set can influence which starting search level is more efficient. The experimental results using some of the standard UCI data sets, demonstrate that the proposed algorithm is effective and efficient for data sets with more than 30 features. © 2014 Wiley Periodicals, Inc. Complexity 20: 50–62, 2015     

LP Modelling for the Time Optimal Control Problem of the Heat Equation

To find a control function which puts the heat equation in an unknown minimum time into a stationary regime is considered. Using an embedding method, the problem of finding the time optimal control is reduced to one consisting of minimizing a linear form over a set of positive measures. The resulting problem can be approximated by a finite dimensional linear programming (LP) problem. The nearly optimal control is constructed from the solution of the final LP problem. To find the lower bound of the optimal time a search algorithm is proposed. Some examples demonstrate the effectiveness of the method.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

Mixed-Integer Cuts from Cyclic Groups

We analyze a separation procedure for Mixed-Integer Programs related to the work of Gomory and Johnson on interpolated subadditive functions. This approach has its roots in the Gomory-Johnson characterization on the master cyclic group polyhedron. To our knowledge, the practical benefit that can be obtained by embedding interpolated subadditive cuts in a cutting plane algorithm was not investigated computationally by previous authors. In this paper we compute, for the first time, the lower bound value obtained when adding (implicitly) all the interpolated subadditive cuts that can be derived from the individual rows of an optimal LP tableau, thus approximating the optimization over the intersection of the Gomory corner polyhedron with the LP relaxation of the original problem formulation. The computed bound is compared with that obtained when only Gomory mixed-integer cuts are used, on a very large test-bed of MIP instances.     

A piecewise linearization framework for retail shelf space management models

Managing shelf space is critical for retailers to attract customers and optimize profits. This article develops a shelf-space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. A piecewise linearization technique is used to approximate the complicated nonlinear space-allocation model. The approximation reformulates the non-convex optimization problem into a linear mixed integer programming (MIP) problem. The MIP solution not only generates near-optimal solutions for large scale optimization problems, but also provides an error bound to evaluate the solution quality. Consequently, the proposed approach can solve single category-shelf space management problems with as many products as are typically encountered in practice and with more complicated cost and profit structures than currently possible by existing methods. Numerical experiments show the competitive accuracy of the proposed method compared with the mixed integer nonlinear programming shelf-space model. Several extensions of the main model are discussed to illustrate the flexibility of the proposed methodology.     

A cut-and-solve based algorithm for the single-source capacitated facility location problem

In this paper, we present a cut-and-solve (CS) based exact algorithm for the Single Source Capacitated Facility Location Problem (SSCFLP). At each level of CS’s branching tree, it has only two nodes, corresponding to the Sparse Problem (SP) and the Dense Problem (DP), respectively. The SP, whose solution space is relatively small with the values of some variables fixed to zero, is solved to optimality by using a commercial MIP solver and its solution if it exists provides an upper bound to the SSCFLP. Meanwhile, the resolution of the LP of DP provides a lower bound for the SSCFLP. A cutting plane method which combines the lifted cover inequalities and Fenchel cutting planes to separate the 0–1 knapsack polytopes is applied to strengthen the lower bound of SSCFLP and that of DP. These lower bounds are further tightened with a partial integrality strategy. Numerical tests on benchmark instances demonstrate the effectiveness of the proposed cutting plane algorithm and the partial integrality strategy in reducing integrality gap and the effectiveness of the CS approach in searching an optimal solution in a reasonable time. Computational results on large sized instances are also presented.     

Solving the CLSP by a Tabu Search Heuristic

The multi-item, single-level, capacitated, dynamic lot-sizing problem, commonly abbreviated as CLSP, is considered. The problem is cast in a tight mixed-integer programming model (MIP); tight in the sense that the gap between the optimal value of MIP and that of its linear programming relaxation (LP) is small. The LP relaxation of MIP is then solved by column generation. The resulting feasible solution is further improved by adopting the corresponding set-up schedule and re-optimizing variable costs by solving a minimum-cost network flow (trans-shipment) problem. Subsequently, the improved solution is used as a starting solution for a tabu search procedure, with the worth of moves assessed using the same trans-shipment problem. Results of computational testing of benchmark problem instances are presented. They show that the heuristic solutions obtained are effective, in that they are extremely close to the best known solutions. The computational efficiency makes it possible to solve realistically large problem instances routinely on a personal computer; in particular, the solution procedure is most effective, in terms of solution quality, for larger problem instances.     

A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem

In this paper we present a heuristic method to generate constrained two-dimensional guillotine cutting patterns. This problem appears in different industrial processes of cutting rectangular plates to produce ordered items, such as in the glass, furniture and circuit board business. The method uses a state space relaxation of a dynamic programming formulation of the problem and a state space ascent procedure of subgradient optimization type. We propose the combination of this existing approach with an and/or-graph search and an inner heuristic that turns infeasible solutions provided in each step of the ascent procedure into feasible solutions. Results for benchmark and randomly generated instances indicate that the method’s performance is competitive compared to other methods proposed in the literature. One of its advantages is that it often produces a relatively tight upper bound to the optimal value. Moreover, in most cases for which an optimal solution is obtained, it also provides a certificate of optimality.     

求解带时间窗车辆路径问题的混合Memetic算法

为提高带时间窗车辆路径问题的求解精度和求解效率,设计了一种混合Memetic算法。采用基于时间窗升序排列的混合插入法构造初始种群,提高解质量的同时兼顾多样性,扩大搜索空间;任意选择组成父代种群,以维持搜索空间;运用简化的变邻域搜索进行局部开发,引入邻域半径减少策略提高开发效率,约束放松机制开放局部空间;以弧为对象,增加种群向当前最优解和全局最优解的后学习过程。实验结果表明,所提出的算法具有较好的寻优精度和稳定性,能搜索到更好的路径长度结果,更新了现有研究在最短路径长度的目标函数上的下限。     

Proximity search for 0-1 mixed-integer convex programming

In this paper we investigate the effects of replacing the objective function of a 0-1 mixed-integer convex program (MIP) with a “proximity” one, with the aim of using a black-box solver as a refinement heuristic. Our starting observation is that enumerative MIP methods naturally tend to explore a neighborhood around the solution of a relaxation. A better heuristic performance can however be expected by searching a neighborhood of an integer solution—a result that we obtain by just modifying the objective function of the problem at hand. The relationship of this approach with primal integer methods is also addressed. Promising computational results on different proof-of-concept implementations are presented, suggesting that proximity search can be quite effective in quickly refining a given feasible solution. This is particularly true when a sequence of similar MIPs has to be solved as, e.g., in a column-generation setting.