48
votes
Accepted
Optimization Problem Libraries
Quadratic assignment problem
Vehicle routing problem also at HEC
Traveling salesman
Graph partitioning
Quantified Boolean formulas
Constraint solvers
Shortest paths
Mixed integer programming
Train ...
- 2,705
26
votes
Accepted
How to formulate (linearize) a maximum function in a constraint?
(I'm going to change $c$ to $x$ in my answer, since $c$ is usually used for cost coefficients, not decision variables.)
We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new ...
- 13k
26
votes
Optimization Problem Libraries
Here is a start. Please add to this.
BOLIB: Bilevel Optimization LIBrary of Test Problems https://eprints.soton.ac.uk/436854/1/BOLIBver2.pdf
CBLIB: The Conic Benchmark Library: http://cblib.zib.de/ . ...
- 12.8k
24
votes
Accepted
Deep Reinforcement Learning for General Purpose Optimization
"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 ...
- 4,068
22
votes
Accepted
Cubic programming and beyond?
In addition to the excellent answers that are already posted, I want to add that for the pragmatic optimizer, quadratic may already be sufficient.
For example, the cubic constraint $x^3 \le x$ may be ...
- 6,033
20
votes
Accepted
Linearize or approximate a square root constraint
This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP.
Specifically, due to $x_{ij}$ being binary, $x_{ij}^2 = x_{ij}$. ...
- 12.8k
19
votes
Accepted
Trustful Nonlinear Programming
Local nonlinear optimization solvers, such as IPOPT, are not guaranteed to find a feasible point for problems that are feasible. That is certainly the case for problems with non-convex constraints, ...
- 12.8k
17
votes
Cubic programming and beyond?
I am not sure whether you are looking for polynomial optimization like Introduction to concepts and advances in polynomial optimization by Martin Mevissen, or polynomial optimization by Hoang Tuy?
- 5,889
16
votes
Nonlinear integer (0/1) programming solver
Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, ...
- 12.8k
15
votes
Accepted
Sum of Max terms maximization
If your problem is reasonably small then one relatively simple approach is to reformulate the objective as a MIP, under a big-M assumption.
Suppose that our objective is to maximize $$\sum_i g_i(x),$$...
- 1,112
15
votes
How can we write a binary variable as a power to a constant number?
If you check the two cases for $x_{i,j}$, you will see that you can rewrite the expression as a linear function of $x_{i,j}$:
$x_{i,j}=0$ yields $1-0.3^0=0$
$x_{i,j}=1$ yields $1-0.3^1=0.7$
So $1-0....
- 29.8k
14
votes
Optimization Problem Libraries
Some more libraries:
Biq Mac Library: a Binary quadratic and max cut Library: http://biqmac.uni-klu.ac.at/biqmaclib.html
OR Library: a collection of test data sets for a variety of Operations ...
- 1,112
14
votes
Accepted
How to formulate a problem to prove/disprove convexity?
Based on the comment by Ryan Cory-Wright, you could formulate it like this.
Verify convexity of the domain $\{x \in X : g(x) \le 0\}$
Solve the following problem, and check the optimal value.
\...
- 6,033
14
votes
Nonlinear integer (0/1) programming solver
Maybe I am missing something but it looks like there is no need for a library:
\begin{align}
\sum_i \sum_j \sum_k x_{ji} y_{kj} cost(i,k)&=\sum_i \sum_j x_{ji} \sum_k y_{kj} cost(i,k)
\end{align}
...
- 141
13
votes
Accepted
CPLEX non-convex Quadratic Programming algorithms
The best publicly available CPLEX global QP algorithm description I am aware of is the tutorial presentation by Ed Klotz of IBM at the March 2018 INFORMS Optimization conference.
Performance Tuning ...
- 12.8k
13
votes
Optimization Problem Libraries
Some other libraries (mainly for MINLP) are:
MINLP-Lib.
PrincetonLib.
- 1,065
13
votes
Cubic programming and beyond?
+1 for @MarcoLübbecke
But in addition, this is also known as "Polynomial Programming". Also look at algebraic geometry and semialgebraic sets, and sum of squares optimization: Wikipedia and Lall, ...
- 12.8k
13
votes
Dedicated solver for convex problems
Are you formulating your model with nonlinear expressions that just happen to be convex?
Or can you provide conic normal forms, maybe using a modeling tool based on displicined convex programming? In ...
- 2,306
13
votes
Accepted
Do the KKT conditions hold for mixed integer nonlinear problems?
No, the KKT conditions aren't applicable to mixed-integer programming problems with integer variables. The theory behind the KKT conditions depends on the objective and constraint functions being ...
- 781
13
votes
Accepted
Why does a Max constraint work, but this non-negativity constraint does not?
A rigorous way to look at this problem is to consider the polyhedra corresponding to your constraints (I linearized the 'max' for the second one):
$$P_1 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t = ...
- 2,295
13
votes
Trustful Nonlinear Programming
Oh boy. Adding to Mark's great answer, I'll add some fun facts on what can go wrong with IPOPT and feasibility, and provide us with endless nights of entertainment:
The linear system solver gets ...
- 11.9k
12
votes
How to linearize the product of two continuous variables?
Unlike cases where one or both of the $x$ and $y$ are binary, you won't be able to truly (i.e. exactly) linearize this. https://stackoverflow.com/questions/49021401/how-to-linearize-the-product-of-...
- 2,362
12
votes
Accepted
IPOPT with HSL vs MUMPS
This question happened to appear only a couple days after Byron Tasseff, Carleton Coffrin, Andreas Wächter, and Carl Laird (the last two are the original authors of IPOPT together with Larry Biegler) ...
- 1,065
12
votes
Accepted
Solvers and saddle points
While iteratively approximately solving the first order Karush-Kuhn-Tucker conditions, many (nonconvex) nonlinear solvers "roll downhill", i.e., enforce descent (for minimization) of the objective ...
- 12.8k
12
votes
Accepted
Can Tuning Knitro Solver Considerably Make A Difference?
(Disclaimer: I am a developer of Knitro)
When developing a NLP solver, we set the default values for the different options so as to minimize the resolution time in average for different class of ...
- 1,471
11
votes
Optimization Problem Libraries
Some more:
Atamturk datasets on fixed-charge flow, lot sizing, mixed-integer knapsack, and more
Combinatorial Auction Test Suite (CATS)
National Traveling Salesman Problems
VLSI data sets: Another ...
- 5,806
11
votes
Cubic programming and beyond?
Thanks to everyone who answered this question for introducing the concept of polynomial programming.
From there I have found two papers that link cubic programming to convex programming, and provide ...
- 5,341
11
votes
Suggested Resources for Non-Linear Optimization
There are plenty of courses and books out there.
For convex optimization I'd take a look into Boyd's & Vandenberghe's lecture which also has a good accompanying script.
The lecture/book from ...
- 2,727
11
votes
Is a mathematical programming problem with no objective function an optimization problem?
Yes. But some software may require explicit specification of an objective, which can be a constant.
Yes. An optimization solver will attempt to find a feasible solution. Any feasible solution is ...
- 12.8k
10
votes
Accepted
KKT inequality conditions
If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since ...
- 3,449
Only top scored, non community-wiki answers of a minimum length are eligible