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
8
votes
1answer
97 views

Can I use an MDP for a stochastic inventory model when my demand distribution is non-stationary?

Most formulations of Markov Decision Processes for stochastic inventory models I've come across assume a fixed demand distribution. But in my case I have a time series forecast with a non stationary ...
8
votes
0answers
153 views

Relationship between two minimization problems

Let $\mathbf{A}$ be a ${n\times J}$ matrix with $A_{ij}\geq0$ (and $A_{ij}>0$ for most $ij$, there cannot be any rows or columns that consist only of $0$s), $Q=\left\{\mathbf{q}\mid \mathbf{q}\in\...
8
votes
0answers
377 views

Having trouble with objective function in Python: “GurobiError: Variable not in model”. What else could I try?

I am trying to figure out how I can write this objective function into python using Gurobi. I have to minimize the sum of the product of three dictionary's values. The reason I am confused is that ...
7
votes
2answers
407 views

How to model bicycle sharing scheme?

One of the problems I have recently considered is the problem of rebalancing bicycle stations for bike-sharing schemes all over the world. It is not a secret that the demand for bikes across the city ...
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, ...
7
votes
2answers
262 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.&\...
7
votes
2answers
760 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.&\...
7
votes
1answer
352 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,...
7
votes
1answer
66 views

Expressing a chain of boolean if-then with logical ANDs using MIP

How to express a chain of boolean If-then as MIP such as: If $(x_{10} \ge b_1$ and $x_{11} \le b_1)$ AND $(x_{20} \ge b_2$ and $x_{21} \le b_2)$... AND... then $y_1 = 1$ else $y_1 = 0$. So basically,...
7
votes
1answer
2k 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 ...
7
votes
2answers
508 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 ...
7
votes
2answers
510 views

Solving a Certainty Equivalent (Decision Analysis) problem

I am solving a Certainty Equivalent (Decision Analysis) problem. The problem is a Risk-Averse Case - a deal of $60\%$ chance to win $\$100,\!000$ and $40\%$ chance to lose $\$10,\!000$. Suppose the ...
7
votes
1answer
90 views

How to decide the hiring headcount for a retail department

The job responsibility is exactly the same in the department. The department has a total number of working hours required. The total retention is about 50% a year, and the hiring cost is about $2000 ...
7
votes
1answer
229 views

Finding the optimal, spatially compact set of grid cells

I have a regular grid of cells, maybe square, maybe hexagonal. Each cell has a numeric value associated with it. How can I find a subset of cells that are: a connected, compact set and have an ...
7
votes
1answer
97 views

Count this to the family of Job Shop Problem?

I will explain the problem in a simplified version. Three Tasks: $T_1, T_2, T_3$ Four Machines: $M_1, M_2, M_3, M_4$ The machines $M_2$ and $M_3$ make the same processing, so they are parallel. ...
7
votes
1answer
72 views

Aggregate production planning

I'm looking for an optimization model about production planning that takes the following into consideration: Single site Multi products One machine/resource Sequence-dependent Fixed batch ...
7
votes
1answer
171 views

Custom Nurse Rostering Problem

I've asked this question also on Math Stack Exchange. It's a custom nurse rostering problem: $N$ is a set of nurses; $S$ is the set of shift-type (morning, afternoon, night, rest) $n_\mathrm{...
7
votes
1answer
98 views

Variant of job shop scheduling problem

I'm looking to identify a problem in the literature that I'm currently solving. I have a set of jobs each having a set of operations. Each operation has a duration. An operation may be done by a ...
7
votes
1answer
153 views

Why is this version of the algorithm more efficient?

I am a student self-studying Optimization, and I am reading about the Conjugate Gradient Method in Numerical Optimization by Nocedal & Wright, and they present two different algorithms for it. ...
7
votes
0answers
57 views

KKT conditions validation- one dual variable equating to two values

I have the following optimization problem: \begin{alignat}2\min &\quad A(t)\cdot x(t)-B(t)\cdot y(t)+C(t)\cdot z(t)-D(t)\cdot k(t)\\\text{s.t.}&\quad z(t)+z_1(t)-y(t)-y_1(t)+x(t) = k(t);&...
7
votes
0answers
224 views

How to make constraints satisfy disciplined convex programming guidelines?

How do I turn my convex constraints (described below) into constraints that are DCP so that I can solve them in CVXPy? Is there some ``cheat sheet'' of standard tricks? I'm trying to implement 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 ...
6
votes
3answers
289 views

Gurobi and CPLEX cannot exploit more than 32 cores of machine

I have some attempts to solve a scheduling problem using the Gurobi and doCPLEX API in python and .NET on Ubuntu-server installed on a hyper-computing cluster with 64 physical cores. Unfortunately, ...
6
votes
4answers
151 views

Sequential quadratic programming source

What are the good text books to learn SQP? Are there any online courses that you can suggest?
6
votes
1answer
213 views

Can Operations Research applications scale?

What do I mean by scaling? Let's say you developed a software for an operations research application for an industry client. Now you want to make a product out of this and sell it for other clients. ...
6
votes
3answers
595 views

How to determine if this problem is NP-HARD or NP-COMPLETE?

Suppose that I have a pool with N nodes and I have to move the nodes one by one to another pool. For each move, consider a value on the edge linking the two pools. The goal is to find a order of nodes ...
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 ...
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 ...
6
votes
2answers
317 views

Assignment problem where assignments must be done sequentially

I have a weird planning problem. I think it falls under the assignment category, but I'm not sure because I'm not familiar with assignment problems, and also because there is a "temporal" angle to it, ...
6
votes
2answers
155 views

Linear objective function with non-linear constraints

I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type $$ \underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\ $$ subject to the ...
6
votes
1answer
186 views

Extreme point and extreme ray of a network flow problem

"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) ...
6
votes
2answers
175 views

A heuristic approach to solve a MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem? Since I have an additional but ...
6
votes
2answers
116 views

Is this another variant of Job Shop Scheduling Problem?

The problem is as follows: there are $n$ jobs $\mathcal{J}=\{J_1,\ldots, J_n\}$, each of which could be done. There are $k$ machines $M_1,\ldots,M_k$ that work in parallel, independently of each other,...
6
votes
1answer
87 views

How to minimize a weighted sum of RMSE-like terms?

I am trying to solve the following problem: \begin{align} \min&\quad f(x) = \sum_{i=1}^{n}{a_ix_i} + \sum_{i=1}^{n}{b_i\sqrt{\sum_{j=1}^{m}{\left(y_{i,j}-x_i\right)^2}}}\\\text{s.t.}&\quad x_{...
6
votes
2answers
71 views

Optimizing MIP Parameters For Various Data Sets

I have a MIP that runs for several different data sets. For each data set the MIP runs multiple times, once for each time period in the data set, and each time period is independent. I've experimented ...
6
votes
1answer
160 views

Convert summation of min functions into linear constraints for optimization

I have the following optimization problem: $$ \mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{...
6
votes
1answer
114 views

Optimal Energy Charging/discharging Scheduling Problem

I'm new to IBM CP optimizer. I want to make charging / discharging scheduling based on cost (value will change on time) and my objective function is $$\sum_{t=1}^{24}\sum_{j=1}^5x(1)^{(t,j)}x(2)^{(t,j)...
6
votes
1answer
64 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 ...
6
votes
1answer
74 views

Prove that $x^*$ is an optimal solution where $f_0$ is $C^1$ and convex and $f_i$ are $C^1$ and strictly convex functions

Let $x^*$ be a feasible solution of the following convex optimization problem \begin{align}\min&\quad f_0(x)\\\text{s.t.}&\quad f_i(x)\leq0,i=1,\ldots,m\end{align} where $f_0$ is $C^1$ and ...
6
votes
1answer
104 views

Minimize binary variable's distance with respect to the index values

For a given binary decision variable $x[i,j,k]$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values: $d ...
6
votes
1answer
109 views

How to write a constraint for a directed graph?

I'm working on an optimization problem regarding a directed acyclic graph. The constraint looks in pyomo like this: ...
6
votes
1answer
168 views

GUROBI Re-optimize a model

(For Linear Programming) I am aware of CPLEX's reoptimize methods. If I am not wrong, if you solve a problem and after that you add a new constraint, then you can call the reoptimize method for not to ...
6
votes
1answer
90 views

DAG shortest path in R - I have a list of nodes, each node's completion time and each node's predecessor(s). How can I turn this to a list of arcs?

Without trying to manually sketch out a graph on paper, is there a simple way I could get the arcs between nodes in this problem? I am using R and it seems there must be an elegant way of doing so but ...
6
votes
1answer
70 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 ...
6
votes
1answer
74 views

Maximum weight b-matching with global cardinality constraint

Suppose $A$ is an $n$-by-$n$ symmetric matrix whose entries are all nonnegative. $A_{ii} = 0$ for all $i$. We want to find an $n$-by-$n$ binary ($0/1$ valued) matrix $X$ that maximizes $$\sum_{ij} A_{...
6
votes
1answer
83 views

MPS file generation

I have a code in MATLAB which uses YALMIP to structure my optimization model and solve it via a solver. I would like to obtain a .mps file out of my model, apparently, YALMIP does not produce this if ...
6
votes
0answers
221 views

Substituting inequality by equality constraints

Let $\mathbf{A}=\left(a_{ij}\right)$ be a $n\times J$ matrix with $a_{ij}\geq 0$, $n>J$ and such that no row or column has all its entries equal to zero. Let also $\mathbf{k}=\left(k_j\right)$ be a ...
6
votes
0answers
43 views

Mixing time exponent above threshold temperature for Glauber dynamics or annealing

It is well-known that the Glauber dynamics will converge in polynomial time to the Gibbs distribution for, say, the Ising model on a d-regular graph at high enough temperatures $T>T_c$. There are ...
6
votes
0answers
51 views

Semi-definite Programming, non standard notation

The usual way to define a semi-definite program (SDP), e.g., as given in Boyd and Vandenberghe's convex optimization book, is: $$ \begin{array}{cl} \min & c^\top x \\ \mathrm{s.t.} & 0 \succeq ...
6
votes
0answers
33 views

In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples

Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion. ...

1 2 3
4
5
9