47 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 ...
user avatar
  • 2,665
25 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/ . ...
user avatar
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 ...
user avatar
  • 3,253
23 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 ...
user avatar
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}$. ...
user avatar
19 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 ...
user avatar
18 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, ...
user avatar
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, ...
user avatar
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),$$...
user avatar
15 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?
user avatar
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 ...
user avatar
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} ...
user avatar
  • 141
14 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....
user avatar
  • 21.7k
13 votes

Optimization Problem Libraries

Some other libraries (mainly for MINLP) are: MINLP-Lib. PrincetonLib.
user avatar
  • 1,045
13 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. \...
user avatar
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 = ...
user avatar
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-...
user avatar
12 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 ...
user avatar
12 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, ...
user avatar
12 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 1,381
12 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 ...
user avatar
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 ...
user avatar
  • 5,641
11 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 ...
user avatar
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 ...
user avatar
  • 2,667
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 ...
user avatar
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 ...
user avatar
  • 3,034
10 votes
Accepted

Heuristics for mixed integer linear and nonlinear programs

This is a question, for which google "primal heuristics integer program solver" may give a better answer than I can give myself, but: One of the "definitive" references is this dissertation by Timo ...
user avatar
10 votes

McCormick envelopes and nonlinear constraints

For real $x\in[l,u]$ and binary $b\in\{0,1\}$ the McCormick envelope gives you bounds on $w=xy$ $$\begin{align} lb & \leq w \leq ub,\\ ub+x-u& \leq w\leq x+lb-l. \end{align}$$ By case ...
user avatar
  • 2,665

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