This paper describes the application of an optimization-based technique to the design of novel value-added products to be synthesized from soybean oil. Soybean oil derivatives have been found in previous studies to have excellent properties, in terms of improving diesel fuel performance. The use of soybean oil derivatives to serve as improved fuel enhancers and surfactants is an example of the use of a renewable feedstock for commercial applications, which would also boost the potential market for this agricultural product. However, the number of potential products that can be synthesized using soybean oil components as precursors is very large. The goal of this work is to determine the structure of a soybean oil derivative with physical property values that most closely match those desired for a given application. An optimization methodology that allows the determination of optimal molecular structures for soybean oil-derived compounds is described. To predict the physical properties of the novel compounds, molecular connectivity indices are used as structural descriptors. New structure-property correlations for the hydrophilic-lipophilic balance, the critical micelle concentration, lubricity, surface tension, and wetting time have been generated, based on these indices, and are then used within an optimization framework to derive the optimal molecular structure for a given application requiring specific values of these properties. The optimization problems are formulated as mixed-integer linear programs (MILPs), which are then solved to determine guaranteed globally optimal solutions. In this work, second-order connectivity indices have been used within a computational molecular design algorithm for the first time to provide improved property prediction, and a novel mathematical transformation has been used to generate an exact linear representation for these indices, such that they can be included in the MILP formulation of the molecular design problem. Examples are presented for the design of a fuel additive, a textile surfactant, and fuel detergents. The novel structures found using this methodology serve as lead compounds that could then be synthesized from soybean oil components, such as palmitic acid or oleic acid, and tested for potential industrial application.