Computational complexity of some restricted instances of 3-SAT

Tovey [A simplified satisfiability problem, Discrete Appl. Math. 8 (1984) 85-89] showed that it is NP-hard to decide the satisfiability of 3-SAT instances in which every variable occurs four times, while every instance of 3-SAT in which each variable occurs three times is satisfiable. We explore the border between these two problems. Answering a question of Iwama and Takaki, we show that, for every fixed k?0, there is a polynomial-time algorithm to determine the satisfiability of 3-SAT instances in which k variables occur four times and the remaining variables occur three times. On the other hand, it is NP-hard to decide the satisfiability of 3-SAT instances in which all but one variable occurs three times, and the remaining variable is allowed to occur an arbitrary number of times.     

Hard satisfiable instances for DPLL-type algorithms

We address lower bounds on the time complexity of algorithms solving the propositional satisfiability problem. Namely, we consider two DPLL-type algorithms, enhanced with the unit clause and pure literal heuristics. Exponential lower bounds for solving satisfiability on provably satisfiable formulas are proven. Bibliography: 11 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 293, 2002, pp. 139–148.This revised version was published online in April 2005 with a corrected cover date and article title.     

Complexity of the satisfiability problem for multilinear forms over a finite field

Multilinear forms over finite fields are considered. Multilinear forms over a field are products in which each factor is the sum of variables or elements of this field. Each multilinear form defines a function over this field. A multilinear form is called satisfiable if it represents a nonzero function. We show the N P-completeness of the satisfiability recognition problem for multilinear forms over each finite field of q elements for q ≥ 3. A theorem is proved that distinguishes cases of polynomiality and NP-completeness of the satisfiability recognition problem for multilinear fields for each possible q ≥ 3.     

EIN NEUER BEWEIS UND EINE VERSCHÄRFUNG FÜR DEN REDUKTIONSTYP ∀∃∀∞(0, 1) MIT EINER ANWENDUNG AUF DIE SPEKTRALE DARSTELLUNG VON PRÄDIKATEN

A simultaneous semantical and syntactical reduction is given for the satisfiability respectively finite satisfiability of first order formulas. We choose ???∞(0, 1) as conservative reduction class and allow only formulas out of ???∞(0, 1) having a simple set theoretical model if they are satisfiable at all. With the same method we get a spectral representation of any ?-ary enumerable respectively coenumerable predicate by a formula out of ???∞(?, 1).     

Testing satisfiability

Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1,d]. We say that Φ is ε-far from satisfiable, if one must remove at least εn^k functions in order to make the set of remaining functions satisfiable. Our main result is that if Φ is ε-far from satisfiable, then most of the induced sets of functions, on sets of variables of size c(k,d)/ε², are not satisfiable, where c(k,d) depends only on k and d. Using the above claim, we obtain similar results for k-SAT and k-NAEQ-SAT.Assume we relax the decision problem of whether an instance of one of the above mentioned problems is satisfiable or not, to the problem of deciding whether an instance is satisfiable or ε-far from satisfiable. While the above decision problems are NP-hard, our result implies that we can solve their relaxed versions, that is, distinguishing between satisfiable and ε-far from satisfiable instances, in randomized constant time.From the above result we obtain as a special case, previous results of Alon and Krivelevich, and of Czumaj and Sohler, concerning testing of graphs and hypergraphs colorability. We also discuss the difference between testing with one-sided and two-sided error.     

Projecting systems of linear inequalities with binary variables

We investigate methods for projecting out 0–1 variables from a system of linear inequalities. After reviewing some special cases like monotone polyhedra and the satisfiability problem, we examine why Fourier elimination cannot be applied to the general case. Finally, we give a procedure based on disjunctive programming for solving the general case. We also discuss a simpler procedure applicable only under certain conditions.     

Scheduling with safety distances

We investigate the problem of Scheduling with Safety Distances (SSD) that consists in scheduling jobs on two parallel machines without machine idle time. Every job is already assigned to its machine, and we just have to specify an ordering of the jobs for each machine. The goal is to find orderings of the jobs such that the minimum time elapsed between any two job completion times is maximized. We prove that this problem is NP-hard in general and give polynomial time algorithms for special cases. These results combined establish a sharp borderline between NP-complete and polynomial solvable versions of the problem SSD.This research was supported by the Christian Doppler Laboratorium für Diskrete Optimierung.On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, PR China.     

On discrete optimization with ordering

This paper studies discrete optimization problems with ordering requirements. These problems are formulated on general discrete sets in which there exists an ordering on their elements together with a cost function that evaluates each element of a given subset depending on its ordering relative to the remaining elements in the set. It is proven that ordered sequences over the original ground set define an independence system. The simplest such ordering problem, that consists of finding the ordered sequence of maximum weight, and its restriction to sets of a fixed cardinality are studied. In both cases, the polyhedral structure of the corresponding feasible sets is analyzed.     

A Solution Concept for Fuzzy Multiobjective Programming Problems Based on Convex Cones

A solution concept for fuzzy multiobjective programming problems based on ordering cones (convex cones) is proposed in this paper. The notions of ordering cones and partial orderings on a vector space are essentially equivalent. Therefore, the optimality notions in a real vector space can be elicited naturally by invoking a concept similar to that of the Pareto-optimal solution in vector optimization problems. We introduce a corresponding multiobjective programming problem and a weighting problem of the original fuzzy multiobjective programming problem using linear functionals so that the optimal solution of its corresponding weighting problem is also the Pareto-optimal solution of the original fuzzy multiobjective programming problem.     

Selecting Complementary Pairs of Literals

We present and rigorously analyze a heuristic that searches for a satisfying truth assignment of a given random instance of the 3-SAT problem. We prove that the heuristic asymptotically certainly succeeds in producing a satisfying truth assignment for formulas with clauses to variables ratio (density) of up to 3.52. Thus the experimentally observed threshold of the density where a typical formula's phase changes from asymptotically certainly satisfiable to asymptotically certainly contradictory is rigorously shown to be at least 3.52. The best previous lower bound in the long series of mathematically rigorous approximations by various research groups of the experimental threshold was 3.42. That was the first result where the probabilistic analysis was based on random formulas with a pre-specified, typical number of appearances for each literal. However, in that result, in order to simplify the analysis, the number of appearances of each literal was decoupled from the number of appearances of its negation. In this work, we assume not only that each literal has the typical number of occurrences, but that for each variable both numbers of occurrences of its positive and negated appearances are typical. By standard techniques, our algorithm can be easily modified to run in linear time. Thus not only the satisfiability threshold, but also the threshold (experimental again) where the complexity of searching for satisfying truth assignments jumps from polynomial to exponential is at least 3.52. This should be contrasted with the value 3.9 for the complexity threshold given by theoretical (but not mathematically rigorous) techniques of Statistical Physics.     

多阶段生产系统最优生产批量和原材料订购决策模型

Sarker和Parija(1996)建立了生产系统最优生产批量和原材料订购决策模型。然而他们的模型仅局限于单阶段生产系统,本文将他们的模型扩展到多阶段生产系统,我们首先建立了使整个多阶段生产系统总成本最小的各阶段最优生产批量、原材料订购批量及阶段之间的运输批量模型,然后分析了原材料订购费、半成品运费及设备安装费的敏感性。最后,我们结合实例综合分析了原材料订购费、半成品运输费和设备安装费的变化及最小值点取整后对原材料订购决策、最优生产批量和总成本的影响。     

Polynomial cases of the economic lot sizing problem with cost discounts

In this paper we study the economic lot sizing problem with cost discounts. In the economic lot sizing problem a facility faces known demands over a discrete finite horizon. At each period, the ordering cost function and the holding cost function are given and they can be different from period to period. There are no constraints on the quantity ordered in each period and backlogging is not allowed. The objective is to decide when and how much to order so as to minimize the total ordering and holding costs over the finite horizon without any shortages. We study two different cost discount functions. The modified all-unit discount cost function alternates increasing and flat sections, starting with a flat section that indicates a minimum charge for small quantities. While in general the economic lot sizing problem with modified all-unit discount cost function is known to be NP-hard, we assume that the cost functions do not vary from period to period and identify a polynomial case. Then we study the incremental discount cost function which is an increasing piecewise linear function with no flat sections. The efficiency of the solution algorithms follows from properties of the optimal solution. We computationally test the polynomial algorithms against the use of CPLEX.     

A general procedure for solving boundary-value problems of elastostatics for a spherical geometry based on Love's approach

We develop a general procedure for solving the first and secondfundamental problems of the theory of elasticity for cases whereboundary conditions are prescribed on a spherical surface, usingLove's general solution of the elastostatic equilibrium equationsin terms of three scalar harmonic functions. It is shown thatthis general solution combined with a methodology by Brennerpaves an elegant way to determine the three harmonic functionsin terms of the boundary data. Thus, with this general scheme,solution of any such boundary-value problem is reducible toa routine exercise thereby providing some `economy of effort'.Furthermore, we develop a similar general scheme for thermoelasticproblems for cases when temperature type boundary conditionsare prescribed on a spherical surface. We then illustrate theapplication of the procedure by solving a number of problemsconcerning rigid spherical inclusions and spherical cavities.In particular, apart from furnishing alternative solutions tothe known problems, we demonstrate the use of this general procedurein solving the problem of interaction of a rigid spherical inclusionwith a concentrated moment and that of a concentrated heat sourcesituated at an arbitrary point outside the inclusion. We alsoderive closed-form expressions for the net force and the nettorque acting on a rigid spherical inclusion embedded into aninfinite elastic solid under an ambient displacement field characterizedby an arbitrary-order polynomial in the Cartesian coordinates.To the best of our knowledge, these results are new.     

Semidefinite resolution and exactness of semidefinite relaxations for satisfiability

This paper explores new connections between the satisfiability problem and semidefinite programming. We show how the process of resolution in satisfiability is equivalent to a linear transformation between the feasible sets of the relevant semidefinite programming problems. We call this transformation semidefinite programming resolution, and we demonstrate the potential of this novel concept by using it to obtain a direct proof of the exactness of the semidefinite formulation of satisfiability without applying Lasserre’s general theory for semidefinite relaxations of 0/1 problems. In particular, our proof explicitly shows how the exactness of the semidefinite formulation for any satisfiability formula can be interpreted as the implicit application of a finite sequence of resolution steps to verify whether the empty clause can be derived from the given formula.     

The multi-period newsboy problem

We will try to generalize the so-called newsboy model so that we can deal with unsatisfied demand or unsold quantity. Consider the time interval that consists of multiple ordering cycles. Assume that the probability density function of demand is given for each cycle. Then our problem is to make the ordering plan with which we can maximize the expected profit. In the classical newsboy model ordering quantity is always equal to the (planned) initial inventory level. But if we take account of unsatisfied demand and unsold quantity, the (desired) ordering quantity must be determined by a proper stochastic rule. Then, in stead of determining the ordering quantity of each cycle, we must plan the initial inventory level so that the expected profit may be maximized. If unsold exists in present cycle, the ordering quantity of next cycle becomes smaller than the planned inventory level. And if unsatisfied demand exists in the present cycle, the ordering quantity of next cycle becomes larger than the planned inventory level.     

On the choice of parameters for the weighting method in vector optimization

We present a geometrical interpretation of the weighting method for constrained (finite dimensional) vector optimization. This approach is based on rigid movements which separate the image set from the negative of the ordering cone. We study conditions on the existence of such translations in terms of the boundedness of the scalar problems produced by the weighting method. Finally, using recession cones, we obtain the main result of our work: a sufficient condition under which weighting vectors yield solvable scalar problems. An erratum to this article can be found at     

Prices stabilization for inexact unit-commitment problems

A widespread and successful approach to tackle unit-commitment problems is constraint decomposition: by dualizing the linking constraints, the large-scale nonconvex problem decomposes into smaller independent subproblems. The dual problem consists then in finding the best Lagrangian multiplier (the optimal “price”); it is solved by a convex nonsmooth optimization method. Realistic modeling of technical production constraints makes the subproblems themselves difficult to solve exactly. Nonsmooth optimization algorithms can cope with inexact solutions of the subproblems. In this case however, we observe that the computed dual solutions show a noisy and unstable behaviour, that could prevent their use as price indicators. In this paper, we present a simple and easy-to-implement way to stabilize dual optimal solutions, by penalizing the noisy behaviour of the prices in the dual objective. After studying the impact of a general stabilization term on the model and the resolution scheme, we focus on the penalization by discrete total variation, showing the consistency of the approach. We illustrate our stabilization on a synthetic example, and real-life problems from EDF (the French Electricity Board).     

Construction of inclusions with vanishing generalized polarization tensors by imperfect interfaces

We investigate the problem of planar conductivity inclusion with imperfect interface conditions. We assume that the inclusion is simply connected. The presence of the inclusion causes a perturbation in the incident background field. This perturbation admits a multipole expansion of which coefficients we call as the generalized polarization tensors (GPTs), extending the previous terminology for inclusions with perfect interfaces. We derive explicit matrix expressions for the GPTs in terms of the incident field, material parameters, and geometry of the inclusion. As an application, we construct GPT-vanishing structures of general shape that result in negligible perturbations for all uniform incident fields. The structure consists of a simply connected core with an imperfect interface. We provide numerical examples of GPT-vanishing structures obtained by our proposed scheme.     

A production planning model for an unreliable production facility: Case of finite horizon and single demand

We study a two-level inventory system that is subject to failures and repairs. The objective is to minimize the expected total cost so as to determine the production plan for a single quantity demand. The expected total cost consists of the inventory carrying costs for finished and unfinished items, the backlog cost for not meeting the demand due-date, and the planning costs associated with the ordering schedule of unfinished items. The production plan consists of the optimal number of lot sizes, the optimal size for each lot, the optimal ordering schedule for unfinished items, and the optimal due-date to be assigned to the demand. To gain insight, we solve special cases and use their results to device an efficient solution approach for the main model. The models are solved to optimality and the solution is either obtained in closed form or through very efficient algorithms.     

Stability and monotonicity in newsvendor situations

This study considers a supply chain that consists of n retailers, each of them facing a newsvendor problem, and a supplier. Groups of retailers might increase their expected joint profit by joint ordering and inventory centralization. However, we assume that the retailers impose some level of stock that should be dedicated to them. In this situation, we show that the associated cooperative game has a non-empty core. Afterwards, we concentrate on a dynamic situation, where several model cost parameters and the retailers’ dedicated stock levels can change. We investigate how the profit division might be affected by these changes. We focus on four monotonicity properties. We identify several classes of games with retailers, where some of the monotonicity properties hold. Moreover, we show that pairs of cooperative games associated with newsvendor situations do not necessarily satisfy these properties in general, when changes in dedicated stock levels are in concern.