The Weight Function Lemma for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble byt a vertex. Deciding if the pebbling number is at most k is \(\Pi _2^\mathsf{P}\)-complete. In this paper we develop a tool, called the Weight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply the Weight Function Lemma to several specific graphs, including the Petersen, Lemke, \(4\mathrm{th}\) weak Bruhat, and Lemke squared, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. In doing so we partly answer a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.     

Hard and soft constraints in linear programming

The linear programme and its constraints are split into two parts. The first consists of the traditional structure, the second being akin to goal programming. SOFT constraints are weighted relative to each other and then approximately weighted relative to the HARD constraints. The LP is run four times giving different emphasis to the SOFT and HARD constraints. The manager requesting the LP has then to decide which gives the most appropriate solution.     

基于0-1半无限规划的新产品开发计划方法

开发新产品,加速产品更新换代,是企业持续经营和不断发展的重要手段.近年来随着CIMS技术的不断发展,生产管理集成化程度的提高,只对产品作定性的分析已远远不能满足企业发展的需要.本文提出一种新产品开发计划的定量分析方法.该方法将所有产品分为四种具有不同收益曲线与参数的产品类型.每种类型产品的曲线参数由其经济特性确定.在产品量化描述的基础上,给出了一种利用0-1半无限规划(0-1 SIP)制订新产品开发计划的数学模型方法.     

The use of edge-directions and linear programming to enumerate vertices

Given a list of vectors that contains directions of the edges of a given polytope ℘ and the availability of an algorithm that solves linear programs over ℘, we describe a method for enumerating the vertices of ℘; in particular, the method is adaptable to polytopes which are presented as (linear) projections of polytopes having linear inequality representation. Polynomial complexity bounds under both the real and the binary computation models are derived when the dimension of the polytope is fixed and the given LP algorithm is polynomial. Dedicated to Professor Frank K. Hwang on the occasion of his sixty fifth birthday. Supported in part by a grant from ISF—the Israel Science Foundation, by a VPR grant at the Technion and by the Fund for the Promotion of Research at the Technion.     

区间线性规划的标准型及其最优值区间

定义了区间线性规划的标准型. 研究求解标准型区间线性规划的最好最优值和最差最 优值,从而确定其最优值区间. 分别对区间目标函数、区间不等式约束和区间等式约束作了讨 论. 基于此分别构造了求解区间线性规划最好最优值和最差最优值的确定型线性规划模型. 最 后给出一个算例并对一些特殊情况作了补充说明     

Strengthened 0-1 linear formulation for the daily satellite mission planning

In this paper, we compare several 0-1 linear programs for solving the satellite mission planning problem. We prove that one of them presents a smaller integrality gap. Our explanation is based on stable set polytope formulations for perfect graphs.     

Mixed integer (0–1) fractional programming for decision support in paper production industry

This paper presents an effective and efficient method for solving a special class of mixed integer fractional programming (FP) problems. We take a classical reformulation approach for continuous FP as a starting point and extend it for solving a more general class of mixed integer (0–1) fractional programming problems.To stress the practical relevance of the research we focus on a real-life application in paper production industry. The constantly advancing physical knowledge of large scale pulp and paper production did have a substantial impact on an existing DSS in which mixed integer (0–1) fractional programming is introduced. We show that the motivation to solve a real-life fractional programming problem can provide the basis for a new approach in a new context that has an added value of its own, even outside the given application area. We describe the main characteristics of the DSS, the necessity to develop a non-iterative solution procedure and demonstrate both the effectiveness and efficiency of the proposed approach from practical data sets.     

A linear programming based heuristic algorithm for charge and discharge scheduling of electric vehicles in a building energy management system

Electric vehicles (EVs) are becoming an attractive alternative to gasoline vehicles owing to the increase of greenhouse gas emissions and gasoline prices. EVs are also expected to function as battery storages for stabilizing large fluctuations in the power grid through the vehicle-to-grid power system, which requires smart charge and discharge scheduling algorithms. In this paper, we develop a linear programming based heuristic algorithm on a time–space network model for charge and discharge scheduling of EVs. We also develop an improved two-stage heuristic algorithm to cope with uncertain demands and departure times of EVs, and evaluate the effect of the smart charge and discharge scheduling of EVs on a peak load reduction in a building energy management system.     

An interactive decision support system for an aggregate production planning model based on multiple criteria mixed integer linear programming

In this paper, we present an aggregate production planning (APP) model applied to a Portuguese firm that produces construction materials. A multiple criteria mixed integer linear programming (MCMILP) model is developed with the following performance criteria: (1) maximize profit, (2) minimize late orders, and (3) minimize work force level changes. It includes certain operational features such as partial inflexibility of the work force, legal restrictions on workload, work force size (workers to be hired and downsized), workers in training, and production and inventory capacity. The purpose is to determine the number of workers for each worker type, the number of overtime hours, the inventory level for each product category, and the level of subcontracting in order to meet the forecasted demand for a planning period of 12 months. Additionally, a decision support system (DSS) based on the MCMILP model is proposed. It will help practitioners find the “best” solution for an APP problem without having to familiarize themselves with the mathematical complexities associated with the model. An example to illustrate the use of the DSS is also included.     

Lower bounds for positive semidefinite zero forcing and their applications

The positive semidefinite zero forcing number of a graph is a parameter that is important in the study of minimum rank problems. In this paper, we focus on the algorithmic aspects of computing this parameter. We prove that it is NP-complete to find the positive semidefinite zero forcing number of a given graph, and this problem remains NP-complete even for graphs with maximum vertex degree 7. We present a linear time algorithm for computing the positive semidefinite zero forcing number of generalized series–parallel graphs. We introduce the constrained tree cover number and apply it to improve lower bounds for positive semidefinite zero forcing. We also give formulas for the constrained tree cover number and the tree cover number on graphs with special structures.     

New bounds for locally irregular chromatic index of bipartite and subcubic graphs

A graph is locally irregular if the neighbors of every vertex v have degrees distinct from the degree of v. A locally irregular edge-coloring of a graph G is an (improper) edge-coloring such that the graph induced on the edges of any color class is locally irregular. It is conjectured that three colors suffice for a locally irregular edge-coloring. In the paper, we develop a method using which we prove four colors are enough for a locally irregular edge-coloring of any subcubic graph admiting such a coloring. We believe that our method can be further extended to prove the tight bound of three colors for such graphs. Furthermore, using a combination of existing results, we present an improvement of the bounds for bipartite graphs and general graphs, setting the best upper bounds to 7 and 220, respectively.     

Linear programming and financial cost models for industrial enterprises

Linear programming models of complex interrelated manufacturing enterprises have improved production planning decisions. With a linear programming formulation, the planning engineer concerned with specifying levels of production activity need not be concerned with cost accounting formulations of product costs to make his production decisions. He is only concerned with examining alternative production activities in terms of the added production costs the activity incurs, and the amount of product that is fed or consumed. The financial analyst, however, is concerned with development of budgetted average product costs. He must roll the costs of feed and intermediate products down to the final stage products. This paper bridges these two interests by demonstrating a methodology for the direct translation of the solution of the linear programming model to the development of rolled product standard costs.     

Online graph exploration algorithms for cycles and trees by multiple searchers

This paper deals with online graph exploration problems by multiple searchers. The information on the graph is given online. As the exploration proceeds, searchers gain more information on the graph. Assuming an appropriate communication model among searchers, searchers can share the information about the environment. Thus, a searcher must decide which vertex to visit next based on the partial information on the graph gained so far by searchers. We assume that all searchers initially start the exploration at the origin vertex, and the goal is that each vertex is visited by at least one searcher and all searchers finally return to the origin vertex. The objective is to minimize the time when the goal is achieved. We study the case of cycles and trees. For the former, we give an optimal online exploration algorithm in terms of competitive ratio, and for the latter, we also give an online exploration algorithm which is optimal among greedy algorithms.     

Note on power propagation time and lower bounds for the power domination number

We present a counterexample to a lower bound for the power domination number given in Liao (J Comb Optim 31:725–742, 2016). We also define the power propagation time, using the power domination propagation ideas in Liao and the (zero forcing) propagation time in Hogben et al. (Discrete Appl Math 160:1994–2005, 2012).