An objective hyperplane search procedure for solving the general all-integer linear programming (ILP) problem

We describe an objective hyperplane search method for solving a class of integer linear programming (ILP) problems. We formulate the search as a bounded knapsack problem and develop requisite theory for formulating knapsack problems with composite constraints and composite objective functions that facilitate convergence to an ILP solution. A heuristic solution algorithm was developed and used to solve a variety of test problems found in the literature. The method obtains optimal or near-optimal solutions in acceptable ranges of computational effort.     

The balanced academic curriculum problem revisited

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

Characterizations of the Solution Sets of Convex Programs and Variational Inequality Problems

For a convex program in a normed vector space with the objective function admitting the Gateaux derivative at an optimal solution, we show that the solution set consists of the feasible points lying in the hyperplane whose normal vector equals the Gateaux derivative. For a general continuous convex program, a feasible point is an optimal solution iff it lies in a hyperplane with a normal vector belonging to the subdifferential of the objective function at this point. In several cases, the solution set of a variational inequality problem is shown to coincide with the solution set of a convex program with its dual gap function as objective function, while the mapping involved can be used to express the above normal vectors.The research was supported by the National Science Council of the Republic of China. The authors are grateful to the referees for valuable comments and constructive suggestions.     

On a generalised<Emphasis Type="Italic">ε</Emphasis>-control problem in Banach space

In this paper a linearε-control problem for a general objective function is considered by functional analytic approach. Existence and uniqueness of solutions are shown. The characterization of the solution is given in terms of a hyperplane.     

Finding multiple solutions to general integer linear programs

Integer linear programming (ILP) problems occur frequently in many applications. In practice, alternative optima are useful since they allow the decision maker to choose from multiple solutions without experiencing any deterioration in the objective function. This study proposes a general integer cut to exclude the previous solution and presents an algorithm to identify all alternative optimal solutions of an ILP problem. Numerical examples in real applications are presented to demonstrate the usefulness of the proposed method.     

A GRASP + ILP-based metaheuristic for the capacitated location-routing problem

In this paper we present a three-phase heuristic for the Capacitated Location-Routing Problem. In the first stage, we apply a GRASP followed by local search procedures to construct a bundle of solutions. In the second stage, an integer-linear program (ILP) is solved taking as input the different routes belonging to the solutions of the bundle, with the objective of constructing a new solution as a combination of these routes. In the third and final stage, the same ILP is iteratively solved by column generation to improve the solutions found during the first two stages. The last two stages are based on a new model, the location-reallocation model, which generalizes the capacitated facility location problem and the reallocation model by simultaneously locating facilities and reallocating customers to routes assigned to these facilities. Extensive computational experiments show that our method is competitive with the other heuristics found in the literature, yielding the tightest average gaps on several sets of instances and being able to improve the best known feasible solutions for some of them.     

An integer linear formulation for the file transfer scheduling problem

In this paper, we propose a new integer linear programming (ILP) formulation for solving a file transfer scheduling problem (FTSP), which is to minimize the overall time needed to transfer all files to their destinations for a given collection of various sized files in a computer network. Each computer in this network has a limited number of communication ports. The described problem is proved to be NP-hard in a general case. Our formulation enables solving the problem by standard ILP solvers like CPLEX or Gurobi. To prove the validity of the proposed ILP formulation, two new reformulations of FTSP are presented. The results obtained by CPLEX and Gurobi solvers, based on this formulation, are presented and discussed.     

On the convergence of a class of outer approximation algorithms for convex programs

This paper presents a new class of outer approximation methods for solving general convex programs. The methods solve at each iteration a subproblem whose constraints contain the feasible set of the original problem. Moreover, the methods employ quadratic objective functions in the subproblems by adding a simple quadratic term to the objective function of the original problem, while other outer approximation methods usually use the original objective function itself throughout the iterations. By this modification, convergence of the methods can be proved under mild conditions. Furthermore, it is shown that generalized versions of the cut construction schemes in Kelley-Cheney-Goldstein's cutting plane method and Veinott's supporting hyperplane method can be incorporated with the present methods and a cut generated at each iteration need not be retained in the succeeding iterations.     

The multiparametric 0–1-integer linear programming problem: A unified approach

We designed an algorithm for the multiparametric 0–1-integer linear programming (ILP) problem with the perturbation of the constraint matrix, the objective function and the right-hand side vector simultaneously considered. Our algorithm works by choosing an appropriate finite sequence of non-parametric mixed integer linear programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

凸规划的新算法

对一般凸目标函数和一般凸集约束的凸规划问题新解法进行探讨,它是线性规划一种新算法的扩展和改进,此算法的基本思想是在规划问题的可行域中由所建－的一个切割面到另一个切割面的不断推进来求取最优的。文章对目标函数是二次的且约束是一般凸集和二次目标函数且约束是线性的情形,给出了更简单的算法。     

Integer linear programming models for grid-based light post location problem

Selecting optimal location is a key decision problem in business and engineering. This research focuses to develop mathematical models for a special type of location problems called grid-based location problems. It uses a real-world problem of placing lights in a park to minimize the amount of darkness and excess supply. The non-linear nature of the supply function (arising from the light physics) and heterogeneous demand distribution make this decision problem truly intractable to solve. We develop ILP models that are designed to provide the optimal solution for the light post problem: the total number of light posts, the location of each light post, and their capacities (i.e., brightness). Finally, the ILP models are implemented within a standard modeling language and solved with the CPLEX solver. Results show that the ILP models are quite efficient in solving moderately sized problems with a very small optimality gap.     

A contraction algorithm for the multiparametric integer linear programming problem

We designed and implemented an algorithm to solve the continuos right hand side multiparametric Integer Linear Programming (ILP) problem, that is to solve a family of ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of nonparametric Mixed Integer Linear Programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

一种改进的禁忌搜索算法及其在选址问题中的应用

本文研究了选址问题中无容量限制的p-中值问题,在Rolland等人提出的有效禁忌搜索算法基础上,提出了一种以目标函数变化量作为评价函数的改进禁忌搜索算法,并进行了理论分析,然后将其与有效禁忌搜索算法作了性能比较.通过比较三个公共测试数据集的计算结果,验证了本文提出的禁忌搜索算法的可行性和有效性.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Online scheduling of parallel jobs on two machines is 2-competitive

We consider online scheduling of parallel jobs on parallel machines. For the problem with two machines and the objective of minimizing the makespan, we show that 2 is a tight lower bound on the competitive ratio. For the problem with m machines, we derive lower bounds using an ILP formulation.     

Tabu search approaches for solving the two-group classification problem

The two-group classification problem consists in constructing a classifier that can distinguish between the two groups. In this paper, we consider the two-group classification problem which consists in determining a hyperplane that minimizes the number of misclassified points. We assume that the data set is numeric and with no missing data. We develop a tabu search (TS) heuristic for solving this NP-hard problem. The TS approach is based on a more convenient equivalent formulation of the classification problem. We also propose supplementary new intensification phases based on surrogate constraints. The results of the conducted computational experiments show that our TS algorithms produce solutions very close to the optimum and require significantly lower computational effort, so it is a valuable alternative to the MIP approaches. Moreover the tabu search procedures showed in this paper can be extended in a natural way to the general classification problem, which consists of generating more than one separating hyperplanes.     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

Two derivative-free projection approaches for systems of large-scale nonlinear monotone equations

This study proposes two derivative-free approaches for solving systems of large-scale nonlinear equations, where the underlying functions of the systems are continuous and satisfy a monotonicity condition. First, the framework generates a specific direction then employs a backtracking line search along this direction to construct a new point. If the new point solves the problem, the process will be stopped. Under other circumstances, the projection technique constructs an appropriate hyperplane strictly separating the current iterate from the solutions of the problem. Then the projection of the new point onto the hyperplane will determine the next iterate. Thanks to the low memory requirement of derivative-free conjugate gradient approaches, this work takes advantages of two new derivative-free conjugate gradient directions. Under appropriate conditions, the global convergence result of the recommended procedures is established. Preliminary numerical results indicate that the proposed approaches are interesting and remarkably promising.