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
3
votes
0answers
51 views

Where I can study some job shop scheduling by course (video )?

I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver by some course/video as I see some of books and papers hard to understand . It is hoped that the ...
1
vote
0answers
63 views

How to start the Dantzig-Wolfe decomposition?

I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&...
0
votes
1answer
44 views

Adding slack nodes to min cost network flows

I have the following question. I want to clarify couple of points. As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is: Do we need to ...
2
votes
2answers
107 views

Multi-objective function normalization

I am trying to solve the multi-objective function of my linear program. Are there another approaches other than the weighted sum approximation?
2
votes
0answers
84 views

Solving transportation problem by the Network Simplex

I am trying to solve the following problem using Network Simplex method. But I have questions. My attempt: Basis Matrix$(B)$ Rows: 1, 2, 3, 4, 5 Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) $$ \...
1
vote
1answer
43 views

Maximum flow minimum cut

For the following problem I am trying to find maximum flow and minimum cut: I found the maximum flow as 6 like this: $1-3-7-8:2 flows$ $1-2-5-8: 2 flows$ $1-3-4-5-8:1 flow$ $1-3-4-6-5-8:1 flow$ But I ...
4
votes
1answer
210 views

Column generation for a linear optimization problem

I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My ...
1
vote
1answer
59 views

$i \neq j$ as a linear constraint where variables are binary

Let $i$ and $j$ be two binary variables. How can I express $i \neq j$ as a linear constraint?
0
votes
1answer
54 views

Minimum cost flow problem with negative cost arcs

As far as I know, if there is a directed arc with a negative cost, we change its direction to its opposite and get a positive cost. But in the following question, if we change the direction of the arc ...
5
votes
3answers
924 views

How do you take into account order in linear programming?

How do you write order in a linear program? For instance, you want to arrange red and blue marbles labelled 1 – 30 each, and you would want to arrange it in ascending order, you cannot have red ...
1
vote
0answers
38 views

Vertices of Polytope using Gurobi

Is there any way I can obtain all the vertices of a polytope using Gurobi? If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
3
votes
2answers
185 views

Modeling in integer programming vs modeling in constraint programming

I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams). Now I am trying to learn how to model with constraint programming. ...
3
votes
1answer
83 views

In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?

I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices. I have trouble ...
1
vote
1answer
76 views

How can I formulate an objective function that minimises the number of items required to solve a problem

I am currently trying to solve a problem where I need to minimise transport cost through the choice of vehicle (and how many of each choice) subject to a given demand. The problem: There are currently ...
3
votes
1answer
52 views

Strict inclusion for facility location formula and aggregate facility location formula

I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\...
2
votes
0answers
70 views

How to linearize this multiplicative constraint?

I have a constraint in the form $\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$ Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable). $x$ and $\zeta$ are also optimization ...
2
votes
1answer
99 views

Defining Solution Space in MILP / LP using If Then Statements

I have the following statements for an MILP: Variables: $c$ (can be $1$ or $0$); $\alpha_j$ (real numbers with $0\le\alpha_j\le1$). I have a linear inequality system for $\alpha_j$: $\sum_jv_j\...
13
votes
3answers
2k views

How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms

As part of a final project for my linear programming course, I have been asked to discuss implementations of pivot algorithms, including which combinations of the ideas we have talked about in class ...
8
votes
4answers
527 views

Algorithm for simplifying a set of linear inequalities

I am looking for an algorithm that, given a set of linear inequalities in $m$ variables, returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of ...
-2
votes
1answer
67 views

How can I model this Hyperbolic constraint?

In this problem, $\beta_u$, $w_{u,c}$ (a vector of complex elements), $x_u$ are optimization variables. Now, $||2\sqrt{\frac{\pi_u}{2}}\beta_u; h_{u,c}^{\rm H}w_{u,c}-\frac{1}{2\pi_u}x_u-1||_2\le h_{u,...
9
votes
2answers
156 views

How to get all the facet inequalities from a set of valid inequalities?

For a given set of valid inequalities $\cal V$ $$ \left\{\sum_{i}^n w_k x_i + c_k \le 0\right\}_k $$ we can obtain a polyhedron $P$ in $n$-dimensional space. It's known that the polyhedron $P$ can be ...
3
votes
0answers
63 views

Optimal Seat Allocation Problem

I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
2
votes
1answer
47 views

Understanding MDP's Dual Linear Program

I'm trying to understand a proof in Puterman'05 (Markov Decision Processes: Discrete Stochastic Systems). My question is within Theorem 6.9.1 pertaining to the equivalence of solutions to the primal (...
2
votes
0answers
61 views

How can I see the engine log when solving a LP using pulp (python)?

I wonder which command should I use to see how the steps the pulp solver is doing when solving a linear program.
2
votes
0answers
57 views

Determine set of “arbitrage-free” regional prices

I am seeking for a way how to determine set of "arbitrage-free" regional prices for a single commodity market. There are $N>1$ production units with costs $C^{prod}_i, i=1,\dots,N$ and ...
2
votes
0answers
64 views

Reading MPS file for linear programming and reconstructing the Optimization model

Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and ...
2
votes
1answer
66 views

Maximum bipartite matching with breakpoints in edge weight function

I am looking for an analogy to the problem I am facing or better yet a paper or even code. I have: Nodes from set A and B. Edges are from a single A to many B. I am framing a max bipartite matching ...
0
votes
2answers
206 views

How can I formulate this specific if-then constraint?

IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly) AND IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly) $X$ and $Y$ are binary variables. What I'm actually trying to do is to charge the ...
6
votes
1answer
176 views

Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX

Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
17
votes
7answers
3k views

Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?

If one recalls how the Simplex method is taught by hand in most LP classes it takes place entirely in $\mathbb{Q}$. All operations yield exact fractions. For this reason I'm looking for linear ...
3
votes
0answers
53 views

Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?

I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
6
votes
0answers
57 views

Estimating multistop routing costs

In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints. An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
0
votes
1answer
277 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
4
votes
1answer
92 views

How to linearize $f(x,y) = (ax+by)/(x+y)$?

I have a problem which is mainly linear but it has a non-linear component. The objective function is obj = Linear_term + $c*f(x,y)$ where, $f(x,y) = (G_1 x_1 + G_2 x_2)/(x_1 + x_2)$. The decision ...
4
votes
1answer
73 views

the set of optimal solutions of a linear programming (LP) problem as a mapping of right-hand side

Consider a linear programming (LP) problem \begin{align} M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}. \end{align} Suppose the LP is feasible and bounded for all values of $b$. We know that $M(...
0
votes
1answer
88 views

How can I find the shortest path for all nodes in a graph from a source $s$?

This is the shortest path problem. I've used a model where we can find the shortest path between the source and a specified destination. The idea behind this model is that we assign a flow of 1 for ...
6
votes
0answers
124 views

Is this a valid strong polynomial algorithm for deciding LP feasibility?

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
6
votes
1answer
240 views

Multi-period linear dynamic programming with differing in-period dependencies and changes

I’m not sure if I’m wording this right but in a nutshell, my problem is: I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
1
vote
1answer
102 views

Minimum value for a group of variables in linear programming

I want to use linear programming to assign weights to a number of groups of variables. Let's assume we have group $A$ with $x,y,$ and $z$ and group $B$ with $m,n,$ and $p$. Is it possible to define ...
7
votes
1answer
111 views

Maximizing a Ratio/Percent

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
3
votes
1answer
144 views

Derive “true” shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)

In linear programming for an optimal primal degenerate solution the values of the dual variables are in general not identical with the corresponding shadow prices. Several proposals on how to find the ...
6
votes
1answer
271 views

Can GLPK be used to solve an optimal team selection problem?

My Problem I am quite new to optimisation, so any advice is appreciated. I am currently trying to solve a problem as follows: Given a pool of people, we want to create n teams such to find the optimal ...
3
votes
1answer
85 views

Which method to use to solve this multi-objective conflicting objectives

I have the following multiobjective problem. I need to minimize the user-perceived latency while doing so aggressively minimizing user-perceived latency generates large switching cost (Reconfiguration ...
2
votes
1answer
40 views

Finding bounds on a data sensitivity scenario ILP problem

This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
2
votes
0answers
96 views

Condition for an integer program and its linear relaxation to have the same value

Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
3
votes
1answer
171 views

Why is the Lagrange Multiplier not equal the Shadow Price (Excel solver, Matlab linprog, Gurobi)?

I have a LP with equality and inequality constraints. When solving the LP with the excel-solver (GRG Nonlinear) the sensitivity report returns the lagrange multiplier for all constraints. When solving ...
3
votes
2answers
97 views

Modelling a data-sensitivity scenario as an ILP problem

I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve: When publishing data, it is sometimes important to "suppress" sensitive ...
2
votes
1answer
76 views

Can CPLEX output LP solution with primal variables only?

CPLEX writeSolution method outputs both primal and dual variable values of a LP. I know how to parse through the solution file to extract specific primal variable ...
1
vote
0answers
82 views

Expansion heuristic using gurobi reduced cost / shadow price (LP)

Gurobi 9.0.0 // C++ // LP Let us assume the following problem with three nodes: (1)-----(2)-----(3) node (1) is producing ...
1
vote
2answers
90 views

How this problem can be defined as MultiObjective optimisation

I need to optimize the end-to-end latency of a multi-component application. Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...

1
2
3 4 5
7