Covering partially directed graphs with directed paths

We consider graphs which contain both directed and undirected edges (partially directed graphs). We show that the problem of covering the edges of such graphs with a minimum number of edge-disjoint directed paths respecting the orientations of the directed edges is polynomially solvable. We exhibit a good characterization for this problem in the form of a min-max theorem. We introduce a more general problem including weights on possible orientations of the undirected edges. We show that this more general weighted formulation is equivalent to the weighted bipartite b-factor problem. This implies the existence of a strongly polynomial algorithm for this weighted generalization of Euler's problem to partially directed graphs (compare this with the negative results for the mixed Chinese postman problem). We also provide a compact linear programming formulation for the weighted generalization that we propose.     

A problem with a nonlocal,with respect to time,condition for multidimensional hyperbolic equations

We study a boundary-value problem for a hyperbolic equation with a nonlocal with respect to time-variable integral condition. We obtain sufficient conditions for unique solvability of the nonlocal problem. The proof is based on reduction of the nonlocal first-type condition to the second-type one. This allows to reduce the nonlocal problem to an operator equation. We show that unique solvability of the operator equation implies the existence of a unique solution to the problem.     

A dynamic uncapacitated lot-sizing problem with co-production

We consider an extension of the dynamic uncapacitated lot-sizing problem to account for co-production, where multiple products are produced simultaneously in a single production run. We formulate the problem as a mixed-integer linear programming problem. We then show that a variant of the well-known zero-inventory property holds for this problem, and use this property to extend a dynamic program given for the single-item lot-sizing to solve the problem with co-production. Finally, we provide an illustrative example for our approach.     

Optimal bundle pricing with monotonicity constraint

We consider the problem of pricing (digital) items in order to maximize the revenue obtainable from a set of bidders. We suggest a natural monotonicity constraint on bundle prices, show that the problem remains NP-hard, and we derive a PTAS. We also briefly discuss the highway pricing problem.     

Problem with integral condition for a partial differential equation of the first order with respect to time

We investigate the problem with inhomogeneous integral condition for a homogeneous partial differential equation of the first order with respect to time and, in the general case, of infinite order with respect to the space variable with constant coefficients. We prove the existence and uniqueness of a solution of the problem in a class of quasipolynomials of the special form. We construct a solution of this problem with the use of the differential-symbol method. In the case of existence of a nonunique solution of the problem, we propose formulas for the construction of a particular solution of the problem.     

The network equilibrium problem with mixed demand

We formulate the network equilibrium problem with mixed demand which generalizes the problems of network equilibrium with fixed and elastic demand. We prove the equilibrium conditions for this problem and propose some conditions of existence of a solution that are based on the coercivity property.We establish a connection between the problem of network equilibrium with mixed demand and the problem of auction equilibrium. The results of test calculations are presented for a model example.     

Eigenvibrations of a bar with elastically attached load

We study the problem on the eigenvibrations of a bar with an elastically attached load. The problem is reduced to finding the eigenvalues and eigenfunctions of an ordinary secondorder differential problem with a spectral parameter nonlinearly occurring in the boundary condition at the load attachment point. We prove the existence of countably many simple positive eigenvalues of the differential problem. The problem is approximated by a grid scheme of the finite element method. We study the convergence and accuracy of the approximate solutions.     

A problem with formal initial conditions for differential equations with constant pseudodifferential coefficients

We establish conditions for the unique existence of a solution of a problem with formal initial conditions. We investigate the problem of its solvability in the case where a solution is not unique.     

Quasilinear elliptic problems with multivalued terms

We study the quasilinear elliptic problem with multivalued terms.We consider the Dirichlet problem with a multivalued term appearing in the equation and a problem of Neumann type with a multivalued term appearing in the boundary condition. Our approach is based on Szulkin's critical point theory for lower semicontinuous energy functionals.     

Testing copositivity with the help of difference-of-convex optimization

We consider the problem of minimizing an indefinite quadratic form over the nonnegative orthant, or equivalently, the problem of deciding whether a symmetric matrix is copositive. We formulate the problem as a difference of convex functions problem. Using conjugate duality, we show that there is a one-to-one correspondence between their respective critical points and minima. We then apply a subgradient algorithm to approximate those critical points and obtain an efficient heuristic to verify non-copositivity of a matrix.     

Allocating procurement to capacitated suppliers with concave quantity discounts

We consider a procurement problem where suppliers offer concave quantity discounts. The resulting continuous knapsack problem involves the minimization of a sum of separable concave functions. We identify polynomially solvable special cases of this NP-hard problem, and provide a fully polynomial-time approximation scheme for the general problem.     

Optimal control problem for a quasilinear parabolic equation with controls in the coefficients and with state constraints

We consider an optimal coefficient control problem for a quasilinear parabolic equation. We study the well-posedness of the problem and obtain a necessary condition for optimality.     

Hermite interpolation with symmetric polynomials

We study the Hermite interpolation problem on the spaces of symmetric bivariate polynomials. We show that the multipoint Berzolari-Radon sets solve the problem. We also give a Newton formula for the interpolation polynomial and use it to prove a continuity property of the interpolation polynomial with respect to the interpolation points.     

Buyback problem with discrete concave valuation functions

We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.     

Gellerstedt problem with a generalized Frankl matching condition on the type change line with data on external characteristics

We study the solvability of the Gellerstedt problem for the Lavrent’ev–Bitsadze equation with nonclassical matching conditions for the gradient of the solution (in the sense of Frankl) on the type change line of the equation. We prove that the inhomogeneous Gellerstedt problem with data on the external characteristics of the equation is solvable either uniquely or modulo a nontrivial solution of the homogeneous problem. We obtain integral representations of the solution of the problem in both the elliptic and the hyperbolic parts of the domain. The solution proves to be regular.     

A multidomain discretization method with local mesh refinement

We introduce a nonconforming finite element formulation of asecond-order elliptic problem in the plane. The problem is posedon a domain which is partitioned into disjoint subregions andthe discrete problem is based on an independent triangulationby subregion. We use an integral matching condition at the interfaces.We prove quasi-optimal error estimates and propose an iterativesubstructuring algorithm to solve the system of linear equationsrelated to our discrete problem. The algorithm and its convergenceanalysis rely on an abstract framework of the additive Schwarzmethod.     

Scheduling with partial rejection

We study a single machine scheduling problem with partial rejection. Each job is with an integer processing time. Partial rejection occurs when a job is only partly processed with penalty for the rejected part. We focus on integer size rejection. The objective is to minimize the total weighted completion time of processed jobs plus the total rejection cost. We develop a polynomial time optimal algorithm to solve the problem. We also present an easy-to-implement pseudopolynomial time optimal algorithm.     

Binary knapsack problems with random budgets

The binary knapsack problem is a combinatorial optimization problem in which a subset of a given set of elements needs to be chosen in order to maximize profit, given a budget constraint. In this paper, we study a stochastic version of the problem in which the budget is random. We propose two different formulations of this problem, based on different ways of handling infeasibility, and propose an exact algorithm and a local search-based heuristic to solve the problems represented by these formulations. We also present the results from some computational experiments.     

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

Vector complementarity problems with a variable ordering relation

In this paper, we investigate vector complementarity problems with a variable ordering relation. We establish existence results of a solution of a vector complementarity problem under an inclusive type condition. We obtain equivalence results among a vector complementarity problem, a vector variational inequality problem and other related problems.