Behavioural-based mathematical programming: algorithmics and applications

基于行为的数学规划：算法和应用

• 批准号: RGPIN-2017-05073
• 负责人: Marcotte, Patrice
• 金额: $ 2.99万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=688203
• 关键词: Behavioural; based; mathematical; programming; algorithmics

The aim of my research is to study, from both the theoretical and computational points of view, decision problems that involve agents with conflicting objectives. To fix ideas, let us consider the problem of setting tolls on the links of a highway. In order to optimize the revenue, one must take into account the behaviour of drivers, who want to minimize their own travel cost. If tolls are low, revenue will be low. If tolls are high, revenue will also be low, due to the low number of drivers for which the highway will be attractive. One must then strike the right balance, taking into account user behaviour. Although it has been shown that, even in that simple setting, the problem is hard to solve, the situation becomes all the more complex when behaviour varies across the population or when congestion occurs. Such problems fit the framework of bilevel mathematical programs, or leader-follower games. In these games, the leader factors into its optimization problem the rational reaction of an adversary or a population impacted by his decisions. This reaction would be the drivers' path choices in our introductory example. This situation is ubiquitous. Indeed, it is the exception that all variables of a problem are controlled by the leader. ******Bilevel programming has been applied to areas as diverse as energy (optimizing the efficiency of a network, monitoring the 'smart grid'), urban planning, health care, transportation (rail, airlines). Governments use regulations and taxes to increase global welfare, and fail to achieve this goal if they do not consider the alternatives faced by the citizens. For instance, following a stiff tax increase of cigarettes that triggered smuggling, resulting in a decrease of tax revenues and an actual increase in cigarette consumption, contrary to the goal pursued!******Despite their capability to address important industrial, commercial and social issues, bilevel models are limited by their computational complexity. It is therefore important to design smart algorithms that take advantage of each application's structure. For a class of problems that I am studying, one approach consists in approximating the original model by a more tractable one, and then make progress from its solution towards the solution of the original. Other strategies, that are based on the combinatorial nature of bilevel problems, will also be investigated. All of them will be applied to practical instances in energy, facility location (including health care) and transportation.

我的研究的目的是研究，从理论和计算的角度来看，决策问题，涉及代理与冲突的目标。为了解决这个问题，让我们考虑一下在高速公路的连接处设置通行费的问题。为了优化收入，必须考虑司机的行为，他们希望最大限度地减少自己的旅行成本。如果收费低，收入就会低。如果通行费很高，收入也会很低，因为高速公路对司机的吸引力很小。然后，必须在考虑用户行为的情况下取得适当的平衡。虽然已经表明，即使在这种简单的情况下，问题也很难解决，但当整个人口的行为不同或出现拥挤时，情况就变得更加复杂。这样的问题符合双层数学规划或领导者-跟随者博弈的框架。在这些博弈中，领导者将对手或受其决策影响的人口的理性反应纳入其优化问题。在我们的介绍性示例中，这种反应就是驾驶员的路径选择。这种情况普遍存在。事实上，问题的所有变量都由领导者控制是一个例外。** 双层规划已应用于能源（优化网络效率，监控“智能电网”），城市规划，医疗保健，交通（铁路，航空）等不同领域。政府利用法规和税收来增加全球福利，如果他们不考虑公民面临的选择，就无法实现这一目标。例如，在对卷烟大幅增税之后，引发了走私，导致税收减少，卷烟消费实际增加，这与追求的目标背道而驰！**尽管它们能够解决重要的工业、商业和社会问题，但双层模型受到其计算复杂性的限制。因此，重要的是要设计智能算法，利用每个应用程序的结构。对于我正在研究的一类问题，一种方法是用一个更易处理的模型来近似原始模型，然后从它的解朝着原始模型的解前进。其他策略，是基于双层问题的组合性质，也将进行调查。所有这些都将应用于能源，设施位置（包括医疗保健）和运输的实际情况。