Questions tagged [optimization]

For questions involving mathematical problems that aim to minimize or maximize some objective function, possibly subject to one or more constraints.

Filter by
Sorted by
Tagged with
13
votes
1answer
293 views

Categorization of optimization models

For many families of optimization problems there is some sort of classification scheme. I am thinking about the triple notation for machine scheduling introduced in "Optimization and approximation in ...
12
votes
3answers
779 views

What is a “hard problem” in the context of Mixed-integer programming?

As a practical (real-world problems) point of view, it's important we could solve optimization problems as quickly as possible (for instance, to release a daily schedule). Maybe a problem with many ...
12
votes
3answers
1k views

Allocating credit card points

I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards ...
12
votes
2answers
488 views

Expressing a chain of boolean ORs using ILP

How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables ...
12
votes
3answers
330 views

How to handle real-world (soft) constraints in an optimization problem?

Cross-posted at Stats.SE (aka Cross Validated) I am working on a problem which involves optimizing for minimum power consumption in a large compressor network interconnected through pipelines (think ...
12
votes
3answers
1k views

Does it make sense to use strict equality constraint in optimization?

Once I learned from some post that the strict equality constraint in optimization problem does not make much sense. We should always use $\le$ constraint. How far this is true. If I must have a ...
12
votes
3answers
2k views

Performance of a branch and bound algorithm VS branch-cut-heuristics

I was trying to solve a moderate scheduling model using an open-source solver. I did two different ways. A) using pure branch and bound algorithm (disable all options). B) using the default setting ...
12
votes
3answers
1k views

YALMIP-like modeling environment in Python

What are the handiest optimization parsers out there? Is COIN-OR's PyPy being used actively? I am currently trying to do an optimization project in Python, but I am used to using MATLAB + YALMIP ...
12
votes
2answers
329 views

Expressing an implication as ILP where each implication term comprises a chain of boolean ORs

Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
12
votes
1answer
642 views

Difference between lazy callbacks and using lazy constraints directly

I'm trying to use lazy constraints to solve an optimization problem. In some software such as CPLEX or GUROBI, they have some tools to handle them directly (in the original model) or using callback ...
12
votes
2answers
477 views

How to handle an IP sub-problem with an objective function in Benders Decomposition

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) ...
12
votes
2answers
119 views

Run repeatable numerical tests in the cloud

In numerical tests of optimization algorithms, one often reads "We used a XY computer with X GB RAM for the experiments". Usually, when I want to compare my results with theirs, I do not have an XY ...
12
votes
2answers
449 views

Convex Maximization with Linear Constraints

I am doing active research in convex maximization w.r.t. linear constraints. There are many cases which can be efficiently approximately solved, e.g., convex quadratic maximization, log-sum-exp ...
12
votes
1answer
1k views

If-then constraints in MIP programming

For continuous variables $x$ and $y$, the constraints are: ...
12
votes
1answer
257 views

Simplest way to eliminate redundant constraints due to a new cut

I have a polyhedral set for constraining $x$: \begin{align} \mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \} \end{align} where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the ...
12
votes
2answers
153 views

Is there a known MILP to schedule routes after routes are made

I am trying to create a mixed integer model that has as an objective to schedule routes for a single vehicle within its timeline. Let me try to elaborate. Let's say we have a single vehicle vrp and ...
12
votes
1answer
201 views

Looking for books in the same style as Hans Kellerer 2004, Knapsack Problems

I really enjoyed reading Hans Kellerer, David Pisinger, Ulrich Pferschy 2004 book Knapsack Problems. Can anybody recommend books in a similar style, about some other classes of problems / optimisation?...
11
votes
3answers
5k views

Soft constraints and hard constraints

The terms "soft constraints" and "hard constraints" are used in the context of optimization modeling. Is there any standard way to figure out which is which in some of the complicated models?
11
votes
2answers
3k views

Is it necessary to study rigorous math courses in OR?

I am a business student with engineering background and I am studying papers published in some journals like Management Science, Operations Research, Math of OR and they use some notations and ...
11
votes
3answers
636 views

How can I estimate the monetary savings of a operation research application?

Developing operation research applications for industry clients is often very costly since it is in my experience often a custom special development for the client. The cost of developing a running ...
11
votes
1answer
2k views

An approximate answer to the right question or an exact answer to the wrong question

There is a quote from John Tukey in one of his papers on data analysis Far better an approximate answer to the right question, which is often vague, than an exact answer to the wrong question, ...
11
votes
2answers
1k views

Linear programming: objective function with “buckets”

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. This problem was ...
11
votes
3answers
291 views

Is my approach to my internship project good? Optimal allocation of product across stores, constrained optimization

Context: I am a CS student currently in a non-CS internship (logistics, supply chain). My manager wants to leverage my knowledge of programming to build a program to solve the following problem: As ...
11
votes
2answers
354 views

How difficult is it to understand a Machine Learning method based on integer optimization?

I'm trying to understand a paper called "Supersparse Linear Integer Models for Predictive Scoring Systems" by Ustun, Tracà and Rudin, who introduce a really interesting method for generating an ...
11
votes
1answer
145 views

Branch and Price algorithm is exact?

I know that the Column Generation algorithm delivers an exact solution when you are solving a linear programming optimization problem. I want to know that, does this column generation approach deliver ...
11
votes
1answer
558 views

What are the pros and cons of LocalSolver?

LocalSolver is a company which provides a global optimization solver, combining exact and heuristic techniques. The benchmarks on their website are quite impressive. For example, they claim they can ...
11
votes
1answer
367 views

Suggested Resources for Non-Linear Optimization

I recently completed an undergraduate course in Linear Programming and Operations Research. I am willing to look into advanced concepts and Non-Linear Optimization algorithms and also, their method of ...
11
votes
1answer
281 views

Expressing a chain of boolean ORs using ILP involving different variables

How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that ...
11
votes
1answer
303 views

Minimize number of pieces required to cover distances, with overlap

The specific optimization problem I'm trying to solve is this: Find the minimum integer number of $2$m pieces required to cover $2$ or $4$ distances of length $D$ given that adjacent pieces must have ...
11
votes
2answers
132 views

Is a “multistep” or “multiphase” Newsvendor model possible?

I'm trying to address the question of how many times should I order a product from my supplier, assuming highly stochastic demand. In my mind there would be something like the Newsvendor model, but ...
11
votes
2answers
311 views

Decoding a Deep Neural Network as an Analytical Expression for Optimization Purpose

This post is not really about a specific question but rather a topic I am curious about to know more. We know that when it comes to integrate machine/statistical learning with optimization for the ...
11
votes
2answers
81 views

In portfolio optimization, how do we estimate the variance of a new asset?

Say I want to do Portfolio Optimization using the mean-variance approach (i.e Markowitz model), but that some of my assets are new with no returns history. I can use a judgmental (expert knowledge, ...
11
votes
1answer
280 views

Linearization of the product of two real valued variables - Binary expansion approach

I want to minimize the following objective function: \begin{align}\min &\quad x\cdot y\\\text{s.t.}&\quad2 \le x \le 5\\&\quad5 \le y \le 10.\end{align} Since the objective function is ...
11
votes
0answers
107 views

Armijo Line Search Parameters

I am trying to compare many unconstrained optimization algorithms like gradient method, Newton method with line search, Polak-Ribiere algorithm, Broyden-Fletcher-Goldfarb-Shanno algorithm, so on so ...
10
votes
4answers
1k views

Integer programming problem with simple quadratic objective function in Python

I have $n$ objects that need to be divided among $k$ groups. Each group must receive at least $5$ objects. In addition, the percentage of objects in group $i$ should be as close as possible to $p_i$ ...
10
votes
3answers
232 views

Is the “reverse search” algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities? If it is not, then what is? For $m$ inequalities in $d$ ...
10
votes
2answers
669 views

How to use warm start to solve MIPs efficiently?

I'm working on the scheduling model which takes a long time to solve to optimality (even for a small instance), therefore I would like to use a warm start (MIP start) to solve the problem. I'm using ...
10
votes
2answers
233 views

How to determine the convexity of my problem and categorize it?

My problem is: \begin{align}\min\limits_{x_{ij}}\qquad&{\sum_{i\in N}\sum_{j\in M}\frac{x_{ij}}{C_j-\sum\limits_{i\in N} x_{ij}a_i}}\\\text{s.t.}\qquad&0<C_j-\sum_{i\in N} x_{ij}a_i\\\qquad&...
10
votes
2answers
347 views

Current Issues of Interest

What are some current issue of interest in Operations Research? I am interested in current topics that experts in the field are interested in researching.
10
votes
2answers
182 views

Use integer/quadratic programming to maximize consecutive zeros in a binary array

A binary array $t = [t_1, t_2, t_3, t_4, t_5]$ with each element a binary integer variable taking values 0 or 1. You can think this vector as slots with 1 representing the slot being taken and 0 ...
10
votes
1answer
130 views

Algorithmic gap for Hochbaum's (greedy) algorithm for (metric) uncapacitated facility location

In Jain et al. (2003)1, at the bottom of page 801, they construct an instance of (metric) uncapacitated facility location for which they claim the greedy (Hochbaum's) algorithm has gap $\Omega\left(\...
10
votes
2answers
1k views

Infinite horizon versus finite horizon MDP

When can we approximate a finite horizon MDP with infinite horizon? Can we use infinite horizon stochastic shortest path problem on a directed acyclic graph?
10
votes
1answer
133 views

Approaches for choosing a “risk” factor in an Inventory Optimization problem?

I'm working on an Inventory Optimization (Allocation) problem. The decision variable is the amount of inventory budget to allocate for each product, from a set of products. My objective is to ...
10
votes
1answer
138 views

Is it possible (or straightforward) to define many secondary problems in bilevel programming?

I am new to bilevel programming. I was wondering whether it is possible (or straightforward) to formulate a bilevel problem in which there are many secondary-level problems? An example might be a ...
10
votes
1answer
107 views

Wild oscillation of dual infeasibility in Gurobi mixed-integer solver

As the question says, I am wondering what happens "behind the scene" when the Dual Infeasibility column of the Gurobi runtime log oscillates wildly, before Gurobi eventually quits with infeasibility. ...
10
votes
0answers
157 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
9
votes
4answers
553 views

Recommendations for OM blogs

Could someone suggest good blogs to follow for researchers in Operations Management/ Supply Chain Management /Operations Research?
9
votes
3answers
304 views

To which area does constraint programming belong?

The problem I solved is a flow-shop scheduling problem with parallel machines. I solved it with the IBM ILOG CPLEX Optimization framework. There I used the constraint programming (CP). The question ...
9
votes
3answers
438 views

How could we simplify solving the large scale MIPs without using any advanced methods like decompositions?

Many practical optimization models (specially MIPs) are NP-Hard and solving them need much time even with the modern solvers like CPLEX or GUROBI. One of the best way (but not easy) is using ...
9
votes
1answer
611 views

A variant of the Shortest Path Problem

Consider a layerwise directed acyclic graph DAG, $G=(V,E)$ and two vertices $s$ and $t$. $s$ is connected to all vertices in $L_0$, $L_0$ is connected to all vertices in $L_1$ and so forth. Consider ...

1
2
3 4 5
10