An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource-constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.     

Credal model averaging for classification: representing prior ignorance and expert opinions

Bayesian model averaging (BMA) is the state of the art approach for overcoming model uncertainty. Yet, especially on small data sets, the results yielded by BMA might be sensitive to the prior over the models. Credal model averaging (CMA) addresses this problem by substituting the single prior over the models by a set of priors (credal set). Such approach solves the problem of how to choose the prior over the models and automates sensitivity analysis. We discuss various CMA algorithms for building an ensemble of logistic regressors characterized by different sets of covariates. We show how CMA can be appropriately tuned to the case in which one is prior-ignorant and to the case in which instead domain knowledge is available. CMA detects prior-dependent instances, namely instances in which a different class is more probable depending on the prior over the models. On such instances CMA suspends the judgment, returning multiple classes. We thoroughly compare different BMA and CMA variants on a real case study, predicting presence of Alpine marmot burrows in an Alpine valley. We find that BMA is almost a random guesser on the instances recognized as prior-dependent by CMA.     

The steiner tree packing problem in VLSI design

In this paper we describe several versions of the routing problem arising in VLSI design and indicate how the Steiner tree packing problem can be used to model these problems mathematically. We focus on switchbox routing problems and provide integer programming formulations for routing in the knock-knee and in the Manhattan model. We give a brief sketch of cutting plane algorithms that we developed and implemented for these two models. We report on computational experiments using standard test instances. Our codes are able to determine optimum solutions in most cases, and in particular, we can show that some of the instances have no feasible solution if Manhattan routing is used instead of knock-knee routing.     

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.     

Master physician scheduling problem

We study a real-world problem arising from the operations of a hospital service provider, which we term the master physician scheduling problem. It is a planning problem of assigning physicians’ full range of day-to-day duties (including surgery, clinics, scopes, calls, administration) to the defined time slots/shifts over a time horizon, incorporating a large number of constraints and complex physician preferences. The goals are to satisfy as many physicians’ preferences and duty requirements as possible while ensuring optimum usage of available resources. We propose mathematical programming models that represent different variants of this problem. The models were tested on a real case from the Surgery Department of a local government hospital, as well as on randomly generated problem instances. The computational results are reported together with analysis on the optimal solutions obtained. For large-scale instances that could not be solved by the exact method, we propose a heuristic algorithm to generate good solutions.     

An improved two-stage optimization-based framework for unequal-areas facility layout

The unequal-areas facility layout problem is concerned with finding the optimal arrangement of a given number of non-overlapping indivisible departments with unequal area requirements within a facility. We present an improved optimization-based framework for efficiently finding competitive solutions for this problem. The framework is based on the combination of two mathematical optimization models. The first model is a nonlinear approximation of the problem that establishes the relative position of the departments within the facility, and the second model is an exact convex optimization formulation of the problem that determines the final layout. Aspect ratio constraints on the departments are taken into account by both models. Our computational results show that the proposed framework is computationally efficient and consistently produces competitive, and often improved, layouts for well-known instances from the literature as well as for new large-scale instances with up to 100 departments.     

Fock空间上径向函数诱导的Toeplitz算子

本文讨论了Fock空间上以径向函数和拟齐次函数为符号的Toeplitz算子的代数性质,给出了两个以径向函数为符号的Toeplitz算子的积仍为Toeplitz算子的充分必要条件,并且研究了以拟齐次函数为符号的Toeplitz算子的交换性.     

Human resources management at a marine container terminal

We consider the manpower planning problem in the real context of a marine container terminal. The main features of this problem are the uncertainty of workforce demand and the need of ensuring a time continuous efficiency of the terminal, which enforces to decompose the problem into two phases: a long-period planning first and then a daily planning.We propose mathematical programming models for both problems and suitably tailor them to the container terminal at the Gioia Tauro port. We derive solution algorithms by exploiting the mathematical properties of the models: a heuristic approach to a set-covering type problem for the long-term planning, and a branch-and-bound algorithm for the short-term planning. Finally, we report computational results on some real instances.     

Models and algorithms for a staff scheduling problem

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months. Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59     

Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem

The routing and wavelength assignment (RWA) problem typically occurs in wavelength division multiplexing optical networks. Given a number of available wavelengths, we consider here the problem of maximising the number of accepted connections with respect to the clash and continuity constraints. We first propose a new strategy which combines two existing models. This leads to an improved column generation scheme. We also present two heuristics to compute feasible solutions: a hybrid heuristic and the integer solution at the root node of the column generation. Our approaches are compared with the best existing results on a set of classic RWA instances.     

Integer programming models for the q-mode problem

The q-mode problem is a combinatorial optimization problem that requires partitioning of objects into clusters. We discuss theoretical properties of an existing mixed integer programming (MIP) model for this problem and offer alternative models and enhancements. Through a comprehensive experiment we investigate computational properties of these MIP models. This experiment reveals that, in practice, the MIP approach is more effective for instances containing strong natural clusters and it is not as effective for instances containing weak natural clusters. The experiment also reveals that one of the MIP models that we propose is more effective than the other models for solving larger instances of the problem.     

Structural properties and tractability results for linear synteny

The syntenic distance between two species is the minimum number of fusions, fissions, and translocations required to transform one genome into the other. The linear syntenic distance, a restricted form of this model, has been shown to be close to the syntenic distance. Both models are computationally difficult to compute and have resisted efficient approximation algorithms with non-trivial performance guarantees. In this paper, we prove that many useful properties of syntenic distance carry over to linear syntenic distance. We also give a reduction from the general linear synteny problem to the question of whether a given instance can be solved using the maximum possible number of translocations. Our main contribution is an algorithm exactly computing linear syntenic distance in nested instances of the problem. This is the first polynomial time algorithm exactly solving linear synteny for a non-trivial class of instances. It is based on a novel connection between the syntenic distance and a scheduling problem that has been studied in the operations research literature.     

Multi-stage stochastic programming models for provisioning cloud computing resources

We focus on the resource provisioning problem of a cloud consumer from an Infrastructure-as-a-Service type of cloud. The cloud provider offers two deployment options, which can be mixed and matched as appropriate. Cloud instances may be reserved for a fixed time period in advance at a smaller usage cost per hour but require a full commitment and payment for the entire contract duration. In contrast, on-demand instances reflect a pay-as-you-go policy at a premium. The trade-off between these two options is rooted in the inherent uncertainty in demand and price and makes it attractive to complement a base reserved capacity with on-demand capacity to hedge against the spikes in demand. This paper provides several novel multi-stage stochastic programming formulations to enable a cloud consumer to handle the cloud resource provisioning problem at a tactical level. We first formulate the cloud resource provisioning problem as a risk-neutral multi-stage stochastic program, which serves as the base model for further modeling variants. In our second set of models, we also incorporate a certain concept of system reliability. In particular, chance constraints integrated into the base formulation require a minimum service level met from reserved capacity, provide more visibility into the future available capacity, and smooth out expensive on-demand usage by hedging against possible demand fluctuations. An extensive computational study demonstrates the value of the proposed models by discussing computational performance, gleaning practical managerial insights from the analysis of the solutions of the proposed models, and quantifying the value of the stochastic solutions.     

An algorithm and upper bounds for the weighted maximal planar graph problem

In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.     

Classical and new heuristics for the open-shop problem: A computational evaluation

We study the problem of constructing minimum makespan schedules for the Open-Shop problem. This paper presents two new heuristics: the first one is a list scheduling algorithm with two priorities. The second is based on the construction of matchings in a bipartite graph. We develop several versions of these two heuristics. A computational evaluation shows that around 90% of randomly generated instances are solvable optimally, whereas classical (list scheduling) heuristics achieve less than 20% on average. Therefore, our algorithms make most Open-Shop instances easy to solve in practice, and this raises the problem of generating hard instances. We extend the evaluation to two kinds of such instances: the results are not so good, but remain better than classical heuristics.     

Finite sums of Toeplitz products on the Dirichlet space

On the Dirichlet space of the unit disk, we consider a class of operators which contain finite sums of products of two Toeplitz operators with harmonic symbols. We give characterizations of when an operator in that class is zero or compact. Also, we solve the zero product problem for products of finitely many Toeplitz operators with harmonic symbols.     

Relaxations and discretizations for the pooling problem

The pooling problem is a folklore NP-hard global optimization problem that finds applications in industries such as petrochemical refining, wastewater treatment and mining. This paper assimilates the vast literature on this problem that is dispersed over different areas and gives new insights on prevalent techniques. We also present new ideas for computing dual bounds on the global optimum by solving high-dimensional linear programs. Finally, we propose discretization methods for inner approximating the feasible region and obtaining good primal bounds. Valid inequalities are derived for the discretized models, which are formulated as mixed integer linear programs. The strength of our relaxations and usefulness of our discretizations is empirically validated on random test instances. We report best known primal bounds on some of the large-scale instances.     

The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach

Expressways in China make use of the toll-by-weight scheme, in which expressway tolls are collected based on the weight and traveling distance of the vehicle. Most vehicle routing models assume that the cost of traversing each edge is equivalent to edge length or some constant; as a result, such models cannot be practically applied to the Chinese expressway transportation system. This study addresses a new single vehicle routing problem that takes the vehicle’s (laden and unladen) weight into account. To solve this problem exactly, we provide a branch-and-bound algorithm with a provably valid lower bound measure, along with five dominance checkers for additional pruning. We analyze our algorithm using instances generated from standard TSP test cases, as well as two new sets of test cases based on real expressway information from the Gansu and Jiangxi provinces in China. The algorithm can be applied to any toll scheme in which the toll per unit distance monotonically increases with weight, even if the toll function is non-linear.     

An algorithm for computing the distance between two circular disks

This paper presents an algorithm for computing the distance between two circular disks in three-dimensional space. A Kurush–Kuhn–Tucker (KKT) approach is used to solve the problem. We show that when the optimal points are not both at the borders of disks, the solutions of the KKT equations can be obtained in closed-form. For the case where the points are at the circumferences, the problem has no analytical solutions [IBM J. Res. Develop. 34 (5) (1990)]. Instead, we propose for the latter case an iterative algorithm based on computing the distance between a fixed point and a circle. We also show that the point–circle distance problem is solvable in closed-form, and the convergence of the numerical algorithm is linear.