工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$left( {2 + 2alpha+alpha^{2}}right)$-近似算法, 其中$alpha$为给定的权重参数, 满足$0leqalphaleq 1$。     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

有尺寸的同型机分批排序问题的近似算法

对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法.对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比.     

工件有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝...     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

平行机上带有前瞻区间的不相容工件组在线排序问题

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. betageq 1 时, 提供了一个最优的在线算法; 当0leq beta < 1时, 提供了一个竞争比为1+alpha 的最好可能的在线算法, 其中alpha是方程alpha^{2}+(1+beta) alpha+beta-1=0的一个正根.最后, 给出了当beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为 1+alpha 的最好可能的在线算法,其中 alpha 是方程2alpha^{2}+(beta +1)alpha +beta -2=0的一个正根, 这里0leq beta <1.     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+rho)$, 其中$rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

Robust global optimization with polynomials

We consider the optimization problems max_z∈Ω min_x∈K p(z, x) and min_{x ∈ K} max_{z ∈ Ω} p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Ω can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max_{z ∈ Ω} p(z), whereas the second problem is a robust analogue of the generic problem min_{x ∈ K} p(x) of minimizing a polynomial over a semi-algebraic set. We show that the optimal values of both robust optimization problems can be approximated as closely as desired, by solving a hierarchy of SDP relaxations. We also relate and compare the SDP relaxations associated with the max-min and the min-max robust optimization problems.     

An improved semidefinite programming relaxation for the satisfiability problem

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variable X is maximized (or minimized) subject to linear constraints on the elements of X and the additional constraint that X be positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of higher liftings for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims.Mathematics Subject Classification (2000): 20E28, 20G40, 20C20     

Persistence in discrete optimization under data uncertainty

An important question in discrete optimization under uncertainty is to understand the persistency of a decision variable, i.e., the probability that it is part of an optimal solution. For instance, in project management, when the task activity times are random, the challenge is to determine a set of critical activities that will potentially lie on the longest path. In the spanning tree and shortest path network problems, when the arc lengths are random, the challenge is to pre-process the network and determine a smaller set of arcs that will most probably be a part of the optimal solution under different realizations of the arc lengths. Building on a characterization of moment cones for single variate problems, and its associated semidefinite constraint representation, we develop a limited marginal moment model to compute the persistency of a decision variable. Under this model, we show that finding the persistency is tractable for zero-one optimization problems with a polynomial sized representation of the convex hull of the feasible region. Through extensive experiments, we show that the persistency computed under the limited marginal moment model is often close to the simulated persistency value under various distributions that satisfy the prescribed marginal moments and are generated independently.     

鲁棒投资组合选择优化问题的研究进展

对近年来投资组合研究优化研究的热点问题——鲁棒投资组合优化研究的现状和发展趋势作了综述性研究．在投资组合选择优化的均值-方差模型的基础上,回顾了鲁棒投资组合选择优化问题的发展历史;详细地介绍了鲁棒投资组合选择优化的研究热点及国内外研究现状,就鲁棒投资组合选择优化问题的未来发展方向和主要研究内容,提出了新的观点,以期为相关领域的研究工作提供参考依据．     

Invariance and efficiency of convex representations

We consider two notions for the representations of convex cones G-representation and lifted-G-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-G-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under G-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the “smoothness” of the transformations mapping the central path of the representation to the central path of the represented optimization problem. Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.     

二层次消费与投资决策优化动态规划模型

在动态多阶段情形,投资者面临的环境不仅只有投资环境,还包括消费环境.投资者关于投资与消费的决策具有层次性.因为消费事关人的生存需要,是优先要考虑的问题,且投资的最终目的还是为了消费,所以使消费最大化应是高一层次的目标,而使投资最大化则应是次一级的目标.因此,试图建立一个二层次消费与投资决策优化动态规划模型,以便更好地模拟现实世界的情况.讨论了该模型的动态决策过程和最优解的性质.