# Tag Info

19

"General purpose optimization" is quite broad, so I'll take a step back first, to better identifying the motivation of using ML in optimization settings. To keep things simple, I'll consider a single-objective minimization problem with decision vector $x$, objective function $f$ and some constraints $x \in X$, i.e., \begin{align} (P) \ \ \ \min_{x} ...

17

A great cause would be supply chain in countries/regions with poor infrastructure and/or uncertain supply and high price fluctuations. This is particularly important in many developing countries, because getting supplies to their destination and being able to do so on time is not straightforward. Another amazing cause is to formulate & solve travelling ...

16

QSopt-Exact by Applegate, Cook, Dash, and Espinoza

13

First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases. Most well-known is probably "TU-ness" of your matrix. When you solve a MIP $$\min\{c^tx \mid Ax\geq b, x\in Z^n\times Q^q\}$$ then you will obtain an integer ...

11

A new webinar series was just started: Analytics for a Better World. The first two presentations cover health care (ventilator distribution for COVID-19) and the poverty (food distribution).

10

Ifors has an entire page titled "Developing Countries OR Resources", where they list resources in topics such as: Agriculture Communication Community OR Current Events Education Energy Environment Health Industry Infrastructure Labour Law Enforcement Safety General Articles Finance Transportation Free OR Software

10

It is possible to have an integer subproblem with an objective, but to solve such a problem you need to branch on variables both in the master problem and in the sub-problem. This is not supported by off-the-shelf solvers, so it requires quite some coding to make this work (fast). A recent example of a paper using this method is Zeighami and Soumis (2019), ...

10

What I'm about to suggest is less sophisticated than (and presumably less efficient than) the presolvers Mark L. Stone mentions, but would be relatively easy to implement (assuming you have an LP solver). It assumes that the variables are continuous, not discrete. For simplicity, I'll assume that all inequalities are of the form $a_i'x \ge b_i$ ($i=1,\dots,N$...

9

Unfortunately writing high quality OR code is beyond the reach of most academic settings. This is mainly because: Writing high quality code is very time consuming. The scope of OR code is much better suited to teams of people rather than a lone wolf trying to do everything alone. Because it's time consuming, there's never enough time in academia to do this ...

9

Parma Polyhedra Library supports MIP on fractions. It's based on gmp and is used by gcc and Julia among other projects.

9

I suggest GLPK, which has the advantage of being fully open source and easily available everywhere (as a package on most Linux distribution). Run it from the command line with the --exact option. It is limited to LPs though (no MIPs), and not so easy to use directly from a programming language. From the release notes: GLPK 4.13 (release date: Nov 13, 2006) ...

8

Disclaimer: I have worked for 3 years as an optimization software developer at a utility company and now work for Gurobi. Is the expectation for entry level positions, that the applicant is able to produce high quality code, or is that something that would be learned on the job? There is no expectation because it is often not the case (as Nikos said). ...

7

The journal Socio-Economic Planning Sciences often publishes such OR papers. Some recent examples include papers on public school districting1 and facility location for humanitarian relief.2 INFORMS has a paper competition on "Doing Good with Good OR," which has included work related to managing volunteers3 and Hepatitis B interventions.4 I've also ...

7

Many journals offer best paper awards. For example check out the European Journal of Operations Research best paper awards for some really good papers.

7

This will be opinion based, but I personally like "Handbook of meta heuristics" edited by Michel Gendreau and Jean-Yves Potvin. https://link.springer.com/book/10.1007/978-1-4419-1665-5 There is also "Metaheuristics for Business Analytics" if you are teaching business school students. https://www.springer.com/gp/book/9783319681177

7

Don't know whether this is stating the obvious, but Algorithmic Game Theory by Nisan, Roughgarden, Tardos, and Vazirani has to be in the mix here. Major content would be: (Complexity of) Finding (pure) Nash equilibria, Algorithmic Mechanism Design, the Price of Anarchy (ratio of efficiency between equilibria and optima), Cooperative Games.

7

Solving: why is this solution optimal? As Richard explained, the objective in OR is not "fuzzy" like in ML: we assume an objective that can be evaluated by the computer. Once the problem is specified, there is not much to explain: you can prove optimality or infeasibility directly. Many solution methods attempt to prove optimality, and it is ...

7

If there is one book to know about VRPs, it is: "Vehicle Routing: Problems, Methods, and Applications, Second Edition" (Paolo Toth and Daniele Vigo, 2014)

6

I would suggest reading Numerical Optimization by Nocedal and Wright. It has a pretty neat chapter devoted to SQP methods.

6

SAA is a very widely used technique for stochastic optimization problems and as far as I can see there are two frequently used approaches for the implementation of SAA. Please check Homem-de-Mello's survey paper. I will give you some references on a very specific problem (Influence Maximization) where these approaches are applied. In Lee2015, Wu2017, ...

6

Introduce binary variable $x_{i,j}$ to indicate whether $\beta_{i,j}>0$ and linear constraints: \begin{align} \beta_{i,j} &\le x_{i,j}\\ x_{i,j} + x_{j,i} &\le 1 \end{align} (The big-M here is 1.) The first constraint enforces $$\beta_{i,j}>0 \implies x_{i,j} = 1.$$ The second constraint enforces $$x_{i,j} = 1 \implies x_{j,i} = 0.$$ The first ...

6

Here is one suggestion : Network Flows: Theory, Algorithms, and Applications by Ahuja, Magnanti, Orli. The maximum flow problem is delt with in chapters 6-8, but I suggest you read the ones before if you are not familiar with flows in general. Also, James Orlin (one of the authors, teaches at MIT) has a webpage where you can find solutions to some of the ...

6

Partially overlapping with the other answers, but healthcare is a field where OR has many applications. See for example the Operations Research in Healtcare Journal, or this survey1. References Rais, A. and Viana, A., 2011. Operations research in healthcare: a survey. International transactions in operational research, 18(1), pp.1-31.

6

Is operations research really research?1 discusses how the Design Research paradigm can be used to evaluate OR problems. Reference [1] Manson, N. J. (2006). Is operations research really research?. Orion. 22(2):155-180.

6

For modeling, I would recommend one of the following coursera courses, taught using the MiniZinc modeling language: https://www.coursera.org/learn/basic-modeling and https://www.coursera.org/learn/advanced-modeling For knowing how a solver works, I can recommend the slides of the course "Combinatorial Optimisation and Constraint Programming" at ...

6

In addition to the hyperheuristics mentioned by batwing, you can look for the broader topic of (automatic) algorithm selection and configuration. Generally speaking, algorithm selection is the task of choosing one algorithm among a set of possible ones, based on some information (features) about the problem and instance you want to solve. Configuration is ...

6

You could also use polymake which includes a few exact linear programming libraries (including my own one). It should also be possible to compile SoPlex with GMP support, but I actually never tried it.

6

It sounds like you want something along the lines of a (partial) presolve, which most commercial solvers implement. For example, Gurobi has a presolve accessible from the Python interface which should do what you want, and maybe more. https://support.gurobi.com/hc/en-us/articles/360024738352-How-does-presolve-work- I suppose you can provide a model just ...

6

In my view, mathematical optimization is inherently explainable for various reasons: The model is "white-box", i.e. it is developed by a person defining all the variables and constraints. This means that if a certain constraint is active or inactive, there is a logical conclusion that can be drawn from this. The result is, as you say, provably ...

6

Unfortunately this is a very sparsely documented subject in optimisation literature. The only technical resource I am aware of in my field is this one. Tobias Achterberg's thesis is also a good resource for MILP solver development. The problem is that the number of people who are proficient in solver development is so small that the probability of one of us ...

Only top voted, non community-wiki answers of a minimum length are eligible