The flow circulation sharing problem

The flow circulation sharing problem is defined as a network flow circulation problem with a maximin objective function. The arcs in the network are partitioned into regular arcs and tradeoff arcs where each tradeoff arc has a non-decreasing tradeoff function associated with it. All arcs have lower and upper bounds on their flow while the value of the smallest tradeoff function is maximized. The model is useful in equitable resource allocation problems over time which is illustrated in a coal strike example and a submarine assignment example. Some properties including optimality conditions are developed. Each cut in the network defines a knapsack sharing problem which leads to an optimality condition similar to the max flow/min cut theorem. An efficient algorithm for both the continuous and integer versions of the flow circulation sharing problem is developed and computational experience given. In addition, efficient algorithms are developed for problems where some of the arcs have infinite flow upper bounds.     

Algorithm for minimizing weighted earliness penalty in single-machine problem

In this paper, the problem of minimizing the weighted earliness penalty in a single-machine scheduling problem is addressed. For this problem, every job is assumed to be available at time zero and must be completed before or on its deadline. No tardy job is allowed. Each job has its own earliness penalty and deadline. The paper identifies several local optimality conditions for sequencing of adjacent jobs. A heuristic algorithm is developed based on these local optimality conditions. Sample problems are solved and the solutions obtained from the heuristic are compared to solutions obtained from the heuristics developed by Chand and Schneeberger. Also, comparisons are performed between the solutions obtained from the heuristic and the optimal solutions obtained from a mathematical modeling approach for problems involving 10 and 15 jobs. The results show that the developed heuristic produces solutions close to optimal in small size problems, and it also outperforms the Chand and Schneeberger's method.     

Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure

In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.     

An Exact Procedure for the Resource-Constrained Weighted Earliness–Tardiness Project Scheduling Problem

In this paper we study the resource-constrained project scheduling problem with weighted earliness–tardinesss penalty costs. Project activities are assumed to have a known deterministic due date, a unit earliness as well as a unit tardiness penalty cost and constant renewable resource requirements. The objective is to schedule the activities in order to minimize the total weighted earliness–tardinesss penalty cost of the project subject to the finish–start precedence constraints and the constant renewable resource availability constraints. With these features the problem becomes highly attractive in just-in-time environments.We introduce a depth-first branch-and-bound algorithm which makes use of extra precedence relations to resolve resource conflicts and relies on a fast recursive search algorithm for the unconstrained weighted earliness–tardinesss problem to compute lower bounds. The procedure has been coded in Visual C++, version 4.0 under Windows NT. Both the recursive search algorithm and the branch-and-bound procedure have been validated on a randomly generated problem set.     

Inexact-Restoration Algorithm for Constrained Optimization1

We introduce a new model algorithm for solving nonlinear programming problems. No slack variables are introduced for dealing with inequality constraints. Each iteration of the method proceeds in two phases. In the first phase, feasibility of the current iterate is improved; in second phase, the objective function value is reduced in an approximate feasible set. The point that results from the second phase is compared with the current point using a nonsmooth merit function that combines feasibility and optimality. This merit function includes a penalty parameter that changes between consecutive iterations. A suitable updating procedure for this penalty parameter is included by means of which it can be increased or decreased along consecutive iterations. The conditions for feasibility improvement at the first phase and for optimality improvement at the second phase are mild, and large-scale implementation of the resulting method is possible. We prove that, under suitable conditions, which do not include regularity or existence of second derivatives, all the limit points of an infinite sequence generated by the algorithm are feasible, and that a suitable optimality measure can be made as small as desired. The algorithm is implemented and tested against the LANCELOT algorithm using a set of hard-spheres problems.     

Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs

We consider two linear project time–cost tradeoff problems with multiple milestones. Unless a milestone is completed on time, penalty costs for tardiness may be imposed. However, these penalty costs can be avoided by compressing the processing times of certain jobs that require additional resources or costs. Our model describes these penalty costs as the total weighted number of tardy milestone. The first problem tries to minimize the total weighted number of tardy milestones within the budget for total compression costs, while the second problem tries to minimize the total weighted number of tardy milestones plus total compression costs. We develop a linear programming formulation for the case with a fixed number of milestones. For the case with an arbitrary number of milestones, we show that under completely ordered jobs, the first problem is NP-hard in the ordinary sense while the second problem is polynomially solvable.     

Partially Strictly Monotone and Nonlinear Penalty Functions for Constrained Mathematical Programs

We introduce the concept of partially strictly monotone functions and apply it to construct a class of nonlinear penalty functions for a constrained optimization problem. This class of nonlinear penalty functions includes some (nonlinear) penalty functions currently used in the literature as special cases. Assuming that the perturbation function is lower semi-continuous, we prove that the sequence of optimal values of nonlinear penalty problems converges to that of the original constrained optimization problem. First-order and second-order necessary optimality conditions of nonlinear penalty problems are derived by converting the optimality of penalty problems into that of a smooth constrained vector optimization problem. This approach allows for a concise derivation of optimality conditions of nonlinear penalty problems. Finally, we prove that each limit point of the second-order stationary points of the nonlinear penalty problems is a second-order stationary point of the original constrained optimization problem.     

Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

Fractional multi-commodity flow problem: Duality and optimality conditions

This paper deals with multi-commodity flow problem with fractional objective function. The optimality conditions and the duality concepts of this problem are given. For this aim, the fractional linear programming formulation of this problem is considered and the weak duality, the strong direct duality and the weak complementary slackness theorems are proved applying the traditional duality theory of linear programming problems which is different from same results in Chadha and Chadha (2007) [1]. In addition, a strong (strict) complementary slackness theorem is derived which is firstly presented based on the best of our knowledge. These theorems are transformed in order to find the new reduced costs for fractional multi-commodity flow problem. These parameters can be used to construct some algorithms for considered multi-commodity flow problem in a direct manner. Throughout the paper, the boundedness of the primal feasible set is reduced to a weaker assumption about solvability of primal problem which is another contribution of this paper. Finally, a real world application of the fractional multi-commodity flow problem is presented.     

Design of a recovery network for WEEE collection: the case of Galicia,Spain

This research aims to optimize the design of the reverse logistic network for the collection of Waste of Electric and Electronic Equipment (WEEE), in the Spanish region of Galicia. As a basis for our study a three-phase hierarchical approach is proposed. In the first phase a facility location problem is formulated and solved by means of a mixed integer linear programming; in the second phase a new integer programming formulation for the corresponding heterogeneous fleet vehicle routing problem is presented, and a savings-based heuristic algorithm is developed to efficiently solve the related collection routing problems; in the third phase a simulation study is performed on the collection routes in order to assess the overall performance of the recovery system. The results show a good performance of the proposed procedure, and an improved configuration of the recovery network compared to the one currently in use (particularly transportation costs are reduced by 29.2%).     

Generalized K-T conditions and penalty functions for quasidifferentiable programming

In this paper,a quasidifferentiable programming problem with inequality constraintsis considered. First,a general form of optimality conditions for this problem is glven,which contains the results of Luderer,Kuntz and Scholtes. Next,a new generalized K-T condition is derived. The new optimality condition doesn‘t use Luderer‘s regularity assumption and ita Lagrangian multipliers don‘t depend on the particular elements in the superdifferentials of the object function and constraint functions, Finally,a penalty function for the prohlem is studied. Sufficient conditions of the penalty function attaining a global minimum are obtained.     

Going beyond the basics: creating and inspiring problem solvers

This paper offers a general discussion of a complex student project used in a first-semester, first-year mathematics course that goes beyond the basics taught in the class and inspires creative problem solving. The project requires the student to model the transition of vehicles among regions of a vehicle rental company. A penalty cost is introduced when the regional inventory drops below an established threshold. The project allows the company to move vehicles by rail among regions to reduce or alleviate the penalty cost. In this phase of the project, student teams attempt to minimize the total cost to the company (penalty cost plus transportation costs), thus searching for an ‘optimal’ solution. The project allows the students to use technology to numerically develop an approximate solution to a problem that is easily understood, but whose analytical solution goes well beyond the scope of the course.     

On the optimal control of stochastic systems with an exponential-of-integral performance index

In this paper a theory of optimal control is developed for stochastic systems whose performance is measured by the exponential of an integral form. Such a formulation of the cost function is shown to be not only general and useful but also analytically tractable. Starting with very general classes of stochastic systems, optimality conditions are obtained which exploit the multiplicative decomposability of the exponential-of-integral form. Specializing to partially observed systems of stochastic differential equations with Brownian Motion disturbances, optimality conditions are obtained which parallel those for systems with integral costs. Also treated are the special cases of linear systems with exponential of quadratic costs for which explicit optimal controls are obtainable. In addition, several general results of independent interest are obtained, which concern optimality of stochastic systems.     

Quartic Formulation of Standard Quadratic Optimization Problems

A standard quadratic optimization problem (StQP) consists of finding the largest or smallest value of a (possibly indefinite) quadratic form over the standard simplex which is the intersection of a hyperplane with the positive orthant. This NP-hard problem has several immediate real-world applications like the Maximum-Clique Problem, and it also occurs in a natural way as a subproblem in quadratic programming with linear constraints. To get rid of the (sign) constraints, we propose a quartic reformulation of StQPs, which is a special case (degree four) of a homogeneous program over the unit sphere. It turns out that while KKT points are not exactly corresponding to each other, there is a one-to-one correspondence between feasible points of the StQP satisfying second-order necessary optimality conditions, to the counterparts in the quartic homogeneous formulation. We supplement this study by showing how exact penalty approaches can be used for finding local solutions satisfying second-order necessary optimality conditions to the quartic problem: we show that the level sets of the penalty function are bounded for a finite value of the penalty parameter which can be fixed in advance, thus establishing exact equivalence of the constrained quartic problem with the unconstrained penalized version.     

Maximum network flows with concave gains

This paper deals with a generalized maximum flow problem with concave gains, which is a nonlinear network optimization problem. Optimality conditions and an algorithm for this problem are presented. The optimality conditions are extended from the corresponding results for the linear gain case. The algorithm is based on the scaled piecewise linear approximation and on the fat path algorithm described by Goldberg, Plotkin and Tardos for linear gain cases. The proposed algorithm solves a problem with piecewise linear concave gains faster than the naive solution by adding parallel arcs. Supported by a Grant-in-Aid for Scientific Research (No. 13780351 and No.14380188) from The Ministry of Education, Culture, Sports, Science and Technology of Japan.     

Financial networks with intermediation: Risk management with variable weights

In this paper, we develop a framework for the modeling, analysis, and computation of solutions to multitiered financial network problems with intermediaries in which both the sources of financial funds as well as the intermediaries are multicriteria decision-makers. In particular, we assume that these decision-makers seek not only to maximize their net revenues but also to minimize risk with the risk being penalized by a variable weight. We make explicit the behavior of the various decision-makers, including the consumers at the demand markets for the financial products. We derive the optimality conditions, and demonstrate that the governing equilibrium conditions of the financial network economy can be formulated as a finite-dimensional variational inequality problem. Qualitative properties of the equilibrium financial flow and price pattern are provided. A computational procedure that exploits the network structure of the problem is proposed and then applied to several numerical examples.     

A parametric algorithm for convex cost network flow and related problems

The convex cost network flow problem is to determine the minimum cost flow in a network when cost of flow over each arc is given by a piecewise linear convex function. In this paper, we develop a parametric algorithm for the convex cost network flow problem. We define the concept of optimum basis structure for the convex cost network flow problem. The optimum basis structure is then used to parametrize v, the flow to be transsshipped from source to sink. The resulting algorithm successively augments the flow on the shortest paths from source to sink which are implicitly enumerated by the algorithm. The algorithm is shown to be polynomially bounded. Computational results are presented to demonstrate the efficiency of the algorithm in solving large size problems. We also show how this algorithm can be used to (i) obtain the project cost curve of a CPM network with convex time-cost tradeoff functions; (ii) determine maximum flow in a network with concave gain functions; (iii) determine optimum capacity expansion of a network having convex arc capacity expansion costs.     

多商品流电子商务供应链网络模型

针对多商品流三层供应链网络模型,将电子商务整合到多商品流供应链网络中,导出了每层网络代理商或决策者的最优性条件,给出了问题的变分不等式形式,得到了系统达到均衡的条件,给出了具体算例并进行了求解.     

Newsvendor equations for production networks

We consider production networks with stochastic activity leadtimes. When activities finish early holding costs are incurred and when end products are delivered late penalty costs are incurred. Objective is to find the activity start and finish times that minimize the total cost. We introduce the concept of a tardy path and derive the optimality equations for each node in the network. We show that under the optimal solution, for a set of nodes the tardiness probability satisfies the Newsvendor equations.     

Project Management Duration/Resource Tradeoff Analysis: an Application of the Cut Search Approach

The paper presents an application oriented procedure for solving the project management duration/resource tradeoff problem. A procedure is presented for reducing a project from a normal to a crash duration state at a minimum amount of additional resource expenditure assuming a linear utilization functions. The procedure is network based using a graphical Cut Search Approach to locate the minimal resource level at each reduction in total project duration. Activity-on-arc networks and flow networks are utilized. The paper is presented for practical application and for conceptual development as compared to a theoretical treatment.