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
4
votes
0answers
64 views

What is this type of scheduling problem called?

I am currently working on software that deals with a specific type of scheduling problem, and I want to improve the scheduling algorithms that it uses. However, when I tried to research algorithms ...
3
votes
1answer
106 views

Having negative value for non basic variable gives a infeasible solution in simplex method?

I try to solve the following linear program with the simplex method: $$ \begin{alignedat}{4} \max & \quad & x_1 & {}-{} & 2x_2\\ \text{subject to} & & &...
6
votes
1answer
64 views

CVXPY: x * min(x)

How can I reformat the problem below to follow DCP rules? DCP rules are Disciplined Convex Programming Rules that allow convex programs to be solved. DCP Is there a way to reformat the problem ...
2
votes
1answer
83 views

Reduction of Unnecessary Parameters and Variables in an MIP

Let's observe an example constraint: $\sum \limits^E_{e\ \in \ A_a \ \cap \ B_b \ \cap \ C_c} x_{e,a,b,c} \geq n_{a,b,c} \; \; \; \forall a \in A,b \in B,c \in C$ with $e \in E$ an element and $A_a$ ...
4
votes
1answer
118 views

How to formulate this scheduling problem efficiently?

Let there be $N$ users with individual demands (of some items). Some users can have higher demands while the others can have lower demands. There are exactly $N$ service points. There is a one-to-one ...
20
votes
4answers
2k views

OR-backed serious games

A "serious game" is a game (usually a simulation) designed for a primary purpose other than pure entertainment. Games like the beer game or the fresh connection can be considered serious games serving ...
2
votes
0answers
94 views

Optimal value exceeds actual value for a minimization problem

I am solving a nonlinear numerical optimization problem in Pyomo using Scip as a solver. The goal is to minimize a certain objective function. For certain input conditions, I notice that the solver ...
14
votes
4answers
487 views

Optimization models for portfolio optimization

What are the mainstream models for portfolio optimization? We have Markowitz mean-variance model and CVaR-based models (e.g., max return subject to a CVaR constraint). What else is out there in terms ...
-3
votes
1answer
72 views

Geometric interpretation of a Linear problem with bounded variables

I have a question of how to make a geometric interpretation of this problem \begin{eqnarray} \mbox{max} & z = 3x_1+x_3 \\ s.a: & \\ & \begin{array}{cc} x_1+2x_2+x_3+x_4& =...
20
votes
4answers
4k views

What instances can be solved today by modern solvers (pure LP)?

I have found a PowerPoint presentation in which the presentor Hall claims instances could be of the size of 108 in variables and constraints to be solved today. I assume that he meant sparse problems. ...
9
votes
1answer
71 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?
14
votes
2answers
199 views

What are some real-world applications of QUBO?

QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables. It has been used for computer vision, Ramsay numbers, factoring numbers, the ...
8
votes
3answers
117 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 ...
5
votes
1answer
47 views

Minimizing a project costs through nonlinear optimization

I have a project and I want to minimize the costs. I am are responsible for the inspection of 1000 miles of sewer grid in Canada. My goal is to provide time high quality inspection reports. I tried to ...
5
votes
1answer
265 views

KKT inequality conditions

Let's say I have an objective function $$f(x_1,x_2, \cdots, x_n)$$ and $N$ constraints $$x_i \ge 0. $$ I am trying to solve it with KKT conditions. Now the objective function becomes $$f(x_1,x_2,...
14
votes
5answers
994 views

Ordered list of OR journals

Is there any compact resource that includes a list of all academic journals in the OR/MS space, ranked by journal importance? Although there are some helpful features offered by publisher websites ...
4
votes
1answer
59 views

Python PuLP - Unable to Model Non-Square Matrix

I am having issues with setting up constraints using both input arrays from excel and variable arrays within PuLP. It appears the model only works with square matrices and my final code has a matrix ...
15
votes
3answers
302 views

As an Operations Research professional, how is your time divided when working on an optimization project?

When working on an optimization project, what is the typical time division (in percentage) between the various tasks that you have to work on: Problem understanding/definition (figuring out what is ...
14
votes
3answers
152 views

Variable bounds in column generation

Consider the set covering problem \[ \begin{align} \min&\ \sum_{j=1}^nc_jx_j\\ s.t.:&\ \sum_{j=1}^na_{ij}x_j\geq 1,\quad \forall i=1,\dots,m\\ &\ 0\leq x_j \leq 1 \end{align} \] ...
8
votes
1answer
68 views

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

In Jain et. al (2003), 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(\frac{\...
10
votes
1answer
98 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 ...
13
votes
1answer
104 views

Can we replace a binary variable with a continuous variable using a quadratic equality constraint?

Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$? The function $f(x) = x^2 -x$ is not a convex function. Can ...
13
votes
3answers
121 views

Strategic planning based on average values

If you have strategic planning problems like hub location problems, the input data often consists of average values for shipping volumes etc. When planning capacities, it is risky to ignore the ...
13
votes
2answers
189 views

Guidelines for Linear Optimization approaches?

When solving a Linear Optimization model (or Linear Program), there are a lot of solution approaches. Just to name a few: Primal Simplex Dual Simplex Ellipsoid Method (as if) ...
-8
votes
1answer
97 views

Why the optimal value that minimizes a function does not satisfy condition?

I have found a solved example of A Stochastic Two-Period Model with No Setup Cost in the book Operational Research by Hillier, 7th edition, that has a lot of complicated calculations to arrive to the ...
11
votes
1answer
65 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 ...
10
votes
3answers
196 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 ...
17
votes
1answer
241 views

Usages of logarithmic mean in optimization

I have recently learned about the logarithmic mean $$ \frac{x-y}{\ln(x)-\ln(y)},\, x,y > 0. $$ See the Wikipedia entry for Logarithmic mean. It is used a lot in chemical engineering optimization ...
2
votes
1answer
74 views

One and two period policy for inventory situation

The following exercise is in the book Operational Research by Hillier, 7th edition, page 978. In this exercise $p$ and $p$ are the stockout and holding cost parameters, respectively. $𝑦^0_i$ is the ...
-7
votes
2answers
156 views

How to decide to write an objective function?

I'm working on this problem: In the Njaba river basin, the available water was allocated for the purposes of consumption, irrigation, and electric power supply among three communities. The water ...
11
votes
2answers
89 views

How can I approximate a chance constraint in a computationally tractable way?

I want to solve an optimization model that contains a constraint like $$ \Pr[F(x,\xi)\leq0]\geq1-\varepsilon $$ where $x$ are my decision variables, $\xi$ is a random vector, and $\varepsilon\in(0,1)$ ...
19
votes
4answers
204 views

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

Combinatorial Benders decomposition is a mathematical programming technique consisting into dividing a problem into a master problem and a sub problem. The master problem is solved to optimality (or ...
13
votes
3answers
192 views

Benchmark problems for scenario-based stochastic optimization

$\newcommand{\E}{\mathbb{E}}$I am working on numerical algorithms for solving convex large-scale multistage scenario-based problems and I am looking for some standard benchmarks problems. I have so ...
25
votes
4answers
184 views

How to avoid having your optimization models rusting?

When designing optimization models for external organizations, I have witnessed the following: We design an optimization model for a given problem. We fine-tune it based on a portfolio of ...
15
votes
12answers
429 views

Recommended books/materials for practical applications of Operations Research in industry

I have a Masters' degree in Mathematics. I've very fair understanding of methods and techniques of Operations Research. I am looking for a good book/material where I can see a lot of examples on Math ...
9
votes
1answer
62 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 ...
5
votes
1answer
56 views

Optimal power flow vs. economic dispatch

What is the difference between the two common optimization models for electricity systems, optimal power flow (OPF) and economic dispatch (ED)? I've heard people say that ED is just a multi-period ...
26
votes
7answers
435 views

Why is the programming code of many algorithms not public in the OR community?

In recent years, a huge number of scholars in AI and ML community are using Python to develop their algorithms and then publishing their papers and codes in GitHub. This provides an opportunity for ...
13
votes
3answers
225 views

What is the connection of Operations Research and Reinforcement Learning?

I know that Markov Chains and Markov Decision Processes have been studied in the OR community too. But, I was wondering what is the relationship of Operations Research (OR) and Reinforcement Learning (...
10
votes
2answers
147 views

Reference request: how to model nonlinear regression?

As part of my research in statistics, I recently stumbled upon the paper by Wang, 2006, although its primary audience is for those who teach. For simple linear regression, quadratic programming can ...
14
votes
3answers
139 views

Solving ATSP problem for large-scale problem

I want to solve the Asymmetric TSP for a large-scale problem for an industrial application where the company cannot buy a commercial software license. For their applications, it is very important to ...
11
votes
0answers
156 views

The difference between max-min and min-max

I am solving two-stage optimization problems in the form of $$\displaystyle\max_{x \in X}\min_{y \in Y} f(x,y),$$ where $f(x,y)$ is the solution of a mixed integer linear program (MIP). As the ...