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
16
votes
2answers
491 views

Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

The closest thing I know is the computer vision problem, in which an image is de-blurred and/or de-noised by quadratizing a quartic problem into a quadratic optimization problem (QUBO) and then the ...
6
votes
5answers
2k views

Algorithms vs LP or MIP

Is there a way of writing an algorithm with if-, while-statements to find an optimal solution without using linear-programming (LP)/MIP? If so, what would the benefits be against the LP/MIP? Is it ...
11
votes
2answers
325 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
1answer
305 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 ...
12
votes
2answers
512 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 ...
13
votes
2answers
483 views

Simulation optimisation: Monte carlo simulation, regression, optimise within regression model?

Can you help me identify if this technique has a standard name to help me explore the literature? Suppose I have a black-box stochastic simulation parameterised by $X=[x_1,...,x_p]$ with some single ...
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
2answers
122 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 ...
17
votes
6answers
2k views

Infeasibility in mathematical optimization models

Sometimes, when solving mathematical optimization models (especially MIPs), they may be infeasible. Is there any comprehensive method to deal with the infeasibility conditions? (especially in complex ...
21
votes
5answers
2k views

Validation and verification of mathematical models

Within the subject of simulation I have found some literature on validation and verification (e.g. Sargent's paper). My question is, what techniques do you use to validate and verify your mathematical ...
13
votes
7answers
870 views

What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?

I'm specifically looking for real applications of the following form of MIP: $$\max\,Cx$$ subject to: \begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{...
8
votes
1answer
161 views

Model Update for Data Driven Real Time Process Optimization

The question I am about to ask is not a technical one but rather based on following a correct approach, which I am sure would be helpful to many. I am currently working on a project which involves ...
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 ...
6
votes
1answer
3k views

How to linearize min function as a constraint?

I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed ...
6
votes
2answers
285 views

How to add Binary Variable with condition in LP

Notation $\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants. $a_{h,s},x_{i,j,s}$ are binary variables. $\text{wt}_{h,s}$ are continuous variables. Problem \begin{align}\min.&\...
6
votes
2answers
880 views

Linearization of objective function

Notation $\text{src}_{h,s},\text{dst}_{h,s},\text{ch}_{h,s}$ are constants. $a_{h,s},x_{i,j,s}$ are binary variables. $\text{wt}_{h,s}$ are continuous variables. Problem \begin{align}\min.&\...
-3
votes
2answers
202 views

Some theories and laws of Operations Research? [closed]

Can I know some theories and laws of Operation Research which has being widely used nowadays?
6
votes
2answers
597 views

How to modify EMSR when capacity for each fare class is different

In the normal EMSRa and EMSRb (Expected Marginal Seat Revenue) algorithms, each fare class is utilizes exactly 1 unit of capacity (for example, one seat on a plane). But I have a similar problem for ...
8
votes
1answer
404 views

Finding minimum time for vehicle to reach to its destination

Given a set of Vehicles with source and destination I need to find the minimum time of travel for all the vehicles, there are also some charging stations and its necessary for vehicles to charge 1 ...
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?
6
votes
1answer
75 views

Labour Model - Resource Allocation based off Product Forecasts

at my company, we have a product level forecast that we run through a model which pulls out an hours number for our retail outlets. We do this by binning various products into categories and give ...
9
votes
2answers
406 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 ...
4
votes
1answer
573 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} & & &...
8
votes
1answer
265 views

Disciplined convex programming representation of $x\cdot\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
115 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$ ...
7
votes
1answer
395 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 ...
22
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 ...
1
vote
0answers
137 views

Optimal value exceeds actual value for a minimization problem [closed]

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 ...
15
votes
4answers
756 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
88 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& =...
22
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. ...
10
votes
2answers
2k 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?
18
votes
3answers
955 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, Ramsey numbers, factoring numbers, the ...
11
votes
3answers
294 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 ...
6
votes
1answer
73 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 ...
7
votes
1answer
369 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,...
19
votes
5answers
3k 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 ...
5
votes
1answer
331 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 ...
17
votes
3answers
425 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 ...
19
votes
3answers
269 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} \] ...
10
votes
1answer
134 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
1answer
139 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 ...
16
votes
2answers
234 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 ...
14
votes
3answers
138 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 ...
18
votes
2answers
371 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
136 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 ...
12
votes
1answer
700 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 ...
11
votes
3answers
346 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 ...
20
votes
1answer
369 views

Usages of logarithmic mean in optimization

I have recently learned about the logarithmic mean $$\frac{x-y}{\ln(x)-\ln(y)},\quad x,y > 0.$$ It is used a lot in chemical engineering optimization models e.g. see slide 15 of Developing ...
4
votes
1answer
117 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 ...

1
7 8 9
10
11