# Tag Info

18

For context: most (if not all) major LP solvers are built on 2 algorithms: the simplex method, and the interior-point method. The simplex method is intrinsically sequential: you're doing a lot of (cheap) operations called pivots, and the matrices involved are usually sparse. At each pivot, you essentially perform a rank-one update of a sparse LU ...

9

Using the max operator, your objective function has directional derivatives but is not smoothly differentiable. For instance, if $x$ is scalar and $g(x) = x-2$, then at $x=2$ the max term has directional derivative 0 in the direction of decreasing $x$ and $c$ in the direction of increasing $x$. For a gradient-based algorithm, this makes the value of the ...

9

Let binary decision variable $x_{i,g}$ indicate whether node $i\in\{1,\dots,N\}$ appears in group $g\in\{1,\dots,N\}$, and let binary decision variable $y_{i,j,g}$ indicate whether edge $(i,j)$ appears in group $g$. You want to maximize $$\sum_{i<j}\sum_g w_{i,j} y_{i,j,g}$$ subject to \begin{align} \sum_g x_{i,g} &= 1 &&\text{for all $i$} \...

6

Yes. The ruggedness of a landscape is a measure of how much variability is observed between neighbouring solutions, and it can be computed using the landscape correlation function. Rugged landscapes (with a very low correlation) typically have lots of local minima and are more difficult to traverse than smooth landscapes (correlation close to 1). For a fixed ...

4

I'll try to give a geometrical approach. You are considering a polyhedron $$P = \{x \in \mathbb{R}^{n} \ | \ Ax \leq b \}.$$ where $b \in \mathbb{R}^{m}$ and $A \in \mathbb{R}^{n \times m}$. (I'm using $Ax$ and not $A^{T}x$ to match the dimensions in the OP). The easy case: no degeneracy Let's assume that there is no primal degeneracy, i.e., no ...

4

You just seem to have hidden a long list of constraints of the form $(x_i=j) \Rightarrow \text{equalities}_{ij}$ Introduce a binary matrix $C_{ij}$ with $\sum_j C_{ij}= 1$ and $C_{ij} \Rightarrow \{x_{i} = j, \text{equalities}_{ij}\}$ To model the binary implication you can use big-M modelling, e.g. $-M(1- C_{ij})\leq x_{i} - j\leq M (1-C_{ij})$ and similar ...

3

From the looks of it (simple feasible set, convex objective, gradient available), Frank-Wolfe indeed makes a lot of sense here. I can point out that there exist many variants of the algorithm, and that several are implemented in this recent Julia package. This can give you a quick way to experiments various algorithmic configurations. If you do decide to ...

3

Your bisection code is returning a tuple of [a,b] but in your main function you are only retrieving a, which should be causing the type error. There's also another bug in your bracket_minimum function - it can potentially get stuck in an infinite loop if your return condition is never satisfied. Ideally you want to have max iterations and return no solution ...

3

A short little note about computing gaps just appeared in 4OR: Laporte, G., Toth, P. A gap in scientific reporting. 4OR-Q J Oper Res (2021). https://doi.org/10.1007/s10288-021-00483-0

3

First question: Theoretically, yes (assuming you are talking about the reduction factor per pair of observations). Practically speaking, there is a minimum gap you can have between $c$ and $d$, below which rounding error makes the comparison of $f(c)$ and $f(d)$ too dicey to trust. So the reduction factor per pair of iterations approaches something slightly ...

3

For the automatic solver configuration, I know of this reference (there may be a journal version): A learning-based mathematical programming formulation for the automatic configuration of optimization solvers. They also cite further references on the topic.

3

By dual feasibility, all that the authors mean is that $(x^{k+1}, \lambda^{k+1})$ in Equation (1) satisfies the stationarity equation in the KKT optimality conditions for the problem shown at the top of your question. Recall that the stationarity equation for the problem is to find $x, \lambda$ such that $$\nabla f(x) + A^{\top} \lambda = 0$$

2

A proof that $x^*$ is optimal can be achieved by a Taylor expansion around $x^*$ at optimality. Observe that $$f(x^*+p) = f(x^*) + p^\top f'(x^*) + \frac12p^\top f''(x^*)p$$ Note that at a local optimum $\nabla f=0$ and given that $f$ is strictly convex it is a PD matrix with positive eigenvalues. Thus the third argument involving the Hessian $>0$ thereby ...

2

Permutation matrices will preserve the feasible region. Since you are not modifying the objective function, the solution will also be the same.

2

I hesitate to suggest it, since gradient methods tend to be faster than non-gradient methods, but the Nelder-Mead "simplex" algorithm is easy to code and might be worth a try.

2

When you have only box constraints I don't think Frank Wofle is very efficient. Frank Wolfe can handle more complex constraints. You should try a quasi newton algorithm like l-bfgs-b or a truncated newton conjugate gradient algorithm with projection.

2

Assuming you are fine with turning the warnings off, you can change the verbosity level of the data consistency checks that you get from docplex by changing the value of datacheck parameter. You can read more about it in the IBM doc on data consistency. from docplex.mp.model import Model mdl = Model(name='my_model') ... mdl.parameters.read.datacheck = 0 # ...

2

This is by no means a complete list, but this is some of the best stuff for this mathematical structure: Open source: Couenne, SCIP Commercial and free: Octeract Engine (our own solver). Commercial and not free: Gurobi, Lindo Global, Baron, Antigone. You might be able to get a free version of Gurobi (and maybe some of the other non-free ones) if you are an ...

2

A) I think you might want to use a multi-level score (something like our BendableScore): SOFT: maximize rank 1 assignments SOFTER: maximize rank 2 assignments SOFTEST: maximize rank 3 assignments Otherwise, three rank 2 assignments can be considered better than one rank 1 assignments (which I presume is not the requirement). Where it gets more interesting ...

2

Given that your function is apparently unimodal (single local minimum, which is global), you might try golden section search. The first four function evaluations result in about a 40% reduction in the initial interval. Each additional function thereafter again reduces the remaining interval by about 40%.

1

As far as I know, this is a special type of blocking job shop problem. Take a look at this paper: https://link.springer.com/article/10.1007/s10878-014-9723-3 If you search for BJS-RT you will find more literature that is freely available. Once you have formulated it as BJS, there are different ways of solving it. Heuristics or for smaller instances CP or ...

1

The problem is a combination of two problems: The first is the transport with the cranes and the non crossing constraints (non colusion condition). Check out this paper: N. Boysen, D. Briskorn, S. Emde Parts-to-picker based order processing in a rack- moving mobile robots environment Eur J Oper Res, 262 (2) (2017), pp. 550-562 as a good starting point into ...

1

If you really want to ignore them then you can often set the warning output to null (or similar) https://www.ibm.com/docs/en/icos/20.1.0?topic=cm-warning-method-1 From where/how are you calling cplex?

1

Ipopt and similar solvers rely on criteria such as KKT to find out whether they converged against a point which satisfies 2nd order optimality conditions. However for the sake of not running forever and in the face of finite precision of Floating point numbers it does not make sense to continue running. So it stopped early and reported a failure. Imagine a ...

1

I'm not sure if this is exactly on point, but there is a paper by Carvajal et al. on the use of parallel trees (with communication between them) for solving integer programs. You might also be interested in reference [10] in their paper (Koch et al.), which discusses "racing ramp-up", a technique adopted by CPLEX a while back, in which you ...

1

Not sure about operations research but there is a club called stackexchange in clubhouse. Do join and you can start a topic of your own. https://www.clubhouse.com/join/stackexchange/FrzrVmPK

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