# Black Box Optimization Problems Homework

A principal challenge in optimization practice is how to optimize in the absence of an algebraic model of the system to be optimized. We are interested in problems for which algebraic models are (1) intractable to conventional optimization software (for instance, due to discontinuities, non-smoothness, or excessive computational cost of a function evaluation), or are (2) entirely unavailable (as in the case of many experimental systems and operating processes to be optimized). We refer to systems of this sort as ``black-box systems'' and assume that the black box can be queried through a simulation or experimental measurements that provide a system output for specified values of system inputs.

Our work in this area focuses on the development of methodologies that rely on statistical and machine learning techniques to handle experimental and simulation data in conjunction with deterministic optimization methods to aid decision-making and model-building for black-box systems.

The methods we develop have been applied to problems in bioinformatics, portfolio optimization, protein-ligand docking, carbon capture and sequestration, parameter tuning for optimization solvers, antenna optimization, optimization of polymerase chain reactions, protein structure alignment, and powder diffraction.

## Derivative-free optimization

Obtaining derivative information for many complex and expensive simulations is impractical. To tackle such systems, we maintain a comprehensive library of existing derivative-free algorithms, and perform extensive studies of their performance in various domains. Results from a recent comparison of 22 software implementations are summarized here.

In addition, we are developing novel algorithms to address classes of derivative-free optimization problems while performing the fewest number of experiments.

## Learning process models

We are developing a model generation methodology that uses derivative-based and derivative-free optimization alongside machine learning and statistical techniques to learn algebraic models of detailed simulations and experimental systems. Once a candidate set of models is defined, they are tested, exploited, and improved through the use of derivative-free solvers to adaptively sample new points. Of particular importance is the algorithm's ability to generate models that are simple yet accurate. We have implemented this strategy in ALAMO, a code for the Automatic Learning of Algebraic MOdels.

## Simulation optimization

An added complication in the case of discrete-event simulations is the inherent stochasticity associated with their outputs. Our goals in this area are to (1) compile and compare existing methods for simulation optimization on new problem testbeds, and to (2) provide algorithms and implementations that handle uncertainty in data in a robust manner while locating optimal solutions.

### Related Publications

- Amaran, S., N. V. Sahinidis, B. Sharda, and S. J. Bury, Simulation optimization: A review of algorithms and applications,
__Annals of Operations Research__, 240, 351–380, 2016. - Ploskas, N., C. Laughman, A. U. Raghunathan, and N. V. Sahinidis, Optimization of circuitry arrangements for heat exchangers using derivative-free optimization,
__Chemical Engineering Research and Design__, accepted, 2017. - Rios, L. M. and N. V. Sahinidis, Derivative-free optimization: A review of algorithms and comparison of software implementations,
__Journal of Global Optimization__, 56, 1247–1293, 2013. - Shah, S. B. and N. V. Sahinidis, SAS-Pro: Simultaneous residue assignment and structure superposition for protein structure alignment,
__PLoS ONE__, 7(5): e37493, 2012.

## Winter 2009 - MAT-180-1 (Special Topics): Mathematics for Decision Making: An Introduction

**What will you do with your degree in mathematics?** Chances are that you are looking forward to start a career in a company, in one of a wide variety of industries. It is a fact that many companies hire mathematicians because of their ability to **analyze business processes** (such as production, logistics, finances). We create mathematical models for the processes and **use mathematical software** to solve them. This allows us to **make good (or even optimal) decisions** on how to change these processes to make them better.

**In this class** you will learn about basic techniques of optimal decision making, which will help to prepare you for such a career. It is a self-contained class without any prerequisites other than familiarity with rigorous mathematics.

You will learn to use a convenient **mathematical modeling language** that allows to write down a mathematical model of a business process in the computer. We will then use **mathematical optimization software** to solve this model. This software is amazingly powerful, it will solve most models that we try within just a second. We will use this software as a **black box** only. (To learn what is inside, take MAT-168 in Spring, followed by a number graduate-level courses where we explain this exciting optimization technology...)

Some business processes, however, have an enormous complexity, which will create huge mathematical models. In these cases, just using the black box of mathematical optimization software will not be good enough. There are many exciting ways how to fix this. In this class, we will mostly be studying special cases, such as shortest route and network problems. For these special (but important) cases, we will show that there are **beautiful and super-fast "combinatorial" algorithms** that are much faster (and simpler!) than the black box. We will study **mathematical proofs** that establish that the algorithms are correct (always produce an optimal solution) and efficient.

**For students who have already taken MAT-168 (Math. Programming),** this class is also an excellent choice. You have already learned about network flows; we also cover this topic, but we introduce different algorithms (such as the primal-dual algorithm rather than the network simplex algorithm), so your knowledge will be extended.

**For computer science majors,** this class is also very beneficial, as we discuss important and fundamental combinatorial optimization algorithms, efficient data structures, and their complexity analysis.

If you have any questions on the class, please write an email () or stop by my office (MSB 3143), I will be happy to answer them.

## Technical description of the class

**Textbook:** I will be teaching material that corresponds to selected chapters of the book *Combinatorial Optimization*, by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, which is also **suggested reading** for this class. **It is not required to buy the book, as I will give out copies of my notes before each class.**

**Prerequisites:** The class has **no formal prerequisites**. The class should be suitable for all math, computer science, and engineering majors. I will assume familiarity with rigorous mathematics, in particular the ability to follow and write mathematical proofs; also I will assume basic familiarity with a programming language of your choice.

**Relation to other courses:** This class complements, but is independent of MAT-145 (Combinatorics) and MAT-168 (Mathematical Programming).

**Grading:** Grading will be based on homework (20%), one programming project in the general-purpose programming language of your choice (20%), two 50-minute written midterms (30%; **I drop the lower grade of the two midterms**), and a final 50-minute written exam (30%).

**I reserve the right to replace all or some of the in-class midterms and the final exam by take-home exams.**

## Syllabus

Week | Topic | Chapter |
---|---|---|

1(Jan 6, 8) | Decision Making, and the rôle of Mathematical Optimization. Deterministic vs. stochastic, continuous vs. discrete, linear vs. nonlinear, combinatorial vs. unstructured, single-criteria vs. multi-criteria optimization problems. Introduction to modeling languages and black-box optimization software, using the ZIMPL modeling language and the SoPLEX and SCIP solvers. | |

2(Jan 13, 15) | First combinatorial examples: The Shortest Path Problem; the Euclidean Traveling Salesperson Problem; the Euclidean Matching Problem. Their optimization models. Practical efficiency: Measuring the running time of black-box optimization software. | 1.1 1.2 2.2 |

3(Jan 20, 22) | What to do when the black box is too slow. A specialized algorithm for the Shortest Path Problem: Feasible potentials; Ford's algorithm. Correctness proof. Theoretical efficiency (complexity theory) in the Random Access Machine model of computation; asymptotic notation using Landau symbols ("big O"). Complexity analysis of the algorithm. | 2.2 9.1–9.9 |

4(Jan 27, 29) | More algorithms for the Shortest Path Problem: The Ford–Bellman algorithm, Dijkstra's algorithm. Correctness and efficiency of the algorithms. | 2.2 |

5(Feb 3, 5) | Mid-term exam I (written).After the quiz: | 2.2 |

6(Feb 10, 12) | Introduction to network flow problems. Maximum flows and minimum cuts. Auxiliary digraphs, and the augmenting path algorithm for the Maximum Flow Problem. Shortest augmenting path algorithm. | 3.1 3.2 |

7(Feb 17, 19) | Applications of Max-Flow–Min-Cut: Bipartite matchings and Kőnig's Theorem; flow feasibility problems. | 3.3 |

8(Feb 24) | Mid-term exam II (written) | |

(Feb 26) | Minimum-cost flows. Optimality conditions. A primal algorithm: The Augmenting Circuit Algorithm. | 4.1 4.2 |

9(Mar 3, 5) | The primal-dual algorithm for minimum-cost flows. Correctness and efficiency. | 4.3 |

10(Mar 10, 12) | A look at the Traveling Salesperson Problem. The cutting-plane method. Equivalence of separation and optimization. Separation of subtour constraints and comb inequalities. | 6.7 6.8 7.1–7.4 |

(Mar 20) | Final exam (written), on Friday Mar 20, 3:30 pm. |

## Course materials

### Week 1

Slides of Lecture 1, ZIMPL manualSlides of Lecture 2, Example ZIMPL file

### Week 2

Slides of Lecture 3

Slides of Lecture 4, Models for the 6-city TSP

**Homework** (as announced in the lecture, due next Thursday): Study the ZIMPL manual carefully. Do the case study on the last slide of Lecture 4, on GPS navigation systems.

### Week 3

Slides of Lecture 5

Slides of Lecture 6, Models, data, and scripts for the pen plotter problem

**Homework (written)** as announced in the lecture, due next Thursday, see the last slide of Lecture 6.

### Week 4

Slides of Lecture 7 (**link corrected**), Model of the matching formulation of the pen plotter problem

**Homework (oral)** as announced in the lecture, due this Thursday: Run the Ford algorithm for the two given examples.

Slides of Lecture 8

**Homework (written)** as announced in the lecture, due next Thursday (Feb 5): Homework problems 1, 2, 3 at the end of the slides.

**Additional, non-required homework (training for the 1st midterm):** Do some of the modeling exercises from the copies I gave out. If you turn these in by Tuesday (Feb 3), I will grade/comment and return them by Thursday (Feb 5).

### Week 5

Slides of Lectures 9 and 10

**Announcement:**

The first **mid-term exam** will be a take-home exam, given out on Thursday (Feb 5) and due Tuesday (Feb 10)

### Week 6

Slides of Lecture 11

Slides of Lecture 12

**Homework (written)** 4 problems as announced in the lecture, due next Thursday (Feb 19).

### Week 7

Slides of Lecture 13, 14

**Programming homework:** As announced in the lecture (see last slide of Lecture 13), due on **March 17**; data files are available here.

### Week 8

Slides of Lecture 15, 16

### Week 9

Slides of Lecture 17

Slides of Lecture 18, 19

### Week 10

Slides of Lecture 20

## 0 Replies to “Black Box Optimization Problems Homework”