# Tag Info

22

"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

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

13

In my opinion, @Erwin Kalvelagen's blog is a great resource for learning mathematical modeling. He posts a variety of tricks and tips, compares different models with one another, different solvers, etc. What is great about the blog is that its not just textbook theory, its operational research exploration which challenges and/or verifies textbook theory. ...

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$...

10

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) ...

9

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

9

You can consider going through below blogs: i) Erwin Kalvelagen's blog ii) Prof Paul Rubin's blog (https://orinanobworld.blogspot.com/) Interesting things about above blogs is that you can see different applications, their implementations and practical issues while handling them. Another good course is by Prof. Pascal Van on Coursera (https://www.coursera....

9

For an idea of industrial applications of OR write large (minus the gory technical details), you might want to look at a few INFORMS publications. Analytics (aimed at the general public) and OR/MS Today (for INFORMS membership) contain articles about implementations. The INFORMS Journal of Applied Analytics (formerly known as Interfaces) contains primarily ...

8

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 ...

8

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 ...

8

Below are some papers from LocalSolver team members that detail local search approaches for diverse combinatorial optimization problems, with some focus on low-level implementation details: T. Benoist, B. Estellon, F. Gardi, A. Jeanjean (2011). Randomized local search for real-life inventory routing. Transportation Science 45(3), pp. 381-398. pdf (extended ...

8

If I understand correctly, you can obtain the desired linear constraints via conjunctive normal form. Explicitly, suppose $f(\bar{x}_1,\dots,\bar{x}_n)=1$, and let $S_0 = \{j\in\{1,\dots,n\}:\bar{x}_j = 0\}$ and $S_1 = \{j\in\{1,\dots,n\}:\bar{x}_j = 1\}$. You want to enforce \left[\left(\bigwedge_{j\in S_0} \lnot x_j\right) \bigwedge \left(\bigwedge_{j\...

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

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 ...

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)

7

I propose reading the following textbook: Linear Programming and Network Flows by by Hanif D. Sherali, John J. Jarvis, and M. S. Bazaraa I read the first 7 chapters of the book a long time ago (during my Bachelor studies), and I really enjoyed it. Chapter 7 of the book titled THE DECOMPOSITION PRINCIPLE introduces Dantzig-Wolfe decomposition and its ...

7

Honestly, there is not that much in general that I am aware of. The best resource (other than the ones you mentioned) that comes to mind is Fischetti's modeling book "Introduction to Mathematical Optimization", which gives a good overview over many standard problems and various formulations. Otherwise I can recommend some specific ones: LP tricks ...

7

Optimization is a very large area in terms of the types of problems and models. You have taken a course on linear programming, in which (a) the problem is deterministic (you assume that you know at the outset everything required to find an optimal solution), (b) the variables are real-valued and "continuous" (perhaps more correctly, "divisible&...

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

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

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

I took the course 42136 for Benders decomposition and Dantzig-Wolfe (DW) decomposition at Technical University of Denmark. Besides the textbook [conejo2006decomposition] (mentioned by @A.Omidi as well), following materials are recommended: [carøe1998l], chapter 5.1 in [birge2011introduction] for L-shaped Benders Decomposition, in terms of two-stage (...

6

There are many useful references that can be found by googling. In the following you can find some of them: IBM ILOG CPLEX Optimization Studio OPL Language User’s Manual Introduction to Computational Optimization Models for Production Planning in a Supply Chain A Deep Dive into Strategic Network Design PS: About the first mentioned reference, it is about (...

6

I found it quite useful to start (social scientist with background in stats). I had mostly read more complicated papers using linear programming in geographical allocation contexts, and was totally baffled by it. (Relative to stats, in retrospect people using X/Y as decision variables and Greek letters as fixed values is where quite a bit of my confusion ...

5

I agree with Rob Pratt about QSopt-Exact. That's probably the right thing to do if you're doing larger scale solves. I think that you can also do exact LP in Sage (using fractions). Sage is based on Python, so this would be easy to code in, but you do have to download the whole Sage installation at this point. But I don't think this would be quite as ...

5

I think you may be interested in the topic of hyper-heuristics. Very loosely, given a bunch of local search operators for a problem, the idea is to combine those local search operators to form a short chains. Each chain is a sequence of the local search operators, and so each chain itself acts like a heuristic for the original problem. Typically, the work in ...

5

These are called Generalized Upper Bound (GUB) constraints.

5

I know some related sites which provide what you want. The first is A compendium of NP optimization problems, the most related to your question. It has formal definitions of the problems and papers containing algorithms for solving them. The second is mostly related to mathematical programming and constraint programming, Global Constraint Catalog. It has ...

5

A good starting point is to look at the following Wikipedia resources: https://en.wikipedia.org/wiki/Protein_design https://en.wikibooks.org/wiki/Structural_Biochemistry/Proteins/Protein_Folding_Problem The biochemistry problematic is described and the related mathematical optimization problems are discussed. Now, the state of the art on this topic can be ...

5

The transformation is mentioned in Ahuja, Magnanti, and Orlin, Network Flows, Exercise 16.25(b).

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