Scheduling subject to nonrenewable-resource constraints

Polynomially bounded solution methods are presented to solve a class of precedence constrained scheduling problems in which each job requires a certain amount of nonrenewable resource that is being consumed during its execution.     

Perturbation bounds for the linear least squares problem subject to linear inequality constraints

We study the effect on the solution to a linear least squares problem with linear inequality and equality constraints when the data defining the problem are perturbed. The existence and uniqueness of a solution are investigated. If the matrices involved have full rank, then a detailed bound is obtained by the duality theory for quadratic programming. Sufficient conditions are derived for an estimate of the perturbation in the solution to hold in terms of the largest perturbation in the data.     

Quasi-concave minimization subject to linear constraints

A finite algorithm is presented for solving the quasi-concave minimization problem subject to linear constraints. The concept of an extreme point is generalized to that of an extreme facet of a polyhedron. Then a search routine is developed for the detection of an extreme facet of the feasible region relative to the polyhedron defined by the current set of cuts. After identifying an extreme facet we cut it off by a cut developed for this purpose. We call this cut the facet cut. The method is both compatible with other cutting procedures and is finite..     

Uniform reciprocal approximation subject to coefficient constraints

In this paper best approximation by reciprocals of functions of a subspace U_n=span (u₁,...,u_n) satisfying coefficient constraints is considered. We present a characterization of best approximations. When (u₁,...,u_n) is a Descartes system an explicit characterization of best approximations by equioscillations is given. Existence and uniqueness results are shown. Moreover, the theory is applied to best approximaitons by reciprocals of polynomials.     

An integer programming approach for linear programs with probabilistic constraints

Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results which indicate that by using our strengthened formulations, instances that are considerably larger than have been considered before can be solved to optimality.     

Optimization of functionals subject to integral constraints

The classical method for optimizing a functional subject to an integral constraint is to introduce the Lagrange multiplier and apply the Euler-Lagrange equations to the augmented integrand. The Lagrange multiplier is a constant whose value is selected such that the integral constraint is satisfied. This value is frequently an eigenvalue of the boundary-value problem and is determined by a trial-and-error procedure. A new approach for solving this isoperimetric problem is presented. The Lagrange multiplier is introduced as a state variable and evaluated simultaneously with the optimum solution. A numerical example is given and is shown to have a large region of convergence.     

An algorithm for minimizing a differentiable function subject to box constraints and errors

We consider the problem of minimizing a differentiable function ofn parameters, with upper and lower bounds on the parameters. The motivation for this work comes from the optimization of the design of transient electrical circuits. In such optimization, the parameters are circuit elements, the bound constraints keep these parameters physically meaningful, and both the function and gradient evaluations contain errors. We describe a quasi-Newton algorithm for such problems. This algorithm handles the box constraints directly and approximates the given function locally by nonsingular quadratic functions. Numerical tests indicate that the algorithm can tolerate the errors, if the errors in the function and gradient are of the same relative size.This paper was presented at the SIAM National Meeting, Chicago, Illinois, 1976.This research was sponsored in part by the Air Force Office of Scientific Research (AFSC), United States Air Force, under Contract No. F44620-76-C-0022.     

Interactive multiple objective programming subject to flexible constraints

An interactive decision support system is introduced which aids in solving multiple objective programming problems subject to strict and flexible constraints. Integral part is an extension of a well-known fuzzy sets approach evaluating possible solutions by their degrees of membership to objectives and constraints. This approach is linked to classical multiple objective programming models. If the decision maker cannot determine membership functions a priori the system suggests functions dependent on the given information and interactive modifications are allowed.     

An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns

Daily, there are multiple situations where machines or workers must execute certain jobs. During a working day it may be that some workers or machines are not available to perform their activities during some time periods. When scheduling models are used in these situations, workers or machines are simply called “machines”, and the temporal absences of availability are known as “breakdowns”. This paper considers some of these cases studying stochastic scheduling models with several machines to perform activities. Machines are specialized and models are flow-shops where breakdowns are allowed. The paper proposes a general procedure that tries to solve these problems. The proposed approach converts breakdowns scheduling problems into a finite sequence of without-breakdowns problems. Thus, we consider random variables, which measure the length of availability periods and repair times, to study availability intervals of machines. We propose partial feasible schedules in these intervals and combine them to offer a final global solution to optimize the expected makespan. Computational experiences are also reported.     

Hölderian variational problems subject to integral constraints

We prove a necessary stationary condition for non-differentiable isoperimetric variational problems with scale derivatives defined on the class of Hölder continuous functions.     

Minimising total average cycle stock subject to practical constraints

Silver and Moon (J Opl Res Soc 50(8) (1999) 789–796) address the problem of minimising total average cycle stock subject to two practical constraints. They provide a dynamic programming formulation for obtaining an optimal solution and propose a simple and efficient heuristic algorithm. Hsieh (J Opl Res Soc 52(4) (2001) 463–470) proposes a 0–1 linear programming approach to the problem and a simple heuristic based on the relaxed 0–1 programming formulation. We show in this paper that the formulation of Hsieh can be improved for solving very large size instances of this inventory problem. So the mathematical approach is interesting for several reasons: the definition of the model is simple, its implementation is immediate by using a mathematical programming language together with a mixed integer programming software and the performance of the approach is excellent. Computational experiments carried out on the set of realistic examples considered in the above references are reported. We also show that the general framework for modelling given by mixed integer programming allows the initial model to be extended in several interesting directions.     

Scheduling subject to resource constraints: classification and complexity

In deterministic sequencing and scheduling problems, jobs are to be processed on machines of limited capacity. We consider an extension of this class of problems, in which the jobs require the use of additional scarce resources during their execution. A classification scheme for resource constraints is proposed and the computational complexity of the extended problem class is investigated in terms of this classification. Models involving parallel machines, unit-time jobs and the maximum completion time criterion are studied in detail; other models are briefly discussed.     

Optimal investment, consumption and retirement choice problem with disutility and subsistence consumption constraints

In this paper we consider a general optimal consumption-portfolio selection problem of an infinitely-lived agent whose consumption rate process is subject to subsistence constraints before retirement. That is, her consumption rate should be greater than or equal to some positive constant before retirement. We integrate three optimal decisions which are the optimal consumption, the optimal investment choice and the optimal stopping problem in which the agent chooses her retirement time in one model. We obtain the explicit forms of optimal policies using a martingale method and a variational inequality arising from the dual function of the optimal stopping problem. We treat the optimal retirement time as the first hitting time when her wealth exceeds a certain wealth level which will be determined by a free boundary value problem and duality approaches. We also derive closed forms of the optimal wealth processes before and after retirement. Some numerical examples are presented for the case of constant relative risk aversion (CRRA) utility class.     

Multidimensional investment problem

In this paper we demonstrate that the Riesz representation of excessive functions is a useful and enlightening tool to study optimal stopping problems. After a short general discussion of the Riesz representation we concretize to geometric Brownian motions. After this, a classical investment problem, also known as exchange-of-baskets-problem, is studied. It is seen that the boundary of the stopping region in this problem can be characterized as a unique solution of an integral equation arising immediately from the Riesz representation of the value function. The two-dimensional case is studied in more detail and a numerical algorithm is presented.     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

An efficient curvilinear method for the minimization of a nonlinear function subject to linear inequality constraints

An algorithm is presented that minimizes a continuously differentiable function in several variables subject to linear inequality constraints. At each step of the algorithm an arc is generated along which a move is performed until either a point yielding a sufficient descent in the function value is determined or a constraint boundary is encountered. The decision to delite a constraint from the list of active constraints is based upon periodic estimates of the Kuhn-Tucker multipliers. The curvilinear search paths are obtained by solving a linear approximation to the differential equation of the continuous steepest descent curve for the objective function on the equality constrained region defined by the constraints which are required to remain binding. If the Hessian matrix of the objective function has certain properties and if the constraint gradients are linearly independent, the sequence generated by the algorithm converges to a point satisfying the Kuhn-Tucker optimality conditions at a rate that is at least quadratic.     

An interior penalty approach to a large-scale discretized obstacle problem with nonlinear constraints

Numerical Algorithms - We propose an interior penalty method to solve a nonlinear obstacle problem arising from the discretization of an infinite-dimensional optimization problem. An interior...     

Non-monotone trust-region algorithms for nonlinear optimization subject to convex constraints

This paper presents two new trust-region methods for solving nonlinear optimization problems over convex feasible domains. These methods are distinguished by the fact that they do not enforce strict monotonicity of the objective function values at successive iterates. The algorithms are proved to be convergent to critical points of the problem from any starting point. Extensive numerical experiments show that this approach is competitive with the LANCELOT package.     

On the definity of quadratic forms subject to linear constraints

A short proof is given of the necessary and sufficient conditions for the positivity and nonnegativity of a quadratic form subject to linear constraints.