Questions tagged [optimization]
For questions involving mathematical problems that aim to minimize or maximize some objective function, possibly subject to one or more constraints.
395
questions
5
votes
0answers
211 views
What is the difference between root relaxation and LP relaxation
(I apologize. I saw this question but, I do not know these may be the same or not.)
I am trying to solve a MIP problem and have an issue about that. The problem's LP relaxation has the objective ...
11
votes
3answers
630 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 ...
3
votes
1answer
43 views
Is Multidisciplinary Design Optimization / Collaborative Optimization used anywhere outside of the Mechanical Engineering context?
I recently stumbled across the concept of Multidisciplinary Design Optimization (MDO), sometimes referred to as Multi-Disciplinary Optimization or Multidisciplinary Systems Design Optimization (MSDO), ...
3
votes
1answer
139 views
Pyomo add constraint error: Rule failed when generation expression for constraint
I am trying to solve a model with Pyomo and struggling with indexing. Below is a simple problem instance, where you can also see the error. The message is straightforward and self-explanatory but ...
2
votes
4answers
78 views
Linearity of an optimization problem which comprises the product of variables with constant values from a non-linear function
In a mathematical integer optimization problem, if the objective function is represented as $\sum x_k \cdot M_k$, where $M_k$ is a non-linear function whose value is known and just plugged in to the ...
17
votes
3answers
365 views
Best ways to use machine learning / AI as an OR scientist
I have come across GUROBI's webinar "Mathematical optimization and machine learning".
In essence, Mathematical Optimization (MO) and Machine Learning (ML) are different but complementary technologies....
1
vote
0answers
80 views
Simplex - Network flow problem : Arc from 1 to P with infinite capacity
The Network - Maximum flow problem below aims to find the maximum flow using simplex method :
With the LP as follow :
LP : \begin{Bmatrix}
Z(Max) = \sum_{i=1}^{m} fi \\
Af =0
\end{Bmatrix}
...
6
votes
1answer
329 views
Is there a name for this variation of the assignment problem?
I'm given two matrices:
$A$, an $n\times n$ adjacency matrix of a graph. The graph is unweighted, undirected and has no self-edges or multi-edges.
$X$, an $n\times n$ symmetric matrix of edge ...
4
votes
1answer
195 views
PuLP Transport Problem - How to add outcomes of decision variables together
I am working on a rail scheduling problem that moves product from a production plant to a storage facility to satisfy demand. I am new to PuLP so finding this difficult to understand why this isn't ...
4
votes
1answer
84 views
Clustering a large ride-matching problem
Background: We are solving a large scale vehicle to person ride-matching problem. The problem is essentially simple (match every person with a vehicle, if possible), yet the problem size is quite ...
24
votes
9answers
3k views
What are Operations Research applications for 'good causes'?
I am looking for applications of OR for good causes, possibly with some literature. I intend a good cause loosely defined in the sense that the scope is that of improving the well-being of others, e.g....
5
votes
1answer
109 views
Interpretability Vs Accuracy in Operations Research and Management Science Community
This question might be somewhat general and not completely relevant to this forum but I think here is the most relevant place to ask the question.
Currently, deep learning, RL and generally black-...
3
votes
1answer
107 views
How to transform these conditional constraints to linear integer ones in a more efficient way?
The conditional constraints A and B can be transformed to a set of linear integer constraints as follows:
A) $\text{if} \ x_1=0 \ \text{then} \ d_1=1 \ \text{else} \ d_1= 0\\ x_1\in {\rm I\!R}^{\geq ...
2
votes
0answers
62 views
Density Optimization by Fitting an Circle to a Field - Monte Carlo Method
Given: I have 2D non-parametric formula that provides instantaneous intensity at certain (x,y) location.
Required: I want to en-circle a region where the density is high via optimization. In other ...
8
votes
1answer
61 views
Covering problem on a network (?)
I have this problem described in natural language, and I was wondering whether it is relatable to any known problem.
I have a directed acyclic graph. Each node can host a "probe". If node $i$ hosts ...
1
vote
0answers
66 views
Ways to improve lower bounds while solving MIPs
What are the ways to improve lower bounds while solving a minimization problem (MILP)?
1
vote
2answers
187 views
Pulp: slack variable to identify & measure extent infeasible in supply problem
I am currently modelling a supply problem that attempts to optimise a rail schedule which moves products from a production plant, to a warehouse to satisfy sales.
The model is working fine (thanks in ...
3
votes
0answers
49 views
What are the efficient ways to model this scheduling problem and ways to improve running time
There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots ...
4
votes
2answers
138 views
Maximum Flow Problem : Can someone refer me to accessible valuable resources
Can anyone please refer/suggest me some accessible papers, works, books, websites, documentation related to The Maximum Flow Problem.
6
votes
2answers
1k 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 ...
3
votes
1answer
167 views
Cplex : The cutting stock problem
The problem below aims to minimize the cutting leftovers from each cut :
A company manufactures desks for kids gardens and primary schools, colleges and high schools. The leg of these deks all have ...
2
votes
0answers
55 views
Weapon Target Assignment Problem + Time Windows
So I am very familiar with the WTAP it the static case. What I am wondering, is there a formulation that has "time windows" as well? Let's say you have some weapons and some targets, you know the ...
3
votes
1answer
94 views
What kind of scheduling problem is this?
I am trying to develop algorithm to solve following basic version of the problem.
1) I would like to know what this problem is called in literature so that I can look it up
2) What are efficient ...
1
vote
1answer
150 views
How do I solve this Optimization problem?
Optimization of a simple expansion problem
minimise:
$$
\sum_{t=1}^{5}\left[\sum_{i=1}^{2}x_{i,t}CC_i\left(\frac{1+EIC}{1+r}\right)^t+UE_t*C_{UE}\right]
$$
subject to:
$$
0 \leq x_{i,t} \leq 5 \\
...
7
votes
1answer
1k views
How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour
I would like to know of a method in which if provided say 10 routes with details regarding which route intersects with which another route, we can use the least number of colours to colour the routes, ...
11
votes
1answer
411 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 ...
8
votes
3answers
1k views
Open source MILP solver for quick “good enough” solution
I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
1
vote
1answer
36 views
Enforcing discontinuous range for a variable
I want to enforce the following ranges for a set of variables, where the ranges for each variable are discontinuous. For example, I have two sets of ranges for each variable,
\begin{align}\sf LB_1 &...
4
votes
1answer
107 views
Mobile Sensor Placement for Optimal Coverage
I have come across the paper that deals with spatial positioning of mobile sensors to optimally detect sound source, or position mobile cellphone towers to maximize the coverage.
The region $Q$ is ...
2
votes
1answer
167 views
Does this problem fall into any common problem definition…Knapsack maybe?
I am struggling to find a representative problem formulation for this optimization challenge. I have implemented a MILP in Matlab, but the run time is taking more then a day. My goal is to see if it ...
2
votes
1answer
51 views
Normalization approaches to manufacturing data
I’m hoping someone would be able to help with insight to a normalization approach, I am tasked with identifying the relative difficulty between stages in a manufacturing process.
The processes can be ...
17
votes
3answers
959 views
TSP with revenue maximization
How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ...
21
votes
3answers
2k views
Are valid inequalities worth the effort given modern solvers?
In Laurence Wolsey's Integer Programming[1], he presents a well-known procedure for deriving valid inequalities (VI) suitable for integer and mixed integer linear problems (see Section 8.3, and also ...
3
votes
0answers
33 views
Constraint equivalence in PuLP
I'm working on an optimization problem in PuLP and I have to enforce a daily minimum of shifts and a daily maximum of assigned shifts. I have the following constraints to ensure each day has a minimum ...
11
votes
2answers
121 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 ...
1
vote
2answers
351 views
Solving a (Non-)Linear Programming Problem
Apologies for my basic question, but I am kinda new to optimization methods, and I am bumping into the optimization problem below:
$\min_{x} (c_1 \cdot u_1 + c_2 \cdot u_2)\\
\mbox{subject to:}\\
...
17
votes
1answer
807 views
The difference between max-min and min-max
I am solving two-stage optimization problems in the form of
$$\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 constraints of the ...
2
votes
1answer
69 views
What is the state of the art on the Weber problem?
I'm trying to get up to speed on the Weber problem. I'm very much not an expert, unfortunately. I would really appreciate recent literature recommendations / surveys / potted histories, however ...
4
votes
2answers
281 views
What are the most useful evaluation metrics when comparing the performance of different model formulations
Suppose you are writing a paper about a certain new problem class. You have certain problem instances of different size (real-world as well as random) given. You developed different integer ...
4
votes
0answers
49 views
Identifying saddle point in constrained optimization
Suppose we are minimizing $f(x)$. The first order necessary condition of $x^*$ being local minmum is:
$$\nabla f(x^*)= \mathbf{0}.$$
For sufficiency, we check if also $\nabla^2f(x^*) \succ 0$, i.e., ...
5
votes
1answer
88 views
Local minimization of a function over a line
Let $f:\mathbb{R}^n \mapsto \mathbb{R}$ be a differentiable function. Suppose $x^*$ is a local minimizer of $f$ along every line that passes through $x^*$. This means that the function $$g(\alpha) = f(...
1
vote
0answers
85 views
How do I find the extreme rays and points for a stochastic programming problem
I have the following 2 stage Stochastic Programming program:
\begin{align}\min_x& \quad x+\sum_{s=1}^{3}p_sQ_s(x)\\\text{s.t.}&\quad x\in\Bbb R\\&\quad Q_s(x)=\min\left[\begin{pmatrix}1&...
1
vote
0answers
62 views
Combining Two Different Queues
I am trying to create an optimization model for a problem that involves two different types of queues. Given Poisson demand (for both), there is a queue with constant service time and another queue ...
5
votes
2answers
122 views
Minimizing $x_1/x_2$ over a simplex in the positive orthant
I need to solve the following problem
\begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $A$ is a positive matrix.
The best thing I can think ...
8
votes
1answer
145 views
Heuristic Search Planning Tree Leading to Worse TSP Solutions than Naive Greedy
I'm doing a Traveling Salesman Problem (TSP) homework for a coursera optimization course. My first attempt was a regular naive greedy approach, from each point, moving to the closest node (that hadn't ...
8
votes
2answers
160 views
Modeling Linear Program to decide if an inequality is facet
Suppose you have a set of points $v_1,\ldots,v_n$, which are the vertices of the polytope $P=\operatorname{conv}\{v_1,\ldots,v_n\}$ and a linear inequality $a^\top v \leq b$.
What would be a linear ...
16
votes
7answers
2k views
Does there exist an aggregation of videos on optimization?
Is there a website or otherwise maintained list of talks regarding mathematical optimization? This would be a big help for the community it seems. I'm most interested in those relating to integer ...
4
votes
1answer
84 views
How to convert non-normal probabilistic constraints to deterministic ones for mathematical modelling?
I am working on a chance-constrained optimisation model that takes into account uncertainty. I am aware of how to convert constraints that are of a probabilistic nature into the equivalent ...
4
votes
1answer
85 views
Analytically finding the maximizer of a trace optimization problem
$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$.
I have a ...
3
votes
0answers
35 views
Best method to optimise the blending of different types of coal to ensure all quality parameters are met at the lowest possible price?
I am looking to optimise the blending of different types of coal for the coke making process of a steel plant. I want to take into account the statistical variation of each coal’s qualities, so for ...
