Crew and Vehicle Scheduling; Public Transport Line Planning

I signed up now :)

As you know every nonconvex problem could be regarded as a global optimization, depending on the requirement of the application, whether suboptimal solution are useful or not.

There are plenty of non-convex problems such as semi-supervised learning(SVM), (Deep)Neural Net, Sparse PCA, Hyperparameter optimization(eg C and sigma in SVM) etc. and all the combinatorial problems.

Being NP=Hard, often (enhanced) local optimization methods are used. As far as I concerned among to prevailing approaches, deterministic and stochastic, the deterministic is more popular. In this regard you can read more about continuation and homotopy methods, and watch Prof. Boys Convex Optimization II slides.

For the problem size u mentioned, which I regard it as small and medium scale!, branch and bound with some annealing heuristics applicable.

There is a book series from Springer Editions about applications of large scale optimization - http://www.springer.com/series/3701 - I think you will find these books useful for your work.

In my humble opinion this question is not precise enough. To me "large" depends on the application. My field is scheduling and finite capacity production programming. For some companies, programming and optimizing the production of 50 jobs is "large" as the production of 50 jobs takes 2-3 weeks. For some other companies, 50 jobs is what they produce in a single shift. Therefore, "large" is application dependent.

If you are interested, contact me and I can supply several scheduling related applications of algorithms (mainly metaheuristics) for real problems for which the corresponding MILP model has thousands of 0/1 variables.

See the technical report "Problem Definitions and Evaluation Criteria for CEC 2011 Competition on Testing Evolutionary Algorithms on Real World Optimization Problems". It contains 13 interesting real world problems, like for example "Spacecraft Trajectory Optimization Problem" or "Spread Spectrum Radar Polly phase Code Design".

have a look to the following paper:

http://link.springer.com/article/10.1007%2Fs10898-011-9736-8

Hi,

there have been e.g. two LSGO competitions at CEC now, see e.g. please read our publications:

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5585927

@InProceedings{BrestWCCI2010,

author = {J.~Brest and A.~Zamuda and I.~Fister and M.~Sepesy Maucec},

title = {{Large Scale Global Optimization using Self-adaptive Differential Evolution Algorithm}},

journal = {2010 IEEE World Congress on Computational Intelligence, July 18 - 23, Barcelona, Spain},

year = {2010},

pages = {3097--3104}

}

http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4631301&isnumber=4630767

@InProceedings{ZamudaCEC2008,

author = {A.~Zamuda and J.~Brest and B.~Bo\v{s}kovi\'{c} and V.~\v{Z}umer},

title = {{Large Scale Global Optimization Using Differential Evolution with Self-adaptation and Cooperative Co-evolution}},

journal = {2008 IEEE World Congress on Computational Intelligence},

year = {2008},

pages = {3719--3726}

}

Also, the RWIC at CEC is a kind of LSGO since it may take some time to compute these functions. Our results on it were published at the recent SIDE:

http://dx.doi.org/10.1007/978-3-642-29353-5_18

@InCollection{ZamudaLNCS2012,

author = {A.~Zamuda and J.~Brest},

title = {{Population Reduction Differential Evolution with Multiple Mutation Strategies in Real World Industry Challenges}},

journal = {Artificial Intelligence and Soft Computing -- ICAISC 2012},

year = {2012},

volume = {7269/2012},

pages = {154--161},

doi = {10.1007/978-3-642-29353-5_18}

}

There have been other successful and known algorithms at these competitions, you can find them in citations.

And, as an example, I published an example LSGO optimization problem from tree modelling, which has 4509 dimensions as it is encoded, see:

@Article{ZamudaASC2011,

author = {A.~Zamuda and J.~Brest and B.~Bo\v{s}kovi\'{c} and V.~\v{Z}umer},

title = {{Differential Evolution for Parameterized Procedural Woody Plant Models Reconstruction}},

journal = {Applied Soft Computing},

year = {2011},

volume = {11},

pages = {4904--4912},

doi = {10.1016/j.asoc.2011.06.009}

}

@InProceedings{ZamudaWCCI2012,

author = {A.~Zamuda and J.~Brest},

title = {{Tree Model Reconstruction Innovization Using Multi-objective Differential Evolution}},

journal = {2012 IEEE World Congress on Computational Intelligence (IEEE WCCI 2012), Brisbane, Australia},

year = {2012},

volume = {??},

pages = {575--582}

}

Most of codes for these problems is freely available online if you do a google search. Most of these benchsets also compute within a day/week, if you do propper parallellization.

Best Regards.

Packing:

It is model that can be easily understood. It complexity grows with the number of objects to pack. Apart of the number of objects, their shapes and size (equal or not) and the shape and size of the container play a rule.

This problem has applications in telecomunications (coding theory) and in industry: textile, apparel, automobile, aerospace and chemical. For instance, how to cut leather to produce shoes.

For the equal circle packing in a square problem in:

P. G. Szabo, M. C. Markot, T. Csendes, E. Spech, L. G. Casado and I. García New approaches to circle packing in a square. With program codes. Optimization and Its Applications book series, Volume 6. Springer. ISBN: 978-0-387-45673-7, 2007.

has been probe optimality with an interval Branch and Bound method for only n=28,29 and 30. This shows the complexity of the problem.

You have a review in:

Hifi, M., M'Hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Advances in Operations Research 2009 (2009). doi: 10.1155/2009/150624

And a web page devoted to this:

http://www.packomania.com/

I hope this helps.

Best regards,

Leo

In 1976 we solved the optimal short term management problem of Electricity of France.

What plan of production of every plant is envisaged for the next 24 times 3 periods of 20 minutes. When you know that it is 5 times 20 hydraulics groups, simply in the south east of France (The Durance VerDon rivers basin), and that it is links between these variables, the water which leave a reserve arrive in one other, in the Durance river 18 reserves are linked, you arrive to a large scale optimization problem.

The solution of this problem for the Durance Verdon basin only, produce an average of gain for EdF of about one billion of Euro!

HI, i have worked on Semi Optimal problem of flight path control, which can be extended to outer space control..

In research on magnetically confined plasmas for fusion energy, we have done optimizations of three-dimensional plasma shaping for improvements in confinement, stability and steady-state operation. These devices are known as stellarators. We typically optimize either over a 100-200 dimensional parameter space of Fourier coefficients that generate the outer plasma surface or over a larger (up to a few thousand) parameter space that describes the 3D magnetic field coil shapes. Optimization algorithms used include Levenberg-Marquardt, differential evolution and genetic. This effort (STELLOPT) was started at Oak Ridge National Laboratory in the late 1990's for designing compact stellarators and with collaboration from Princeton Plasma Physics Laboratory several years later. This search continues since globally optimized states are quite hard to find and there is ongoing development of the physics optimization targets. For more information, see:

http://www.ornl.gov/sci/fed/Theory/stci/stellarator_theory.html

http://vmecwiki.pppl.wikispaces.net/STELLOPT

It's possible that what you describe (continuing with early returns) has been used, but not in the work I'm familiar with. It is true that there can be a large range of run-times for components of the objective function. This has motivated development of reduced models (or proxy functions) for the more time-consuming parts and then doing the more comprehensive analysis off-line from the optimization. The other issue is that converged 3D plasma equilibria do not exist for some points in the parameter space and so these have to be blocked off. These regions cannot be predicted, but are only determined computationally. These characteristics have caused stellarator designers to gravitate more to incremental stepping methods such as Levenberg-Marquardt or differential evolution rather that more global approaches. However, if there are better methods available, suggestions are welcomed.

Actually, the problem is that we don't know in advance where the regions of equilibrium non-convergence are due to the large size of the parameter space. They are only encountered computationally by the optimizer. I don't recall exactly how this is done now, but believe they are simply flagged by the optimizer as places not to return to in subsequent steps.

There are many related with power systems and dispach problems

Problems related with portfolios and economics are also characterized for having serela dimsensions

There are a lot of problems that naturally have multiple local minima because of inherent nonconvexity. Floudas book, 'Nonlinear and mixed integer optimization: Fundamentals and Applications' discusses so many of the applications in process engineering.