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
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
763 views

Difference between exploration and exploitation in Simulated Annealing algorithm

In evolutionary algorithms, two main abilities maintained which are Exploration and Exploitation. In Exploration the algorithm searching for new solutions in new regions, while Exploitation means ...
7
votes
1answer
889 views

Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity?

I'm trying to create an assignment optimization model where the areas are assigned to either the south or north school districts so that the total distance is minimized. Each school must have at least ...
7
votes
2answers
480 views

Can I use 'SCIP' solver for PYOMO?

I have an MINLP problem to solve where I was initially using 'ipopt' solver but the solution was not sticking to 'binary/boolean/integer' domain type for a variable. I am not sure which free solver ...
7
votes
1answer
356 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
2answers
148 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-...
7
votes
1answer
230 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
112 views

Solutions to a parametrized optimization problem

I have the following maximization program \begin{align} \max\limits_{\{q_i\}}&\quad\sum\limits_{i=1}^nq_i \\ \text{s.t.}&\quad\begin{cases} k_j \geq \sum\limits_{i=1}^n q_i^{1 \over \...
7
votes
1answer
147 views

Is the solution of a convex combination of the objective in simple problems a convex combination of the solutions of the same problems?

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 has all its entries equal to zero, and each column has at most one zero. Let also $\...
7
votes
1answer
100 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
74 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
174 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
105 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
154 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
58 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
433 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 ...
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
2answers
411 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 ...
6
votes
4answers
157 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
2answers
270 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
817 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.&\...
6
votes
1answer
217 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
2answers
157 views

Index of element in MILP vector decision variable that equals 1

Consider a decision variable in a MILP constrained: $$\sum_i p_i = 1$$ $$p_i\ \in \{0, 1\}$$ Obviously one element in $p$ is 1 and all others are 0. How can I set a decision variable to the index i of ...
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
338 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
329 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
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 ...
6
votes
2answers
167 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
2answers
554 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 ...
6
votes
1answer
193 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
194 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
598 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 ...
6
votes
1answer
91 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 ...
6
votes
2answers
125 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
91 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
74 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
176 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
117 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
69 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
120 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
198 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
91 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
76 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
88 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
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
237 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 ...
5
votes
3answers
1k views

How does a solver generally know whether a solution is optimal?

I was wondering how does the solver for a MILP determine whether a solution is optimal. I am having a hard time to believe that the solver actually tries all solutions, since in some cases I have over ...
5
votes
3answers
386 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, ...

1 2 3
4
5
10