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
9
votes
2answers
204 views

Could reserving a hotel room potentially lead to a suboptimal allocation of rooms?

Suppose you have a standard hotel with a set of rooms. If you have booked a room for a fixed period of time, would allocating a specific room in advance potentially cause a conflict when trying to ...
9
votes
2answers
134 views

Partial derivative of LP solution $(x_1 , \ldots, x_n)$ w.r.t. $x_i$ or $a_i$

Suppose I have an optimal solution and I want to know how the solution would (likely) change if one of the coefficients in the objective function changes, or if I add a constraint that forces $x_i$ ...
9
votes
1answer
190 views

Profit Maximization vs Cost Minimization for Employee Scheduling

I wanted to write two objective functions for an employee scheduling problem (MIP) until it occurred to me, that one objective function may be redundant. Is there a difference between the cost ...
9
votes
2answers
407 views

How to maximize “contrast” between nodes on a graph?

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
9
votes
2answers
1k views

Reading an LP/MPS file using Pyomo software

I would like to know is it possible to read an LP/MPS file into the Pyomo software and solve the problem? If so, how can I do that?
9
votes
2answers
157 views

When should I use a solver for IP and MIP and can I just use a library from Python, R, Matlab, etc…?

Are there any rules of thumb for figuring out when you need to use a solver like Gurobi or CPLEX, and when you can just solve you problems directly with a Python, R, or Matlab package? Is it just a ...
9
votes
2answers
499 views

What is the difference between job shop scheduling and resource constrained project scheduling?

I read here https://slideplayer.com/slide/3353960/ that RCPS is a generalized version of job shop scheduling. I'm new to this area and I'm trying to classify a specific variation of these types of ...
9
votes
1answer
216 views

How can I model regression with an asymmetric loss function?

Mosek provided a concrete example of using the Huber loss function, Huber loss, which is great! One problem I am trying to tackle is to use asymmetric loss, as described in the answer of asymmetric ...
9
votes
2answers
214 views

How to formulate a MIP that can minimize the costs with a combination of subsets given a set?

I am trying to solve the following problem. I have a set $\{1,2,3\}$, which gives the following subsets with its costs: $\{1\}=8$, $\{2\}=9$, $\{3\}=7$, $\{1,2\}=9$, $\{1,3\}=18$, $\{2,3\}=15$ and $\{...
9
votes
1answer
997 views

Graphical method in linear programming

This page describes the graphical method to solve a linear program. The formulation is as follows. $$\begin{alignat}{2} \max &\quad Z = 200W + 100B\\ \text{s.t.} &\quad 1W + 0.8B &&\...
9
votes
2answers
368 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 ...
9
votes
2answers
445 views

Valid Inequalities and Strong Inequalities

Consider the following mixed-integer set: \begin{equation} P(A, b ; S) \stackrel{\text { def }}{=}\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \text { for } j \in S\right\} \end{...
9
votes
1answer
87 views

Problem solvable $\Rightarrow$ subproblems solvable if feasible region closed, convex?

Let $c \in \mathbb{R}^n$, $M \subseteq \mathbb{R}^n$ such that the problem \begin{align}P:\quad\min_{x \in \mathbb{R}^n}&\quad c^\intercal x\\\textrm{s.t.}&\quad x \in M\end{align} is solvable....
9
votes
1answer
144 views

Finding Dual Objective

I have the following simplified optimization problem: \begin{align}\max &\quad ax+by\\\text{s.t.}&\quad0 \le x \le \overline X\\&\quad0 \le y \le\overline Y\\&\quad z = E-x+\beta\cdot ...
9
votes
1answer
112 views

Scheduling events in order to maximize preparation time

Problem statement I'm given a set of events $E$, and $\forall e \in E$ also: a set of plausible dates on which the event can happen $D_e$ importance (weight) $w_e$ ideal preparation time duration $...
9
votes
1answer
162 views

Solving convex programs defined by separation oracles?

General question: What software can solve convex programs defined by a separation oracle? The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I ...
9
votes
1answer
216 views

How to remove or replace sub tour elimination constraints in the VRP variant models?

In many of vehicle routing problems variant (VRP), which can be formulated using MIPs, to avoid creating sub tour, we need to use sub tour elimination constraints (SEC). One of the known SEC is (I ...
9
votes
1answer
213 views

Should I factor in time as a parameter or a variable in a scheduling problem with MILP?

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
9
votes
1answer
293 views

Compute the distance from a point inside a convex set to the boundary of the set

Problem Let $\mathcal C = \{ X \in \mathbb{R}^n \mid g(X) \leq 0\}$ where $g$ is convex, and let $X_c \in \mathcal{C}$. Is there any algorithm to compute the distance from $X_c$ to the boundary of $\...
9
votes
1answer
180 views

How to classify and model this problem?

I was given the task to model the following problem and find a solution for it, but as I do not have any experience in this field, I already have trouble classifying it. There are a number of ...
8
votes
2answers
1k views

How to formulate problems in the language of mathematical programming?

The question says it all. I am having difficulties formulating general problems (meaning no numbers just variables). When I read the solution, I understand but I can't figure how to formulate myself ...
8
votes
5answers
633 views

Paper suggestions on local search algorithms

I am looking for papers (or any resources) that go deep into the details of implementing local search algorithms. I don't want an introductory paper on the subject. Rather, I would prefer a survey ...
8
votes
2answers
2k views

How to convince people that OR can help them?

When talking to people who are not familiar with what OR is and what it is about, and you want to convince them that it might be useful for them/their industry, what do you tell them in order to ...
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 ...
8
votes
3answers
623 views

Bin packing variant

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
8
votes
2answers
326 views

How can I transform this MILP into an LP problem?

I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
8
votes
3answers
189 views

Difference between “Optimization” and “Constrained Optimization”?

(Another OR noob question) As I'm trying to learn about OR and Optimization methods for work, I'm having a hard time understanding the difference between "Optimization" and "Constrained Optimization"...
8
votes
2answers
423 views

Is there a greedy heuristic approach to the MILP problem?

I have the following optimization problem which is an MILP. I can solve it with an MILP solver. \begin{alignat}{1}\max_{x_n,t}\,&\quad t\quad\\\text{s.t.}&\quad\sum_{n=1}^{N} x_n \,&= M\\...
8
votes
1answer
237 views

Standard cumulative distribution function with optimization model variable

We all know that expressions in mathematical optimization models can't contain "black boxes" around a decision variable since everything has to be written using mathematical expressions. For example, "...
8
votes
1answer
398 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 ...
8
votes
1answer
601 views

Travelling salesman problem with given number of locations to visit

There's a great example here of how to find a solution to the travelling salesman problem: ...
8
votes
2answers
2k views

How to linearize a constraint with max

I would like to linearize a constraint with max. I have the following constraint: $$\max_{pcj}X_{pwcj}\leqslant L_{wk}.$$ With this constraint, I would like to ensure that for $\forall w \in W$, no ...
8
votes
1answer
193 views

Can Gurobi or CPLEX handle nonlinearly constrained problems?

Though my title is quite general (please feel free to edit), indeed, I wonder if the following models can be solved in Gurobi or CPLEX. Model 2 is just an alternative one to Model 1. Although we ...
8
votes
1answer
247 views

GLPK: meaning of the "marginal' column in the solution output

I'm using GLPK to solve an LP. I use it through its standalone solver, that I call with the glpsol command, and I get the solution detail written in a file using ...
8
votes
1answer
170 views

Specific filter on the set using Python

I'm trying to write an optimization model using an open-source solver's Python API. I'm new to use Python. The model objective function is as follows: \begin{equation} \sum_{k=1}^{K} \sum_{j=1}^{n}\...
8
votes
1answer
257 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 ...
8
votes
2answers
165 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 ...
8
votes
2answers
2k views

How can I add this conditional constraint to my model in Python?

I am creating an optimization model with 2 sets of binary decision variables. The first, site, is regarding which of 380 cities to place manufacturing sites in, and ...
8
votes
1answer
338 views

if-else condition for the objective variable using big M notation

Let $0\leq \beta\leq 1$ be an objective variable. The size of $\beta$ is $N\!\times\!N$. Now, how can I impose the following? if $\beta_{i,j}>0$ then $\beta_{j,i}=0$ Big M notation can be ...
8
votes
1answer
238 views

Speedup or Caching for a Multi-Iteration MIP problem

I'm solving an MIP: \begin{align}\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\\text{s.t.}&\quad A\,x\geq1,\end{align} where both the matrix $A$ and vector $x$ are boolean valued, and $A$ is ...
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 ...
8
votes
1answer
377 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 ...
8
votes
1answer
178 views

What are Operations Research applications for 'morally discussable causes'?

Out of curiosity, since I read this question What are Operations Research applications for 'good causes'? and thought it might be a good addition to it. What are Operations Research ...
8
votes
1answer
304 views

How to resolve this issue in multi-objective optimization?

I have the following multiobjective optimization problem. The objectives are non-conflicting. The Optimization Problem: $$\underset{\large{a^{(l)}_{c,u},f^{(l)}_{c,u},z_{l,t},l\in\mathcal{L}}}{\max}\...
8
votes
1answer
148 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
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 ...
8
votes
1answer
77 views

Speed of convergence for minimizing Rosenbrock's function

I am minimizing $f(x_1,x_2) = 100(x_2-x_1^2)^2 + (1-x_1)^2$, where I try many algorithms to compare with each other. All of the algorithms find the optimal solution $(1,1)$ quickly, so I am not ...
8
votes
1answer
105 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
155 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
85 views

Calculating robustness of layout plans

We have tried to design a manufacturing cell which will produce specific families of products. We figure out three layout plans for implementation. For practical reasons, we need to calculate the ...

1 2
3
4 5
10