# Tag Info

41

Quadratic assignment problem Vehicle routing problem also at HEC Traveling salesman Graph partitioning Quantified Boolean formulas Constraint solvers Shortest paths Mixed integer programming Train timetabling Set covering and packing Beasley's OR library with many problems Maximum clique, Maximum independent set, minimum vertex cover, vertex coloring ...

22

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/ . Twitter at https://twitter.com/cblibtw COMPlib: COnstraint Matrix-optimization Problem library (Nonlinear SDPs, control system design, and related problems) ...

21

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

20

(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 binary decision variable $y$, which will equal 1 if $x_1 > x_2$, will equal 0 if $x_1 < x_2$, and could equal either if $x_1 = x_2$. Let $M$ be a constant ...

20

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}$. Therefore, the left-hand side is the two-norm of the vector over $i \in I$ having elements $\sqrt{a_{ij}} x_{ij}$. I don't know whether this is the best way ...

19

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 replaced by $xy \le x$ and $y=x^2$, which are both quadratic constraints. Note that these constraints are non-convex, which may not be desirable.* Sometimes non-...

18

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, and I believe may even occur sometimes for problems having convex nonlinear constraints. The starting (initial) point is often important in determining whether or ...

16

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, Gurobi 9.x, and BARON, among others. Option 2: Step 1 Linearize the products of binary variables, per How to linearize the product of two binary variables? . <...

15

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),$$ where each $g_i(x):=\max_j a_j^{i\top} x+b^i_j$ is the maximum of some affine functions. We can model this by introducing auxilliary variables $\theta_i$ such ...

15

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?

14

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} Now since $\sum_k y_{kj}=1$, exactly one row is 1, the others zero. We pick the best one: $$=\sum_i \sum_j x_{ji} \max_k cost(i,k)$$ Since $\sum_j x_{ji}=1$ we ...

13

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 Research problems: http://people.brunel.ac.uk/~mastjjb/jeb/info.html SIPLIB: a collection of stochastic integer programming problems: https://www2.isye.gatech.edu/~...

13

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. \begin{align} \max\qquad& g\left(\lambda x + (1-\lambda) y\right) && \small\textrm{(maximize constraint violation of convex combination)}\\ \text{s.t.}\...

13

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 = x_{t-1}+y_{t-1}-z_{t-1}, x_t \geq 0 \right\}$$ and $$P_2 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t \geq x_{t-1}+y_{t-1}-z_{t-1}, x_t \geq 0 \right\}.$$ In ...

12

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-two-float-variables goes through the approximation approach to this issue.

12

Some other libraries (mainly for MINLP) are: MINLP-Lib. PrincetonLib.

12

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 for Cplex’s Spatial Branch-and-Bound Solver for Global Nonconvex (Mixed Integer) Quadratic Programs ABSTRACT: MILP solvers have been improving for more than ...

12

+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, 2011. This leads to such cool things as Sum of Squares Programming (optimization), for which Semidefinite Programming relaxation comes into play.

12

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 that case, some solvers might be able to exploit that! Disciplined geometric programming is another way to teach solvers how to exploit convexity in nonlinear ...

12

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 function for algorithms which attain and maintain primal feasibility, or improvement in a merit function (or similarly with filter methods) for algorithms which ...

12

(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 problems (CUTer, QPLIB, Mittelmann instances, etc.). When working on a specific problem, it often pays to find appropriate parameters to improve the resolution time....

12

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 stuck. A timeless classic, especially for MUMPS. It will suddenly slow down to a crawl for no apparent reason. It can also fail outright, which can cascade to ...

11

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 differentiable but functions of integer variables aren't differentiable. It's certainly possible to enforce integrality constraints using continuous variables. ...

11

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 Nemirovsky & Ben-Tal is also very good. If you are looking into algorithms that can be used for general (non-convex) problems, you might want for example look ...

11

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 optimal. Feasibility problem. Some optimization modeling systems or optimization software require an objective to be provided. In such case, you can specify the ...

10

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 the KKT's are the first-order necessary conditions for optimality. For convex nonlinear optimization, you are better off using sequential quadratic ...

10

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

10

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 analysis you can see that this is equal to $w=xb$, so you will indeed solve the problem.

10

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 collection of 102 TSP instances GiC Data Sets Update: I made a GitHub repository and added all of these references. there.

10

The problem might be @(x) in the first line of the function. Adding this creates an anonymous function, while MATLAB simply expects a numerical vector as output. Removing @(x) should resolve the issue. Using ceq = [] should not give any problems.

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