All Questions

154 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
12
votes
0answers
123 views

Protein folding and protein design relation

I understand from active COVID-19 question Are there any COVID-19 (coronavirus) related optimization problems with input datasets that we can "crowd solve"? that protein folding problem is ...
12
votes
0answers
140 views

Integrality gap in bilevel binary linear programming problem

I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is $$ \begin{alignat}2 \min\limits_x&\...
12
votes
0answers
239 views

Categorization of optimization models

For many families of optimization problems there is some sort of classification scheme. I am thinking about the triple notation for machine scheduling introduced in "Optimization and approximation in ...
12
votes
0answers
106 views

Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?

It turns out that extending MILP with any of the constraints $y=\lfloor x\rfloor$, $y=\lceil x\rceil$, $0 < x$, or $x\notin \mathbb{Z}$ is 'equally hard'. (see my answer here, and below) ...
11
votes
0answers
172 views

Tools to implement branch-and-price algorithms

As far as I know, implementing a branch-and-price algorithm is a task far from trivial. However, there are tools such as SCIP or the BCP framework of COIN-OR that help implement such algorithms. I ...
11
votes
0answers
80 views

Armijo Line Search Parameters

I am trying to compare many unconstrained optimization algorithms like gradient method, Newton method with line search, Polak-Ribiere algorithm, Broyden-Fletcher-Goldfarb-Shanno algorithm, so on so ...
11
votes
0answers
122 views

Characterizing the solution of a (non) linear maximization program

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 \...
11
votes
0answers
193 views

Modeling an assignment/scheduling problem to minimize total wait

I have an assignment type problem in which there is a set of students, $S$, and a set of training classes $T$. Each training has a fixed start and end day and can accommodate at most 1 student. In ...
10
votes
0answers
109 views

Column generation for TSP

For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach. In the academic literature, an approach is proposed (for example here), where columns ...
10
votes
0answers
79 views

Is there a library of infeasible MINLP problems?

We have a number of test libraries to test solver performance like MINLPLIB, QPLIB, etc., but the problems in all libraries I know are overwhelmingly on the feasible side. Is there a library to test ...
10
votes
0answers
147 views

For the solution of complex gaming are we to leave behind approximation and fixed algorithms in favor of agents?

For an evolutionary extensive form game is the use of multi-agent systems a necessity or can more traditional approximate Nash equilibria and mean-field interactions suffice? Few games can be ...
9
votes
0answers
85 views

Finding primal feasible solution from optimal dual

I'm reading Boyd's notes on forming the dual problem in order to decompose the primal problem. On page 4, right before the start of the next section, he talks about how given the optimal dual solution,...
9
votes
0answers
101 views

How to monitor/debug an optimization model in a production environment professionally?

I have seen this question How to avoid having your optimization models rusting?, which is kind of related, but I am more curious about the actual monitoring and the initial design of the software in ...
9
votes
0answers
69 views

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
9
votes
0answers
137 views

Solving large-scale stochastic mixed integer program

What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
9
votes
0answers
116 views

Ill-conditioned LP in Bender's decomposition

I have implemented a Bender's decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the slave dual LP. As you can see below, the coefficients seem ...
9
votes
0answers
78 views

Examples for a kind of “set family hitting” problem

Given a ground set, say $[n]=\{1,2,\dots,n\}$, and a collection of subset families $\mathcal F_i\subseteq 2^{[n]}$, $i=1,2,\dots,m$, I want to select $m$ sets $B_i\in\mathcal F_i$ such that the ...
9
votes
0answers
83 views

Modelling resource dependency in the assignment problem

The assignment problem is well-studied and has a nice polynomial time algorithm. I'm interested in an extension of this problem where all edges are in a certain group and taking multiple edges from ...
8
votes
0answers
92 views

Modelers and modeling languages: how do you choose, and which features do you use?

There are many modeling languages and APIs around. One or more per solver, plus many that target multiple solvers: AMPL, GAMS, PuLP, JuMP, Pyomo... Among all these possibilities, why did you pick a ...
8
votes
0answers
58 views

Which Constraint solver is extensible to CSP algorithms?

I am novice to constraint programming and I need to implement the following algorithms. Backtacking Conflict-based backjumping AC partial lookahead MAC Forward checking Forward checking + dom ...
8
votes
0answers
67 views

Adjusting duals heuristically

I am solving a scheduling problem-to find shifts and task schedules- using column generation. In essence, it is a set covering problem with additional constraints. The problem seems to be that the ...
8
votes
0answers
63 views

Multiple shipments with FILO order

I am trying to solve a problem statement with the help of jsprit. There is a depot. Identical items need to be delivered or picked up. An item can have two states: Bad or good. Bad items need to be ...
8
votes
0answers
85 views

For subset selection regression as a mixed integer program, how tightly should the bounding box be set?

When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
8
votes
0answers
149 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
156 views

O.R. Brainteasers

In finance, they have lots of books and sources for interview questions. Especially, 'brainteasers' are pretty famous. A brainteaser can be logical deduction questions or questions like 'when does the ...
8
votes
0answers
80 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 ...
8
votes
0answers
75 views

Is a base-stock policy optimal for a serial inventory system with upstream stockout costs?

In a serial inventory system without fixed costs, an echelon base-stock policy is known to be optimal if there is no stockout cost at any stage except the last stage. (This was proved for finite-...
7
votes
0answers
135 views

Modeling traffic in a city

I am trying to model traffic in a city, $(i,j)$ represents a road in a city. There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
7
votes
0answers
65 views

Can demand be modeled by a limited amount of probability distributions?

In stochastic inventory control, it is very important to model the demand appropriate to set e.g. order levels. Demand can be fit to a certain probability distribution via many means (e.g. a goodness ...
7
votes
0answers
98 views

Connection between solver and Julia's JuMP Package

I'm looking for ways or tips to connect a solver with the JuMP Package. I started reading the manual of Math Opt Interface (I don't know the right terms, but I'll call it the Backend of the JuMP), ...
7
votes
0answers
65 views

Why does PuLP call copy for addition and how can I avoid it?

Using a for loop to append terms to an expression seems to be much faster than summing a group of terms all at once. Constructing the expression using a for loop uses __iadd__, which does not include ...
7
votes
0answers
58 views

Modelling a simple ordering problem to have balanced delivery days

Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
7
votes
0answers
77 views

Automatic detection of SOS variables and constraints

We've been working on a new feature for Octeract Engine, namely to automatically extract SOS structure from a model and then exploit it. While the literature is quite rich on what to do with SOS once ...
7
votes
0answers
56 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
217 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
0answers
64 views

Books in applied Online Optimization

What are books on Online Optimization other than Introduction to Online Convex Optimization? Preferably: more on applied side, rather than theoretical not limited to convex only
6
votes
0answers
55 views

Proof that the leaving variable cannot be selected as the entering one in the next round

Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
6
votes
0answers
49 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
27 views

Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
6
votes
0answers
32 views

MPX Queuing Software for Manufacturing with the GTHUBS Case

I'm teaching an Operations Management Class. A long time ago, there was a simple DOS-based product called MPX. It was based on queuing theory and let you model manufacturing processes. There was ...
6
votes
0answers
90 views

OptionalIntervalVar enforced but not working OR-TOOLS

I'm using OptionalIntervalVar and then maximizing the starts. The optimal solution is not affecting the other variables that creates the ...
6
votes
0answers
69 views

Benefits of removing slack variables during presolve

I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2): Consider the equation $4x_1+...
6
votes
0answers
109 views

Modelling issue with precedence constraint in OR-Tools

I'm trying to solve an RCPSPDc model It is infeasible, although Ilog Cplex solves it, so I think I have a modelling issue. I have more constraints but the precedence is the one that makes it ...
6
votes
0answers
60 views

Data Formulation for Mixed-Integer-Programming Models

Until now, I have used the Gurobi, CPLEX and OR-Tools (GCO) interface to formulate mixed-integer-programming models. Recently, I have discovered MiniZinc and want to utilize it to formulate big ...
6
votes
0answers
45 views

Demonstrating a given solution is basic for a MCFP?

Given a minimum-cost flow problem, how could I go about demonstrating that a specific solution (as sets of basic and non-basic (!) arcs that build a rooted spanning tree for a given graph) is basic ...
6
votes
0answers
172 views

Cplex is stuck after root node relaxation solution

I am solving an MIP through Benders decomposition (coded both generic and legacy callback versions), by employing Java with Cplex 12.9. For some of the instances, Cplex is stuck for two hours (time ...
6
votes
0answers
139 views

Minimization of car cost during 4 years problem

I am going to buy a family car at the beginning of the New Year. I am going to stay in the UK for the next 4 years. I am considering the possibility of being a customer of company A which sells BMW ...
6
votes
0answers
40 views

DOE Output Versus Testing Against Baseline

I am doing some output analysis on a discrete event simulation model and trying to interpret the results. My first step was to run the baseline model to get the response variable, let's say it's 10 ...
6
votes
0answers
179 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
0answers
83 views

Help in solving resource allocation optimization problem

I've been pondering on this question for some work optimization, and I need some help in being directed to the right direction. I have multiple customers that require an amount of $X$, $Y$ and $Z$ ...

15 30 50 per page