Fulkersonʼs Conjecture and Loupekine snarks

Fulkersonʼs Conjecture says that every bridgeless cubic graph has six perfect matchings such that each edge belongs to exactly two of them. In 1976, F. Loupekine created a method for constructing new snarks from already known ones. We consider an infinite family of snarks built with Loupekineʼs method, and verify Fulkersonʼs Conjecture for this family.     

A stabilized structured Dantzig–Wolfe decomposition method

We discuss an algorithmic scheme, which we call the stabilized structured Dantzig–Wolfe decomposition method, for solving large-scale structured linear programs. It can be applied when the subproblem of the standard Dantzig–Wolfe approach admits an alternative master model amenable to column generation, other than the standard one in which there is a variable for each of the extreme points and extreme rays of the corresponding polyhedron. Stabilization is achieved by the same techniques developed for the standard Dantzig–Wolfe approach and it is equally useful to improve the performance, as shown by computational results obtained on an application to the multicommodity capacitated network design problem.     

自适应的Dantzig选择器的渐近性质研究

本文首先研究当变量个数p较大、甚至关于样本n指数速度增长时,高维稀疏线性回归模型下适应的Dantzig选择器估计量的渐近性问题.作为适应的Dantzig选择器的权重,当回归系数的初始估计取为某常数的相合估计时,在一些常规条件下,本文证明了适应的Dantzig选择器具有Oracle性质.对于p≤n和pn两种情形,本文也分别给出了易于实现的初始估计量.最后通过模拟验证了前面的理论结果.     

Automatic Dantzig–Wolfe reformulation of mixed integer programs

Mathematical Programming - Dantzig–Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the...     

Converging upon basic feasible solutions through Dantzig–Wolfe decomposition

We derive an important property for solving large-scale integer programs by examining the master problem in Dantzig–Wolfe decomposition. In particular, we prove that if a linear program can be divided into subproblems with affinely independent corner points, then there is a direct mapping between basic feasible solutions in the master and original problems. This has implications for integer programs where the feasible region has integer corner points, ensuring that integer solutions to the original problem will be found even through the decomposition approach. An application to air traffic flow scheduling, which motivated this result, is highlighted.     

菲尔兹奖与沃尔夫奖

由于种种原因诺贝尔奖中并没有数学奖 ,因此世界各国设立了为数不少的数学奖项 ,其中菲尔兹奖和沃尔夫奖这两项影响最大 .1　菲尔兹奖菲尔兹奖是为纪念加拿大数学家菲尔兹(J.C .Fields,1 86 3～ 1 932 )而命名的 .菲尔兹出生于加拿大渥太华 ,在多伦多上大学 ,而后在美国的约翰·霍普金斯大学获得博士学位 .他 1 892～ 1 90 2年游学欧洲 ,而后回到多伦多大学执教 .1 92 4年 ,菲尔兹作为多伦多国际数学家大会主席 ,成功地主持了该届大会 ,并在会后提议利用这次大会节余的经费设立一项国际性数学大奖 .菲尔兹的建议在 1 932年苏黎世国际数学…     

Parallel Dantzig–Wolfe decomposition of petroleum production allocation problems

This article discusses the optimization of a petroleum production allocation problem through a parallel Dantzig–Wolfe algorithm. Petroleum production allocation problems are problems in which the determination of optimal production rates, lift gas rates and well connections are the central decisions. The motivation for modelling and solving such optimization problems stems from the value that lies in an increased production rate and the current lack of integrated software that considers petroleum production systems as a whole. Through our computational study, which is based on realistic production data from the Troll West field, we show the increase in computational efficiency that a parallel Dantzig–Wolfe algorithm offers. In addition, we show that previously implemented standard parallel algorithms lead to an inefficient use of parallel resources. A more advanced parallel algorithm is therefore developed to improve efficiency, making it possible to scale the algorithm by adding more CPUs and thus approach a reasonable solution time for realistic-sized problems.     

A class of Dantzig–Wolfe type decomposition methods for variational inequality problems

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig–Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptions. We also report numerical experiments for computing variational equilibria of the game-theoretic models of electricity markets. Our numerical results illustrate that the decomposition approach allows to solve large-scale problem instances otherwise intractable if the widely used PATH solver is applied directly, without decomposition.     

Classification of Dantzig–Wolfe reformulations for binary mixed integer programming problems

In this note, we provide a classification of Dantzig–Wolfe reformulations for Binary Mixed Integer Programming Problems. We specifically focus on modeling the binary conditions in the convexification approach to the Dantzig–Wolfe decomposition. For a general Binary Mixed Integer Programming problem, an extreme point of the overall problem does not necessarily correspond to an extreme point of the subproblem. Therefore, the binary conditions cannot in general be imposed on the new master problem variables but must be imposed on the original binary variables. In some cases, however, it is possible to impose the binary restrictions directly on the new master problem variables. The issue of imposing binary conditions on the original variables versus the master problem variables has not been discussed systematically for MIP problems in general in the literature and most of the research has been focused on the pure binary case. The classification indicates in which cases you can, and cannot, impose binary conditions on the new master problem variables.     

阿贝尔与阿贝尔奖

国际性的数学奖除了菲尔兹奖(FieldsMedal)和沃尔夫奖(Wolf Medal)之外,2003年又增加了一个新成员,即一项专门为数学家设立的、奖金额约80万美元的数学终身成就奖——阿贝尔奖.     

阿贝尔与阿贝尔奖

国际性的数学大奖除了菲尔兹奖和沃尔夫奖之外，2003年又增加了一个新成员：即一项专门为数学家设立的、奖金额约80万美元的数学杰出成就奖——阿贝尔奖．     

阿贝尔与阿贝尔奖

国际性的数学奖除了菲尔兹奖 (FieldsMedal)和沃尔夫奖 (WolfMedal)之外 ,2 0 0 3年又增加了一个新成员 :一项奖金额约 80万美元的数学终身成就奖———阿贝尔奖 .阿贝尔 (N .H .Abel,180 2～ 182 9) ,挪威数学家 ,180 2年 8月 5日出生于今天奥斯陆附近的芬多村的一个牧师家庭 .这是个多子女的家庭 ,父亲是个神学家 ,生活很清苦 .13岁时 ,阿贝尔到首都奥斯陆的教会学校读中学 .起初 ,枯燥的课程和素质低的教师 ,使阿贝尔对学习没有兴趣 .15岁那年 (1817年 ) ,学校来了一位高水平的数学老师洪保 ,在这位老师的指导下 ,阿贝尔产生了对数学…     

沃尔夫与沃尔夫奖

沃尔夫基金会由已故犹太发明家、外交家和慈善家里卡多·沃尔夫博士创立 .它 1887年生于德国汉诺威城 ,父亲是个五金商人 ,也是当地犹太社团领袖 ,他兄妹共 14人 .活尔夫曾在德国研究化学 ,并获得博士学位 ,在第一次世界大战前移居古巴 .192 4年 ,他与网坛冠军弗朗西斯卡结婚 .他用了近 2 0年的时间 ,经过大量试验 .历尽艰辛 ,成功地发明了一种从熔炼废渣中回收铁的方法 ,从而成为百万富翁 .他支持古巴革命并提供巨额财政支持 ,是卡斯特罗的好友 ,196 1年 ,被古巴政府任命为驻以色列的大使 ,1973年古巴与以色列断交后 ,他留在以色列度晚年 .…     

ICIAM苏步青奖与CSIAM苏步青应用数学奖

国际工业与应用数学大会(ICIAM)是四年一届的工业与应用数学界的盛会,也是最高水平的工业与应用数学家大会.2003年7月的悉尼大会后举行的国际工业与应用数学联合会的理事年会上,顺利通过了由中国工业与应用数学学会(CSIAM)提出的设立ICIAM苏步青奖的建议,成为该会前已设立的Lagrange奖、Collatz奖、先驱奖和Maxwell奖之后的第五个奖项,旨在奖励在数学对经济腾飞和人类发展的应用方面做出杰出贡献的个人.每四年颁发一次,每次一人.同年11月,中国工业与应用数学学会决定设立CSIAM苏步青应用数学奖,用以进一步推动我国工业与应用数学…     

丘成桐与菲尔兹奖

举世瞩目的国际数学家大会 (InternationalCongressofmathematician ,简称ICM) ,已有百余年的历史 .1 897年 ,在瑞士苏黎世举行首届大会 .1 90 0年在法国巴黎召开第二次国际数学家大会之后 ,每四年举行一次 ,现已成为最高水平的全球性数学科学学术会议 .四年一度的菲尔兹奖与ICM紧密相关 ,该奖的提案人是已故的加拿大数学家菲尔兹 (J .C .Fields) .从 1 936年ICM- 1 0起 ,每届ICM的第一项议程就是宣布菲尔兹奖荣获者的名单 ,介绍他们的杰出成就 .菲尔兹奖是数学领域的最高奖 ,被称为数学的诺贝尔奖 .在人类知识的领域中 ,数学以其辉…     

Dantzig–Wolfe decomposition of the daily course pattern formulation for curriculum-based course timetabling

In this paper, we considered the problem of Curriculum-Based Course Timetabling, i.e., assigning weekly lectures to a time schedule and rooms. We developed a Column Generation algorithm based on a pattern formulation of the time scheduling part of the problem by Bagger et al. (2016). The pattern formulation is an enumeration of all schedules by which each course can be assigned on each day; it is a lower bounding model. Pattern enumeration has also been considered in Burke (2008), where the authors enumerated all schedules to which each curriculum can be assigned on each day. We applied the Dantzig–Wolfe reformulation, so each column corresponded to a schedule for an entire day.We solved the reformulation with the Column Generation algorithm, where each pricing problem generated a full schedule for a single day. We provided a pre-processing technique that, on average, removed approximately 45% of the pattern variables in the pricing problems. We then extended the pre-processing technique into inequalities that we added to the model. Lastly, we describe how we applied Local Branching to the pricing problem by using the columns generated in previous iterations.We compare the lower bounds we obtained, with other methods from literature, on 20 data instances of real-world applications. For 16 instances the optimal solutions are known, but the remaining four are still open. Our approach improved the best-known lower bound for all four open instances, and decreased the average gap from 24 to 11%.     

部分线性模型下Adaptive Dantzig Selector方法的渐近正态性

变量选择是处理超高维数据过程中重要的部分.本文提出部分线性模型下ADS(Adaptive Dantzig Selector)方法,并证明其渐近正态性.通过数值模拟以及大众点评网数据,验证此方法的可行性以及高精准性.     

中国数学会2009学术年会召开华罗庚奖与陈省身奖颁发

中国数学会2009学术年会于4月21-24日在厦门大学举行，包括十二位两院院士和国际数学联盟执委会成员在内的近四百名从事数学教育和研究的专家学者和研究生参加了会议．     

A generalized Dantzig—Wolfe decomposition principle for a class of nonconvex programming problems

Since Dantzig—Wolfe's pioneering contribution, the decomposition approach using a pricing mechanism has been developed for a wide class of mathematical programs. For convex programs a linear space of Lagrangean multipliers is enough to define price functions. For general mathematical programs the price functions could be defined by using a subclass of nondecreasing functions. However the space of nondecreasing functions is no longer finite dimensional. In this paper we consider a specific nonconvex optimization problem min {f(x):h _j (x)g(x),j=1, ,m, xX}, wheref(·),h _j (·) andg(·) are finite convex functions andX is a closed convex set. We generalize optimal price functions for this problem in such a way that the parameters of generalized price functions are defined in a finite dimensional space. Combining convex duality and a nonconvex duality we can develop a decomposition method to find a globally optimal solution.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

科学突破奖——数学新视野奖

<正>2019年9月5日,2020年度科学突破奖(Breakthrough Prize)揭晓.该奖项被誉为科学界的奥斯卡!北京大学数学科学学院校友朱歆文因在算术代数几何工作中对志村簇的应用和黎曼希尔伯特问题在p-adic簇的情形中取得了重要突破,获得了本届科学突破奖——数学新视野奖(New Horizons in Mathematics