有哪些非常适合整数线性规划问题的示例？
我一直在编写软件来解决业务问题。我在浏览其中一篇 SO 帖子时偶然发现了 LIP。我用谷歌搜索了它，但我无法关联如何使用它来解决业务问题。如果有人能帮助我用外行术语理解，我将不胜感激。
I've always been writing software to solve business problems. I came across about LIP while I was going through one of the SO posts. I googled it but I am unable to relate how I can use it to solve business problems. Appreciate if some one can help me understand in layman terms.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
ILP 本质上可用于解决涉及做出一系列决策的任何问题，每个决策只有几种可能的结果，所有结果都是提前已知的，并且其中任意组合的整体“质量”可以使用不依赖于选择之间“交互”的函数来描述选择。要了解其工作原理，最简单的方法是进一步限制只能为 0 或 1（整数的最小有用范围）的变量。现在：
示例
例如，假设您有 3 个工人，Anne、Bill 和 Carl，以及 3 个工作：除尘、打字和包装。所有的人都可以完成所有的工作，但每个人在每项工作上都有不同的效率/能力水平，因此我们希望找到每个人执行的最佳任务，以最大限度地提高整体效率。我们希望每个人只执行一份工作。
变量
设置此问题的一种方法是使用 9 个变量，每个变量对应工人和工作的每种组合。如果 Anne 应该在最优解中除尘，则变量 x_ad 的值为 1，否则为 0；如果Bill应该Pack在最优解中，x_bp将得到值1，否则为0；等等。
目标函数
接下来要做的就是制定一个我们想要最大化或最小化的目标函数。假设根据 Anne、Bill 和 Carl 最近的绩效评估，我们有一个包含 9 个数字的表，告诉我们他们每个人完成这 3 项工作需要多少分钟。在这种情况下，取所有 9 个变量的总和是有意义的，每个变量乘以该特定工人执行该特定工作所需的时间，并寻求最小化这个总和——也就是说，最小化完成该任务所需的总时间。完成所有工作。
约束
最后一步是给出约束，强制执行 (a) 每个人都只做 1 份工作，并且 (b) 每项工作都由 1 个人完成。 （请注意，实际上这些步骤可以按任何顺序完成。）
为了确保 Anne 恰好完成 1 项工作，我们可以添加 x_ad + x_at + x_ap = 1 的约束。可以为 Bill 和 Carl 添加类似的约束。
为了确保恰好有 1 个人除尘，我们可以添加 x_ad + x_bd + x_cd = 1 的约束。可以为 Typing 和 Packing 添加类似的约束。
总共有 6 个约束。现在，您可以将这个 9 变量、6 约束问题提供给 ILP 求解器，它会返回最佳解决方案之一中的变量值 - 其中正好有 3 个为 1，其余为 0。 3=1 告诉你哪些人应该做哪些工作！
ILP 是一般性的
碰巧，这个特殊问题有一个特殊结构，可以让它得到更多解决有效地使用不同的算法。使用 ILP 的优点是可以轻松合并问题的变体：例如，如果实际上有 4 个人，只有 3 份工作，那么我们需要放宽约束，以便每个人至多 1 份工作，而不是恰好 1 份工作。这可以简单地通过将前 3 个约束中的等号更改为小于或等于号来表达。
ILP can be used to solve essentially any problem involving making a bunch of decisions, each of which only has several possible outcomes, all known ahead of time, and in which the overall "quality" of any combination of choices can be described using a function that doesn't depend on "interactions" between choices. To see how it works, it's easiest to restrict further to variables that can only be 0 or 1 (the smallest useful range of integers). Now:
Example
For example, suppose you have 3 workers, Anne, Bill and Carl, and 3 jobs, Dusting, Typing and Packing. All of the people can do all of the jobs, but they each have different efficiency/ability levels at each job, so we want to find the best task for each of them to do to maximise overall efficiency. We want each person to perform exactly 1 job.
Variables
One way to set this problem up is with 9 variables, one for each combination of worker and job. The variable x_ad will get the value 1 if Anne should Dust in the optimal solution, and 0 otherwise; x_bp will get the value 1 if Bill should Pack in the optimal solution, and 0 otherwise; and so on.
Objective Function
The next thing to do is to formulate an objective function that we want to maximise or minimise. Suppose that based on Anne, Bill and Carl's most recent performance evaluations, we have a table of 9 numbers telling us how many minutes it takes each of them to perform each of the 3 jobs. In this case it makes sense to take the sum of all 9 variables, each multiplied by the time needed for that particular worker to perform that particular job, and to look to minimise this sum -- that is, to minimise the total time taken to get all the work done.
Constraints
The final step is to give constraints that enforce that (a) everyone does exactly 1 job and (b) every job is done by exactly 1 person. (Note that actually these steps can be done in any order.)
To make sure that Anne does exactly 1 job, we can add the constraint that x_ad + x_at + x_ap = 1. Similar constraints can be added for Bill and Carl.
To make sure that exactly 1 person Dusts, we can add the constraint that x_ad + x_bd + x_cd = 1. Similar constraints can be added for Typing and Packing.
Altogether there are 6 constraints. You can now supply this 9-variable, 6-constraint problem to an ILP solver and it will spit back out the values for the variables in one of the optimal solutions -- exactly 3 of them will be 1 and the rest will be 0. The 3 that are 1 tell you which people should be doing which job!
ILP is General
As it happens, this particular problem has a special structure that allows it to be solved more efficiently using a different algorithm. The advantage of using ILP is that variations on the problem can be easily incorporated: for example if there were actually 4 people and only 3 jobs, then we would need to relax the constraints so that each person does at most 1 job, instead of exactly 1 job. This can be expressed simply by changing the equals sign in each of the 1st 3 constraints into a less-than-or-equals sign.
首先，阅读来自维基百科的线性编程示例
现在想象一下农民生产猪和鸡，或者一家生产烤面包机和吸尘器的工厂 - 现在输出（以及可能的约束）是整数，所以那些漂亮的图表将逐步弯曲。这是一个很容易表示为线性规划问题的业务应用程序。
我之前使用过整数线性规划来确定如何平铺n个相同比例的图像以最大化用于显示这些图像的屏幕空间，并且形式主义可以代表诸如调度之类的覆盖问题，但是整数线性规划的商业应用似乎是更自然的应用它的。
所以用户 flolo 说：
我经常遇到的用例：在数字电路设计中，您需要将对象放置/映射到芯片的某些部分（FPGA 放置） - 这可以通过 ILP 来完成。另外，在硬件-软件协同设计中，经常会出现分区问题：程序的哪一部分仍应在CPU上运行，哪一部分应在硬件上加速。这也可以通过 ILP 来解决。
First, read a linear programming example from Wikipedia
Now imagine the farmer producing pigs and chickens, or a factory producing toasters and vacuums - now the outputs (and possibly constraints) are integers, so those pretty graphs are going to go all crookedly step-wise. That's a business application that is easily represented as a linear programming problem.
I've used integer linear programming before to determine how to tile n identically proportioned images to maximize screen space used to display these images, and the formalism can represent covering problems like scheduling, but business applications of integer linear programming seem like the more natural applications of it.
SO user flolo says:
Use cases where I often met it: In digital circuit design you have objects to be placed/mapped onto certain parts of a chip (FPGA-Placing) - this can be done with ILP. Also in HW-SW codesign there often arise the partition problem: Which part of a program should still run on a CPU and which part should be accelerated on hardware. This can be also solved via ILP.
您可以在任何想要优化的地方轻松应用线性程序，并且目标函数是线性的。你可以制定时间表（我的意思是大的，比如火车公司，他们需要优化车辆和轨道的利用率）、生产（优化胜利），几乎所有事情。有时将您的问题表述为 IP 是很棘手的，并且/或有时您会遇到解决方案的问题，即您必须生产例如 0.345 辆汽车才能获得最佳胜利。这当然是不可能的，因此您需要施加更多约束：汽车数量的变量必须是整数。即使现在听起来更简单（因为变量的选择无限少），但实际上更难。此时它就变得 NP 困难了。这实际上意味着您可以使用 ILP 解决计算机上的任何问题，您只需对其进行转换即可。
对于您，我建议您阅读一些基本的 (I)LP 内容。在我看来，我不知道有什么好的在线网站（但如果你用谷歌搜索，你会找到一些），作为书籍，我可以推荐 Chvatal 的线性编程。它有非常好的示例，并且还描述了真实的用例。
You can apply linear program easily everywhere you want to optimize and the target function is linear. You can make schedules (I mean big, like train companies, who need to optimize the utilization of the vehicles and tracks), productions (optimize win), almost everything. Sometimes it is tricky to formulate your problem as IP and/or sometimes you meet the problem that your solution is, that you have to produce e.g. 0.345 cars for optimum win. That is of course not possible, and so you constraint even more: Your variable for the number of cars must be integer. Even when it now sounds simpler (because you have infinite less choices for your variable), its actually harder. In this moment it gets NP-hard. Which actually means you can solve ANY problem from your computer with ILP, you just have to transform it.
For you I would recommend an intro into reading some basic (I)LP stuff. From my mind I dont know any good online site (but if you goolge you will find some), as book I can recommend Linear Programming from Chvatal. It has very good examples, and describes also real use cases.
示例 ILP 问题类似于：
，其中
...但是，有一组形式为
现在，对维基百科的示例进行更简单的表述：
现在，
因此，
a1,a2,L,F1,F2,F,P1,P2,P - 都是常数（在我们的示例中：正）
我们正在寻找正整数x1,x2，在给定规定的约束的情况下，它将使规定的表达式最大化。
希望它是清楚的...
A sample ILP problem will looks something like:
where
...but, there is a set of constrains in the form
Now, a simpler articulation of Wikipedia's example:
Now,
So,
a1,a2,L,F1,F2,F,P1,P2,P - are all constants (in our example: positive)
We are looking for positive integers x1,x2 that will maximize the expression stated, given the constrains stated.
Hope it's clear...
ILP“本身”可以直接对很多东西进行建模。如果你搜索LP例子，你可能会发现很多著名的教科书案例，比如饮食问题
许多此类问题自然都有要求变量为整数的实例（也许你不能将药丸分成两半），
但真正有趣的是，实际上大量组合问题都简化为 LP。我最喜欢的问题之一是作业问题
大多数自然出现的解决方案都具有指数复杂度，但有一个使用线性规划的多项式解决方案。
当谈到 ILP 时，ILP 具有 NP 完全性的额外好处/困难。这意味着它可以用来对非常广泛的问题进行建模（布尔可满足性在这方面也很流行）。由于有许多优秀且优化的 ILP 求解器，因此通常可以将 NP 完全问题转换为 ILP，而不是设计自己的自定义算法。
ILP "by itself" can directly model lots of stuff. If you search for LP examples you will probably find lots of famous textbook cases, such as the diet problem
Many such problems naturally have instances that require varialbe to be integers (perhaps you can't split pills in half)
The really interesting stuff though is that actually a big deal of combinatorial problems reduce to LP. One of my favourites is the assignment problem
Most solution that naturally come up have exponential complexity but there is a polynomial solution using linear programming.
When it comes to ILP, ILP has the added benefit/difficulty of being NP-complete. This means that it can be used to model a very wide range of problems (boolean satisfiability is also very popular in this regard). Since there are many good and optimized ILP solvers out there it is often viable to translate an NP-complete problem into ILP instead of devising a custom algorithm of your own.
这里的其他答案有很好的例子。使用整数规划和更普遍的运筹学业务的两个黄金标准是
Interfaces 发表了将运筹学应用于现实世界问题的研究，而爱德曼奖是针对商业使用运筹学技术的一个极具竞争力的奖项。
The other answers here have excellent examples. Two of the gold standards in business of using integer programming and more generally operations research are
Interfaces publishes research that uses operations research applied to real-world problems, and the Edelman award is a highly competitive award for business use of operations research techniques.