Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

Filter by
Sorted by
Tagged with
0 votes
0 answers
38 views

Is Converting to Standard Form Necessary to Check if a Proposed Solution is a Basis in Linear Programming?

If I have a Lp problem should I make it to standard form and then calculate number of 0s in the proposed solution and compare it to : number of equation - number of variables; And that's for checking ...
HAMDI ABDERRAHMENE's user avatar
1 vote
1 answer
188 views

Solver for Flexible Job Shop Scheduling Problem

I have a FJSSP that I would like to solve. However, the jobs in this problem have deadlines and in addition there are setup times between two jobs. Because of this, my objective function is not just ...
John D's user avatar
  • 199
2 votes
1 answer
193 views

Obtaining the dual ray of an infeasible lp to generate a benders feasibility cut

I am struggling to correctly interpret the meaning of a dual ray for an infeasible primal lp. Consider the following example. $$ \min z = y_1 + y_2 -2y_3 $$ s.t $$y_1 -2y_1 -y_3 \ge 3 $$ $$-2y_1 - ...
Kit Searle's user avatar
1 vote
4 answers
147 views

How to perform clustering of a large number of nodes?

I have a clustering problem with around 400-500 nodes. The edge between any two nodes has a weight (between 0 and 1, 0: can be considered as there is no edge/connection between these two nodes) as ...
KGM's user avatar
  • 2,265
1 vote
1 answer
59 views

Linearize constraints on a truncated variable

Let $K$ and $Q$ be two variables, and $Q_\min$ and $Q_\max$ be two parameters. I need a series of linear constraints to define $Q$ vis-a-vis the value of $K$ based on the following rules: If $K \le ...
Iman's user avatar
  • 11
0 votes
0 answers
118 views

Multi-Scenario Gurobi Python Output

I have an lp and am trying to solve multiple scenarios at once. One of my scenarios is infeasible though this is not the issue. For some reason, when I print m.status, both solutions have a status of ...
TroyE219's user avatar
  • 105
4 votes
1 answer
247 views

Solver for quadratically constrained mixed-integer linear programs

I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). ...
Carol Eisen's user avatar
1 vote
1 answer
100 views

Single item unconstrained lot-sizing with multiple suppliers and minimum order quantities

Variation of the traditional lot-sizing problem - with some additional complexities: multiple suppliers (S1, S2, S3), with different procurement lead-time Suppliers have to be allocated based on a ...
anerjee's user avatar
  • 119
3 votes
2 answers
168 views

How to find the maximizing number of expected delivered units of a probabilistic minimum cost flow problem?

I am a Bitcoin / Lightning Network open source developer and researcher and new here but very active on the sister site. In the context of my research I discovered the field of operations research ...
Rene Pickhardt's user avatar
2 votes
1 answer
163 views

Reduced cost fixing for binary programs

Consider the binary program $$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$ where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
rolfvdhulst's user avatar
1 vote
0 answers
38 views

Budgeted uncertainty on the RHS

Suppose we consider budgeted uncertainty (Bertsimas and Sim, 2002) for the following scenario. We have a binary decision variable $x_{i,j}$, where $i \in I$ and $j \in J$ (two sets). We then have the ...
Pia MiA's user avatar
  • 392
-2 votes
1 answer
75 views

Mixed Integer programming - Problem modelling coincidence restriction in scheduling match problem

I am trying to model and solve a problem for maximize audience of matches that must be scheduled in different slots (I am using python PulP library). Below I explain the problem and the model process ...
brtin_'s user avatar
  • 19
2 votes
3 answers
2k views

Identifying the minimum number of required machines to schedule jobs

I am relatively new to the topic of optimization. I am currently trying to address the following problem: We are given a set of jobs, say $J$ with release times, deadlines and duration. Jobs can be ...
Pia MiA's user avatar
  • 392
2 votes
0 answers
36 views

Recoverable Robustness for an optimization problem

I am relatively new to the concept of recoverable robustness. I am researching the robust version of an optimization problem. I currently have methods to address the problem with perfect knowledge. ...
Pia MiA's user avatar
  • 392
1 vote
1 answer
153 views

Mixed Integer Programming - How to model objective function with variables that depends on the solution? [duplicate]

I am modelling an optimization problem that is described as follows: I would like to maximize audience for scheduling matches. There are n eligible teams and n/2 different slots. Teams will only play ...
brtin_'s user avatar
  • 19
1 vote
1 answer
96 views

Scheduling tasks to minimize the total number of utilized cores

I currently have a scheduling algorithm which computes an approximate solution, say S, for the nominal scenario of a given problem instance, say N. Given that N changes in a way and becomes infeasible,...
Pia MiA's user avatar
  • 392
0 votes
0 answers
60 views

Gamma uncertainty in the RHS of a constraint

I am new to the concept of robust optimization.I am trying to formulate the robust variation of a Binary Integer Program. Suppose we have a constraint of the form $\sum{x_{i,j}} \geq b_j$ for $ i \in ...
Pia MiA's user avatar
  • 392
2 votes
1 answer
117 views

Separation oracle gives optimisation

Suppose I want to minimize a linear function $f$ over a convex set $K$ and I have only access to a separation oracle, that is, given a point, the oracle returns yes if the point is in $K$ and ...
abc's user avatar
  • 121
5 votes
1 answer
214 views

Short cuts when using the simplex algorithm

I haven't really kept myself up to date with research on the simplex algorithm for several years. I have taught linear programming, but it has not focused on the cutting edge of things. I remember ...
Sune's user avatar
  • 6,497
1 vote
1 answer
360 views

Optimal to-do list scheduling in Python using Pyomo

I am trying to optimally schedule a series of tasks with fixed durations between 9am and 5pm in the day (I guess kind of like a constrained knapsack problem, or job scheduling problem). I have broken ...
Jwem93's user avatar
  • 333
3 votes
1 answer
571 views

Of what size should I expect to be able to solve an integer linear program with Pyomo?

So I am solving a purely integer linear optimization problem with Pyomo on a single computer (core i-5, 12 GB RAM). The problem has around 10000 variables and 300 constraints. For doing this, I am ...
John D's user avatar
  • 199
4 votes
1 answer
335 views

Understanding reduced costs and dual values

I have a headache regarding calculating the reduced costs of a linear program. I am using Pulp for modelling and CBC for solving. What I do is, I model a linear programming problem based on a rhs ...
Djames's user avatar
  • 1,143
3 votes
1 answer
135 views

Gamma uncertainty set

I am new to the concept of robust optimization. I am currently trying to use a gamma uncertainty set (Bertsimas and Sim, 2002) for the following scenario. Suppose we have a constraint of the form $\...
Pia MiA's user avatar
  • 392
4 votes
3 answers
577 views

Determining the optimize lambda in Multi-Objective Optimization

I have a convex optimization problem: Maximize obj1 Minimize obj2 Some constraint Now to solve this problem, I used lambda to make it one problem: ...
Soroosh Noorzad's user avatar
3 votes
1 answer
62 views

Identifying worst case of realized uncertainty

I have a MILP formulation where one of the parameters in the constraints is unknown but comes from a know uncertainty set (Robust Optimization approach). As far as I researched the first step for ...
Pia MiA's user avatar
  • 392
4 votes
2 answers
226 views

how to ensure minimum output of a generator (else zero output) in linear programming?

I want to ensure, that a generator (in my case a heat generator, for example a boiler) first starts to output thermal energy, when a certain minimum output can be realized. Otherwise the output should ...
Andre's user avatar
  • 303
3 votes
1 answer
115 views

How to maximise a function with non-differentiable constraints while integrating over a time series data series with linear programming?

In this problem, I need to pick the optimal charging and discharging times and durations of an electric car-sharing battery to maximize income - not just for a single (dis)charging cycle, but a whole ...
Andreas Schuldei's user avatar
1 vote
0 answers
47 views

Smooth approximation of a five phase piecewise linear function

I am looking for a smooth (continuous differentiable) approximation of the following five-phased linear function: $$ P(U, R, P_r) = \begin{cases} R(U_{max} - U) + R(U_{up} - U_{max}) + P_r; & U \...
Ghulam Mohy-ud-din's user avatar
1 vote
1 answer
42 views

Computing simplex tableu for a given basis

I found the following problem in my book. I know that I can compute the simplex tableau , let's call it S for a basis X_b=(x_1, x2, x_5)^T as ...
tonythestark's user avatar
3 votes
3 answers
644 views

Modelling if elif else conditions as MIP

I have 4 variables. Xl6, Xs6, Pl6, Ps6. I have a constant C as well. Xl6 and Xs6 are binary whereas Pl6 and Ps6 are integers. Also, all variables can take only positive values. I have to implement ...
mufassir's user avatar
  • 201
3 votes
2 answers
150 views

Vehicle passenger assignment with capacity constraint

Problem Summary To match passengers (the number of passengers) to capacitated vehicles such that the profit is increased. All the vehicles have the same capacity $c$. It is not important to track ...
Corey's user avatar
  • 33
3 votes
3 answers
310 views

Set null the next set of N values

I'm dealing with a problem I already modelled by using linear programming. The already existing constraints set at 1 groups of contiguous variables (for ex: ...
devOn's user avatar
  • 33
-1 votes
2 answers
91 views

How to apply smooth approximation to non-linear complementarity constraints?

$P =$ $ x, if U \geq U^{max} $ $ y, if U^{up} < U < U^{max} $ $ z, if U^{down} < U < U^{up} $ $ \alpha, if U^{min} < U < U^{down} $ $ \beta, if U \leq U^{min} $ Where $P$, and $U$ ...
Ghulam Mohy-ud-din's user avatar
3 votes
1 answer
367 views

How to deal this L0 norm of a vector of L2 or L1 norms in objective?

I have an optimization variable denoted as ${\bf A\in\mathbb{C}^{100\times 5}}=[{\bf a}_1\hspace{1mm} {\bf a}_2 \hspace{1mm} {\bf a}_3 \hspace{1mm} {\bf a}_4 \hspace{1mm} {\bf a}_5];$ Here, ${\bf a}_1$...
KGM's user avatar
  • 2,265
6 votes
2 answers
499 views

Is this constraint with an indicator function nonlinear?

We have two variables $x\geq0$ and $y\in\mathbb{Z}^{0+}$. We have this constraint in our model $$x = \sum_{i = 0}c_i \mathbb{1}_{\{y=i\}}$$ where $c_i$ is a parameter and $\mathbb{1}_{A} = 1$ if $A$ ...
user avatar
4 votes
2 answers
559 views

Alternative way to restrict an employee to work on multiple jobs

Suppose I have a set of employee $E$ and set of jobs $J$ in a given time horizon $T$. I would like to make sure that no employee works on multiple jobs where each job $e\in E$ takes a certain amount ...
ball_jan's user avatar
  • 157
2 votes
1 answer
171 views

Piecewise constraint using big-M notation

I have a piecewise constraint that I am having a hard time converting using big-M modelling. The context is a gym owner that is updating membership costs subject to churn restrictions. The owner can ...
akkha's user avatar
  • 67
1 vote
2 answers
78 views

If $x_1 \geq 4$ then **one** out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$

How does one linearize the following constaints: If $x_1 \geq 4$ then one out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$. $$x_1 \leq 4 + Mz_1$$ $$x_2 \leq 3 + M(1-...
Kemit4's user avatar
  • 119
0 votes
0 answers
75 views

Transform any linear program to its standard form used in interior point solvers

I have programmed the primal-dual simplex method as explained here. The method requires the information to be passed in the standard form: $$ min:\quad c^\top \cdot x\\ s.t.:\\ A·x = b\\ x \geq 0 $$ ...
Santi Peñate-Vera's user avatar
4 votes
1 answer
179 views

How to solve a "nearly" linear program

Given a positive integer $n$, a constant $k=2/3$, and $7$ variables $x_1, x_2, x_3, x_{12}, x_{13}, x_{23}, x_{123}$ (non-negative reals or integers) I would like to find: $$\min \binom{x_1}2$$ ...
Fabius Wiesner's user avatar
3 votes
2 answers
315 views

Does solver take advantage of the problem structure?

Does Guroib take advantage of the problem structure? I am working on a large optimization problem with more than 40,000 binary variables and huge number of constraints. below is only one of the ...
Hussein Sharadga's user avatar
4 votes
1 answer
1k views

Can sensitivity analysis and limits report be done on an BILP problem?

I am not that experienced with Operations Research yet. I have become familiar with what Sensitivity Analysis and Limits Reports are in general and through the use of Excel. I know that they can only ...
Tita's user avatar
  • 205
2 votes
1 answer
265 views

Is Dantzig-Wolfe decomposition an example of a divide and conquer algorithm?

Typical Divide and Conquer algorithm solves a problem using following three steps: Divide: This involves dividing the problem into smaller sub-problems. Conquer: Solve sub-problems by calling ...
Eduardo Silva's user avatar
1 vote
0 answers
102 views

min matrix norm with gurobi v10+

I was trying to use Gurobi for a minimization problem like so: $$ \min\|M-TX\|_1 $$ where all three terms are matrices. $X$ is the nonnegative decision variable(s) of compatible size. $M$ and $T$ are ...
Brannon's user avatar
  • 900
2 votes
4 answers
492 views

How to approach this shifts problem with Excel Solver?

I am trying to find a way to solve the following problem of mine by using Solver but I get stuck right at the end of it. I have a table of 14 companies each of which want to work on a project. I will ...
Tita's user avatar
  • 205
5 votes
1 answer
987 views

How many variables and constraints can modern mixed integer programming solvers handle?

I originally asked a question here and they suggested that I crosspost it to the OR stack exchange, so that is what I am doing (hopefully correctly?). Here is the question I asked there: "I know ...
graphtheory123's user avatar
3 votes
1 answer
208 views

How do I pass an objective bound to Gurobi?

I have a non-convex Quadratic Programming over unite simplex set. I have a valid lower bound on the objective function (goal is minimization problem). If I add a constraint like $$f(x)\geq lower~bound,...
Abbas Khademi's user avatar
1 vote
0 answers
58 views

How to avoid complementarity constraints in continuous nonlinear program?

In my two-stage continuous NLP problem, I have a constraint in second stage: $X_{g,k}$ = $X_{g,0} + a_{g} d_{g} $, if $X_{g,k} \in [X_g^u,X_g^l]$ $X_{g,k} = X_g^u$, if $X_{g,k} \geq X_g^u$ $X_{g,k} ...
Ghulam Mohy-ud-din's user avatar
4 votes
1 answer
445 views

Help me reproduce this tableau from the 'Integer Programming' book

From the Integer Programming book by Conforti et al, I've sniped the image below. At the bottom of this image there is the remnants of a tableau, presumably from several iterations of the simplex ...
Brannon's user avatar
  • 900
1 vote
1 answer
72 views

An if-then-else logic whose condition is an inequality

I was hoping to get some help in modelling the following logic. I tried to solve it by "Big-M method" but failed. Thank you in advance! $a(k,n)$ and $b(k,n)$ are known constants, $\lambda$ ...
WaMIMO's user avatar
  • 33

1 2 3
4
5
17