FPT-algorithms for some problems related to integer programming

This paper studies a new version of the location problem called the mixed center location problem. Let P be a set of n points in the plane. We first consider the mixed 2-center problem, where one of the centers must be in P, and we solve it in \(O(n^2\log n)\) time. Second, we consider the mixed k-center problem, where m of the centers are in P, and we solve it in \(O(n^{m+O(\sqrt{k-m})})\) time. Motivated by two practical constraints, we propose two variations of the problem. Third, we present a 2-approximation algorithm and three heuristics solving the mixed k-center problem (\(k>2\)).     

Trim loss and related problems

Because of the diversity of the structures of real-world trim loss (or cutting stock) problems there exist no general standard methods for solving these problems. Hence many solution methods for trim loss problems have been developed in practice, especially heuristics. Since these methods are strongly based on the particular problems to which they are applied, the study of papers on problems with a comparable structure may prove helpful. In this paper a detailed catalogue of criteria for characterization of real-world trim loss problems is developed in a differentiated and systematic manner. The main criteria are: dimension, planning situation, goal, restrictions and solution approach. The proposed system of classification is based on 34 case studies found in the relevant literature. The classification of these case studies is represented by means of a ‘classification schedule’. In view of existing formal similarities the classification system can also be of importance for (bin) packing and loading as well as some assortment problems.     

Two ways to handle dependent uncertainties in multi-criteria decision problems

We consider multi-criteria group decision-making problems, where the decision makers (DMs) want to identify their most preferred alternative(s) based on uncertain or inaccurate criteria measurements. In many real-life problems the uncertainties may be dependent. In this paper, we focus on multicriteria decision-making (MCDM) problems where the criteria and their uncertainties are computed using a stochastic simulation model. The model is based on decision variables and stochastic parameters with given distributions. The simulation model determines for the criteria a joint probability distribution, which quantifies the uncertainties and their dependencies. We present and compare two methods for treating the uncertainty and dependency information within the SMAA-2 multi-criteria decision aid method. The first method applies directly the discrete sample generated by the simulation model. The second method is based on using a multivariate Gaussian distribution. We demonstrate the methods using a decision support model for a retailer operating in the deregulated European electricity market.     

The extremal spectral radii of $$$$-uniform supertrees

In this paper, we study some extremal problems of three kinds of spectral radii of \(k\)-uniform hypergraphs (the adjacency spectral radius, the signless Laplacian spectral radius and the incidence \(Q\)-spectral radius). We call a connected and acyclic \(k\)-uniform hypergraph a supertree. We introduce the operation of “moving edges” for hypergraphs, together with the two special cases of this operation: the edge-releasing operation and the total grafting operation. By studying the perturbation of these kinds of spectral radii of hypergraphs under these operations, we prove that for all these three kinds of spectral radii, the hyperstar \(\mathcal {S}_{n,k}\) attains uniquely the maximum spectral radius among all \(k\)-uniform supertrees on \(n\) vertices. We also determine the unique \(k\)-uniform supertree on \(n\) vertices with the second largest spectral radius (for these three kinds of spectral radii). We also prove that for all these three kinds of spectral radii, the loose path \(\mathcal {P}_{n,k}\) attains uniquely the minimum spectral radius among all \(k\)-th power hypertrees of \(n\) vertices. Some bounds on the incidence \(Q\)-spectral radius are given. The relation between the incidence \(Q\)-spectral radius and the spectral radius of the matrix product of the incidence matrix and its transpose is discussed.     

Risk averse demand selection with all-or-nothing orders

Consider a firm that operates in consecutive single selling seasons, delivering its products across several markets with unique revenue and uncertain demands in each market. Using a profit maximization approach based on a newsvendor-type model, the firm may still incur several losses across consecutive periods in the short run. Risk analysis with demand selection has been modeled where customer/market demands follow a normal distribution. Often a firm faces a set of potential unconfirmed orders, where each order will either come in at a predefined level or it will not come in at all. In this paper, we consider these all-or-nothing (AON) demands and provide insights into their effect on expected profit and the frequency of extremely costly procurement policies. Instead of solely identifying the market/demand set and procurement quantity that maximizes expected profit, we use a conditional value-at-risk approach that allows a decision maker to control the number of profitable but risky demands to consider in the overall procurement policy. This approach is compared against an expected profit objective, and several managerial insights are provided.     

Stochastic orders and non-Gaussian risk factor models

The main results of this paper are monotonicity statements about the risk measures value-at-risk (VaR) and tail value-at-risk (TVaR) with respect to the parameters of single and multi risk factor models, which are standard models for the quantification of credit and insurance risk. In the context of single risk factor models, non-Gaussian distributed latent risk factors are allowed. It is shown that the TVaR increases with increasing claim amounts, probabilities of claims and correlations, whereas the VaR is in general not monotone in the correlation parameters. To compare the aggregated risks arising from single and multi risk factor models, the usual stochastic order and the increasing convex order are used in this paper, since these stochastic orders can be interpreted as being induced by the VaR-concept and the TVaR-concept, respectively. To derive monotonicity statements about these risk measures, properties of several further stochastic orders are used and their relation to the usual stochastic order and to the increasing convex order are applied.     

Some extremal results on the colorful monochromatic vertex-connectivity of a graph

A path in a vertex-colored graph is called a vertex-monochromatic path if its internal vertices have the same color. A vertex-coloring of a graph is a monochromatic vertex-connection coloring (MVC-coloring for short), if there is a vertex-monochromatic path joining any two vertices in the graph. For a connected graph G, the monochromatic vertex-connection number, denoted by mvc(G), is defined to be the maximum number of colors used in an MVC-coloring of G. These concepts of vertex-version are natural generalizations of the colorful monochromatic connectivity of edge-version, introduced by Caro and Yuster (Discrete Math 311:1786–1792, 2011). In this paper, we mainly investigate the Erd?s–Gallai-type problems for the monochromatic vertex-connection number mvc(G) and completely determine the exact value. Moreover, the Nordhaus–Gaddum-type inequality for mvc(G) is also given.     

Some extremal properties of the multiplicatively weighted Harary index of a graph

Let \(G=(V_G, E_G)\) be a simple connected graph. The multiplicatively weighted Harary index of \(G\) is defined as \(H_M(G)=\sum _{\{u,v\}\subseteq V_G}\delta _G(u)\delta _G(v)\frac{1}{d_G(u,v)},\) where \(\delta _G(u)\) is the vertex degree of \(u\) and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G.\) This novel invariant is in fact the modification of the Harary index in which the contributions of vertex pairs are weighted by the product of their degrees. Deng et al. (J Comb Optim 2014, doi: 10.1007/s10878-013-9698-5) determined the extremal values on \(H_M\) of graphs among \(n\)-vertex trees (resp. unicyclic graphs). In this paper, as a continuance of it, the monotonicity of \(H_M(G)\) under some graph transformations were studied. Using these nice mathematical properties, the extremal graphs among \(n\)-vertex trees with given graphic parameters, such as pendants, matching number, domination number, diameter, vertex bipartition, et al. are characterized, respectively. Some sharp upper bounds on the multiplicatively weighted Harary index of trees with given parameters are determined.     

A new approach to solve open-partition problems

A partition problem in one-dimensional space is to seek a partition of a set of numbers that maximizes a given objective function. In some partition problems, the partition size, i.e., the number of nonempty parts in a partition, is fixed; while in others, the size can vary arbitrarily. We call the former the size-partition problem and the latter the open-partition problem. In general, it is much harder to solve open problems since the objective functions depend on size. In this paper, we propose a new approach by allowing empty parts and transform the open problem into a size problem allowing empty parts, called a relaxed-size problem. While the sortability theory has been established in the literature as a powerful tool to attack size partition problems, we develop the sortability theory for relaxed-size problems as a medium to solve open problems.     

Approaches to real world two-dimensional cutting problems

We consider a real world generalization of the 2-Dimensional Guillotine Cutting Stock Problem arising in the wooden board cutting industry. A set of rectangular items has to be cut from rectangular stock boards, available in multiple formats. In addition to the classical objective of trim loss minimization, the problem also asks for the maximization of the cutting equipment productivity, which can be obtained by cutting identical boards in parallel. We present several heuristic algorithms for the problem, explicitly considering the optimization of both objectives. The proposed methods, including fast heuristic algorithms, Integer Linear Programming models and a truncated Branch and Price algorithm, have increasing complexity and require increasing computational effort. Extensive computational experiments on a set of realistic instances from the industry show that high productivity of the cutting equipment can be obtained with a minimal increase in the total area of used boards. The experiments also show that the proposed algorithms perform extremely well when compared with four commercial software tools available for the solution of the problem.     

如何处理组织之间的磨擦与冲突

在管理社会事务的各个组织之间,有时也难免因为工作上的一些问题而发生磨擦与冲突。这些磨擦与冲突,一般可分为低级形态的和高级形态的。低级形态的,表现为不同的组织之间对于需要共同协作处理的事情,意见不相一致,态度不尽相同,组织的关系处于一种潜磨擦、潜冲突的状态;高级形态的,表现为因意见和态度不……     

On statistical bounds of heuristic solutions to location problems

Combinatorial optimization problems such as locating facilities frequently rely on heuristics to minimize the objective function. The optimum is often sought iteratively; a criterion is therefore necessary to be able to decide when the procedure attains such an optimum. Pre-setting the number of iterations is dominant in OR applications, however, the fact that the quality of the solution cannot be ascertained by pre-setting the number of iterations makes it less preferable. A small and, almost dormant, branch of the literature suggests usage of statistical principles to estimate the minimum and its bounds as a tool to decide upon the stopping criteria and also to evaluate the quality of the solution. In the current work we have examined the functioning of statistical bounds obtained from four different estimators using simulated annealing. P-median test problems taken from Beasley’s OR-library were used for the sake of testing. Our findings show that the Weibull estimator and 2nd order Jackknife estimators are preferable and the requirement of sample size to be about 10. It should be noted that reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality; we have therefore provided a simple statistic for checking the quality. The work finally concludes with an illustration of applying statistical bounds to the problem of locating 70 post distribution centers in a region in Sweden.     

Intuitive versus optimal solutions to some problems in distribution

This paper is concerned with the issue of assessing the relative performance of unaided decision-makers and model-based optimal solutions to managerial decision problems. This has important implications for project selection, research direction and management training. Some possible approaches designed to achieve such comparisons are examined and examples given. Some experimental studies are reported, set in the context of distribution management, which make use of one of the research strategies discussed.     

A multiple criteria decision-making model for justifying the acceptance of rush orders

Rush orders are immediate customer demands that exceed the expectation of a currently effective MPS (master production schedule). Decision-makers are often hesitant in the decision of accepting such orders. This paper presents a multiple criteria decision-making model for justifying the acceptance of rush orders for an assembly-to-order production system. Four criteria or production objectives are simultaneously considered and a multiple objective programming technique, the e-constraints approach, is adopted to solve the decision-making problem. This model could give the cost estimation for producing a rush order under various combinations of production objectives. The computed cost value could serve as a valuable reference for justifying the economics of accepting the rush order, and help to determine its pricing strategy.     

Analytic approaches to problems of a middle-sized defence department

The application of operational research to the problems of Canadian defence was very similar to that in Great Britain and the United States during World War II and through the 1950s. But because of the rapidly increasing costs of major weapon systems, since the 1960s systems analysis has been very thoroughly applied to the study of the large procurement programs, including far-reaching examination of their economic impact on the nation. Other problems of special interest to Canada which received analytical attention included peacekeeping and military involvement in activities such as maritime surveillance and search and rescue. Analytical studies have been extended into examination of logistics and manpower, and into economic, sociological, and strategic problems of concern to the Canadian defence department, including arms control. This type of research represents a considerable excursion from the original operational research, but is needed in the Canadian Department of National Defence.     

Cost-effective rehabilitation: Part 2--Approaches to patient management problems

Part one of this two-part series discussed general principles of cost-effective rehabilitation: Patients in rehabilitation programs should be working toward achievement of real-world functional goals. Goals should be realistic, and reachable in a reasonable amount of time. Rehabilitation services should be provided at the lowest safe and effective level of care appropriate to the patient's needs. Patients should be participating to their full potential in an active therapy program. Therapy intended to maintain a patient's current condition should be carried out by nonprofessionals who have had training sessions with rehabilitation professionals as needed. Discharge planning begins on the day of admission to the inpatient or outpatient rehabilitation program. This second of the two-part series will focus on individual patient management issues. It discusses circumstances in which the principles of cost-effective rehabilitation may need to be modified. It also discusses approaches to remedy patient management problems that may lead to excessive or ineffective utilization of rehabilitation services.     

An inverse approach to convex ordered median problems in trees

The convex ordered median problem is a generalization of the median, the k-centrum or the center problem. The task of the associated inverse problem is to change edge lengths at minimum cost such that a given vertex becomes an optimal solution of the location problem, i.e., an ordered median. It is shown that the problem is NP-hard even if the underlying network is a tree and the ordered median problem is convex and either the vertex weights are all equal to 1 or the underlying problem is the k-centrum problem. For the special case of the inverse unit weight k-centrum problem a polynomial time algorithm is developed.